Tree-Coritivity-Based Influence Maximization in Social Networks

被引：0
作者：
Zhu E.-Q. [1 ,2 ]
Wu Y.-L. [2 ]
Xu Y.-G. [2 ]
Niu Y.-Y. [2 ]
机构：
[1] Institute of Computing Science and Technology, Guangzhou University, Guangzhou, 510006, Guangdong
[2] School of Electronics Engineering and Computer Science, Peking University, Beijing
来源：
Tien Tzu Hsueh Pao/Acta Electronica Sinica | 2019年 / 47卷 / 01期
关键词：
Algorithm; Diffusion models; Influence maximization; Social network; Tree-core; Tree-coritivity;
D O I：
10.3969/j.issn.0372-2112.2019.01.021
中图分类号：
学科分类号：
摘要：
Influence maximization problem in social networks deals with finding a small subset of nodes, which could maximize the spread of influence. It has been proved that this problem is NP-hard under the commonly used diffusion models. Although many algorithms have been proposed to solve this problem approximately, it is still a challenge to guarantee the spread of influence within a low time complexity. For this, we propose a novel method based on tree-coritivity theory and give a polynomial-time algorithm, for finding the initial active nodes required in the influence maximization problem. Our algorithm considers both the structure and the propagation characteristics of a network. Moreover, by experiment, we compare this algorithm with other conventional node-selection methods such as Random, Degree and Greedy. The results demonstrate that the proposed algorithm can find the node set that can widely spread the information efficiently. © 2019, Chinese Institute of Electronics. All right reserved.
引用
收藏
页码：161 / 168
页数：7
相关论文
共 24 条
[1]  
Stanley W., Katherine F., Social Network Analysis in The Social and Behavioral Sciences, Social Network Analysis: Methods and Applications, pp. 1-27, (1994)
[2]  
Domingos P., Richardson M., Mining the network value of customers, Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 57-66, (2001)
[3]  
Richardson M., Domingos P., Mining knowledge-sharing sites for viral marketing, Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 61-70, (2002)
[4]  
Kempe D., Kleinberg J., Tardos E., Influential nodes in a diffusion model for social networks, In International Colloquium on Automata, Languages and Programming, 32, pp. 1127-1138, (2005)
[5]  
Kempe D., Kleinberg J., Tardos E., Maximizing the spread of influence in a social network, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146, (2003)
[6]  
Leskovec J., Krause A., Et al., Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420-429, (2007)
[7]  
Kimura M., Saito K., Tractable models for information diffusion in social networks, Knowledge Discovery in Databases: PKDD 2006, pp. 259-271, (2006)
[8]  
Chen W., Wang C., Wang Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029-1038, (2010)
[9]  
Wang Y., Cong G., Song G., Xie K., Community-based greedy algorithm for mining top-k influential nodes in mobile social networks, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1039-1048, (2010)
[10]  
Goyal A., Lu W., Lakshmanan L.V., SIMPATH: an efficient algorithm for influence maximization under the linear threshold model, IEEE 11th International Conference on Data Mining (ICDM), pp. 211-220, (2011)
123