An Efficient Algorithm for Influence Maximization Based on Propagation Path Analysis

摘要

The problem of influence maximization is to find a subset of nodes in a social network which can make the influence spreading maximized. Although traditional centrality measures can better identify the influential nodes, there are still some disadvantages and limitations. In this paper, we firstly propose a propagation path model which can find m paths with the highest probability from a certain node to other nodes in the network. Then utilizing the propagation model, the node set that are most likely to activate a certain node can be obtained. By implementing simulations in three real networks, we verify that our proposed algorithm can outperform well-known centrality measures. We also use the independent cascade model (IC) to evaluate the spreading ability of nodes with different centrality measures. In comparison with traditional centrality methods, our method is more stable and generally applicable. Besides, we apply PPA method extended to signed networks where we proposed PPAS method, through the experiments on real data sets, our PPAS method has the better performance in identifying the state of the nodes in networks.