Shortest Path Tree Maximize Node Influence Propagation in Complex Networks

Influence maximization has been one hot topic in the field of network analysis in recent years. The essence of influence maximization is to find a given number, k, seed nodes, so that their influence can diffuse to as many other nodes as possible in the network. Considering the timeliness and the value attenuation of information in the transmission, we believe that information spreading along the shortest path from one node to another is the fastest way between the pair of nodes. The shortest paths originated from any node form a shortest-path tree, and using the shortest-path tree to estimate the influence of the root node is an effective approach. Motivated by this, we propose an influence maximization algorithm based on the shortest-path tree in this paper, we name it SPTIM (acronym for Shortest Path Tree based Influence Maximization). Firstly, for every node, the shortest paths are identified to form its shortest-path tree, then its influence is estimated according to the rules developed in this paper. Afterwards, the node with the largest estimated influence is selected as a seed. Then, To alleviate the problem of influence overlapping, we attenuate the one- and two-hop neighbors of the selected seed with different proportions considering the impact of community structure. Next, the node with the largest influence is selected as another seed accordingly. This procedure is repeated until the number of selected nodes reaches k. The experimental results on some real networks under the IC, LT, and SIR models show that the proposed method, SPTIM, is competitive in terms of performance and efficiency.