基于树核度的社交网络影响最大化问题

doi:10.3969/j.issn.0372-2112.2019.01.021

电子学报 ›› 2019, Vol. 47 ›› Issue (1): 161-168.DOI: 10.3969/j.issn.0372-2112.2019.01.021

基于树核度的社交网络影响最大化问题

朱恩强^1,2, 吴艳蕾², 许宇光², 牛云云²

1. 广州大学计算科技研究院, 广东广州 510006;
2. 北京大学信息科学技术学院, 北京 100871

收稿日期:2015-04-22 修回日期:2016-07-17 出版日期:2019-01-25
- 作者简介:
- 朱恩强 男,1983年6月出生,辽宁人.2015年获北京大学信息科学技术学院理学博士学位,现为北京大学信息学院博士后,主要从事图论与组合优化、社交网络信息传播及安全、DNA序列编码理论的研究.E-mail:zhuenqiang@pku.edu.cn
- 基金资助:
- 国家973重点基础研究发展计划 (No.2013CB329600，No.2013CB329602，No.2013CB329606）; 国家自然科学基金 (No.61572046，No.61572492，No.61472433）

Tree-Coritivity-Based Influence Maximization in Social Networks

ZHU En-qiang^1,2, WU Yan-lei², XU Yu-guang², NIU Yun-yun²

1. Institute of Computing Science and Technology, Guangzhou University, Guangzhou, Guangdong 510006, China;
2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

Received:2015-04-22 Revised:2016-07-17 Online:2019-01-25 Published:2019-01-25
- Supported by:
- National Program on Key Basic Research Project of China (973 Program) (No.2013CB329600, No.2013CB329602, No.2013CB329606); National Natural Science Foundation of China (No.61572046, No.61572492, No.61472433)

摘要/Abstract

摘要： 社交网络中的影响最大化问题是指对于给定的k值，寻找k个在特定传播模型下能够使得传播范围达到最大的节点.此问题在常用的几种传播模型中都是NP-难的.目前虽然已经有很多近似求解的算法，但如何在较低的算法时间复杂度下，保证较大的传播范围仍然是求解该问题的一个挑战.为此，本文提出了一种新颖的基于图的树核度理论的方法来求解社交网络影响最大化问题，并相应地给出了一个多项式时间的算法.所提算法综合考虑了网络的结构特征和传播特征.另外，我们将该算法与传统的随机、度以及贪心算法进行了比较.实验结果表明，所提算法可以较快地找到能够使得传播范围较大的节点集合.

关键词: 树核度, 树核, 社会网络, 算法, 影响最大化, 传播模型

Abstract: 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.

Key words: tree-coritivity, tree-core, social network, algorithm, influence maximization, diffusion models

中图分类号:

TN95

朱恩强, 吴艳蕾, 许宇光, 等. 基于树核度的社交网络影响最大化问题[J]. 电子学报, 2019, 47(1): 161-168.

ZHU En-qiang, WU Yan-lei, XU Yu-guang, et al. Tree-Coritivity-Based Influence Maximization in Social Networks[J]. Acta Electronica Sinica, 2019, 47(1): 161-168.

参考文献

[1] Stanley W,Katherine F.Social Network Analysis in The Social and Behavioral Sciences[M].Social Network Analysis:Methods and Applications.Cambridge University Press.1994.1-27.
[2] Domingos P,Richardson M.Mining the network value of customers[A].Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2001.57-66.
[3] Richardson M,Domingos P. Mining knowledge-sharing sites for viral marketing[A].Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2002.61-70.
[4] Kempe D,Kleinberg J,Tardos E.Influential nodes in a diffusion model for social networks[J].In International Colloquium on Automata,Languages and Programming,2005,32:1127-1138.
[5] Kempe D,Kleinberg J,Tardos E.Maximizing the spread of influence in a social network[A].Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington,USA,2003.137-146.
[6] Leskovec J,Krause A,et al.Cost-effective outbreak detection in networks[A].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2007.420-429.
[7] Kimura M,Saito K.Tractable models for information diffusion in social networks[A].Knowledge Discovery in Databases:PKDD 2006[C].Springer,2006.259-271.
[8] Chen W,Wang C,Wang Y.Scalable influence maximization for prevalent viral marketing in large-scale social networks[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2010.1029-1038.
[9] Wang Y,Cong G,Song G,Xie K.Community-based greedy algorithm for mining top-k influential nodes in mobile social networks[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2010.1039-1048.
[10] Goyal A,Lu W,Lakshmanan L V.SIMPATH:an efficient algorithm for influence maximization under the linear threshold model[A].IEEE 11th International Conference on Data Mining (ICDM)[C].IEEE,2011.211-220.
[11] Chen W,Wang Y,Yang S.Efficient influence maximization in social networks[A].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].ACM,2009.199-208.
[12] Jiang Q,Song G,et al.Simulated annealing based influence maximization in social networks[A]. AAAI 2011[C].San Francisco,California,USA,Augest 2011.127-132.
[13] Jung K,Heo W,Chen W.IRIE:Scalable and robust influence maximization in social networks[A].Proceedings of the 2012 IEEE 12th International Conference on Data Mining[C].2012.918-923.
[14] Li J S,Yu Y Y.Scalable influence maximization in social networks using the community discovery algorithm[A].Process of the 6th International Conference on Genetic and Evolutionary Computing[C].Washington DC USA:IEEE Computer Society,2012.284-287.
[15] Zhu Y,Wu W,Bi Y,et al.Better approximation algorithms for influence maximization in online social networks[J].Journal of Combinatorial Optimization,2013:1-12.
[16] Cheng S,Shen H et al.2014.IMRank:influence maximization via finding self-consistent ranking[A].In Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval (SIGIR'14)[C].ACM,New York,USA,2014.475-484.
[17] Cohen E,Delling D,Pajor T,Werneck R F.Sketch-based inuence maximization and computation:Scaling up with guarantees[A].In Conference on Information and Knowledge Management,CIKM[C].Shanghai,China,2014.629-638.
[18] Lucier B,Oren J,Singer Y.Influence at scale:distributed computation of complex contagion in networks[A].Process of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA:ACM,2015.
[19] Zhu E Q,Li Z P,et al.Tree-core and tree-coritivity of graphs[J].Information Processing Letters,2015,115(10):754-759.
[20] Bondy J A,Murty U S R.Graph Theory[M].Springer,2008.
[21] 欧阳克智,欧阳克毅,于文池.图的相对断裂度[J].兰州大学学报,1993,29(3):43-48. Ouyang K Z,Ouyang K Y,Yu W C.Relative breaktivity of graphs[J].Journal of Lanzhou University,1993,29(3):43-48(in Chinese).
[22] Guimera R,Danon L,et al.Self-similar community structure in a network of human interactions[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,68(2):93-108.
[23] Gleiser P,Danon L.Community structure in JAZZ[J].Advances in Complex Systems.2011,6(4):565-573.
[24] Goldenberg J,Libai B,Muller E.Talk of the network:a complex systems look at the underlying process of word-of-mouth[J]. Mark Lett 2001,12(3):211-223.

基于树核度的社交网络影响最大化问题

Tree-Coritivity-Based Influence Maximization in Social Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	饶伟, 贾凤勤, 李旦. 有色噪声下不相关和相干混合信号的DOA估计[J]. 电子学报, 2023, 51(3): 622-631.
[2]	李杨帅, 彭斐, 韩倩, 李小帅, 解光军. 一种针对QCA电路自动布局布线的混合策略研究[J]. 电子学报, 2023, 51(3): 666-674.
[3]	刘云涛, 申泽生, 方硕, 王云. 高吞吐率流水线结构的ZUC-256流密码硬件设计[J]. 电子学报, 2023, 51(2): 438-445.
[4]	胡向东, 吕高飞, 白银. 基于优化支持向量回归的工业互联网安全态势预测方法[J]. 电子学报, 2023, 51(2): 446-454.
[5]	熊小峰, 黄淳岚, 乐光学, 戴亚盛, 杨晓慧, 杨忠明. 边缘计算中基于综合信任评价的任务卸载策略[J]. 电子学报, 2022, 50(9): 2134-2145.
[6]	陇盛, 陶蔚, 张泽东, 陶卿. 非光滑强凸情形Adam型算法的最优收敛速率[J]. 电子学报, 2022, 50(9): 2049-2059.
[7]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[8]	魏振春, 傅宇, 马仲军, 吕增威, 石雷, 张本宏. 带时间窗的无线可充电传感器网络多目标路径规划算法[J]. 电子学报, 2022, 50(8): 1819-1829.
[9]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[10]	穆磊, 王鹏. 量子启发式优化算法的尺度动态调速机制[J]. 电子学报, 2022, 50(7): 1664-1673.
[11]	陈嘉兴, 程杰, 董云玲, 刘志华. 基于弯曲声线和测距修正的水下节点定位算法[J]. 电子学报, 2022, 50(7): 1567-1572.
[12]	唐捷凯, 胡蓉, 钱斌, 金怀平, 向凤红. 混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题[J]. 电子学报, 2022, 50(7): 1621-1630.
[13]	吴晓晓, 李刚强, 张胜利. 分布式协作频谱感知网络中恶意节点检测和定位方法研究[J]. 电子学报, 2022, 50(6): 1370-1380.
[14]	许皓文, 陆浩, 王振占. 高光谱微波辐射计系统中2GHz带宽数字谱仪设计[J]. 电子学报, 2022, 50(6): 1472-1479.
[15]	宋鑫, 程乃平, 廖育荣, 倪淑燕, 雷拓峰. 具有逆向边增长结构LT码的设计与分析[J]. 电子学报, 2022, 50(5): 1201-1210.