An Efficient Algorithm for Influence Maximization under Linear Threshold Model
Influence maximization is to find a small set of most influential nodes in the social networks to maximize their aggregated influence in the network. The high complexity of the classical greedy algorithm cannot be well suited for the moderate or large scale networks. It is necessary to develop a more efficient algorithm, not sensitive to the scale of the social network. In this paper, we propose an approach for estimating the nodes influence based on the network structure. By this way, we make the scope of influence reduced to the nodes with the maximal influence, while make the consuming time reduced consequently. Then, we design a more efficient greedy algorithm (called LNG algorithm) for the linear threshold model. Experimental results on large scale networks demonstrate that the time consuming is much less and the influence spread effect is better than the classical greedy algorithm.
Social networks Influence maximization Linear Threshold Model Greedy algorithm
Shengfu Zhou Kun Yue Qiyu Fang Yunlei Zhu Weiyi Liu
Department of Computer Science and Engineering, School of Information Science and Engineering, Yunnan University,Kunming, 650091 China
国际会议
长沙
英文
5352-5357
2014-05-31（万方平台首次上网日期，不代表论文的发表时间）