Optimizing influence propagation in directed networks: Novel formulations

Abstract

This paper aims to identify influential nodes in complex networks in a short period of time by proposing novel formulations. Traditional centrality metrics have ranked nodes based on individual centrality values, which fall short in identifying several influential nodes simultaneously. Recent literature has introduced an optimization model as a solution to this limitation; however, this model has some shortcomings such as long solution return time and high memory usage. In this paper, two novel formulations are presented as alternatives to this optimization model, with a primary goal of reducing the time needed to obtain solutions. Computational tests have shown that whereas the existing model is unable to return a solution within a 5hour time frame for a small network with approximately 5,000 nodes, the proposed formulations can identify the most influential nodes within minutes, even for large networks with more than 100,000 nodes. The superiority of the proposed models actually lies in their significant reduction in the number of constraints and variables compared to the existing model. Additionally, this paper introduces a novel alternative formulation that addresses the overlapping effect observed in the previous formulations. Computational tests have shown that this model surpasses its predecessors in accelerating the spread of influence throughout the network without causing additional computational burden, thereby setting a better benchmark for future studies in this field.