[1]花勇,陈伯伦,朱国畅,等.基于渗流模型的影响力最大化算法[J].智能系统学报,2019,14(6):1262-1270.[doi:10.11992/tis.201906039]
HUA Yong,CHEN Bolun,ZHU Guochang,et al.An influence maximization algorithm based on percolation model[J].CAAI Transactions on Intelligent Systems,2019,14(6):1262-1270.[doi:10.11992/tis.201906039]
点击复制
HUA Yong,CHEN Bolun,ZHU Guochang,et al.An influence maximization algorithm based on percolation model[J].CAAI Transactions on Intelligent Systems,2019,14(6):1262-1270.[doi:10.11992/tis.201906039]
基于渗流模型的影响力最大化算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
14
期数:
2019年第6期
页码:
1262-1270
栏目:
学术论文—智能系统
出版日期:
2019-11-05
- Title:
- An influence maximization algorithm based on percolation model
- Keywords:
- social network; influence maximization; seed set; percolation; propagation probability; giant component; phase point; phase value
- 分类号:
- TP301.6
- 摘要:
- 多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优，忽略网络自身传播影响力的固有能力。本文对网络进行渗流模拟，计算渗流后网络的主连通分量随着传播概率改变的趋势，并且求得主连通分量大小增加开始变快的相变点，从而计算网络自身传播影响力的固有能力。通过相变值与种子节点集合大小的换算，求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范围内即可获得最佳的影响力。在kareteclub、football、highschool和socdolphins社交网络数据集上进行实验，验证了该方法的有效性。
- Abstract:
- Most of the influence maximization algorithms in social networks only focus on whether the influence of the seed node set selected is the optimal, and ignore the inherent ability of social network’s propagating influence. Using percolation simulation, we calculate the change trend of the giant component of the network generation after percolation with propagation probability, and derive the starting point at which the size of the giant component increases fastest, that is, the phase point. The phase value shows the inherent ability of the network propagating influence. The optimal seed set size of the network can be calculated through conversion of the phase value and the size of the seed set. We can obtain the optimal influence by limiting the size of the seed set to the optimal size. We performed experiments on karate club, football, high school, and soc-dolphins, verifying the effectiveness of the algorithm.
- 参考文献/References:
-
[1] BOND R M, FARISS C J, JONES J J, et al. A 61-million-person experiment in social influence and political mobilization[J]. Nature, 2012, 489(7415):295-298.
[2] 蒋庆丰, 门朝光, 田泽宇, 等. 社会感知的延迟容忍网络节点合作机制[J]. 哈尔滨工程大学学报, 2017, 38(6):921-930 JIANG Qingfeng, MEN Chaoguang,TIAN Zeyu,et al. A social-aware node cooperation mechanism for DTN[J]. Journal of Harbin Engineering University, 2017, 38(6):921-930
[3] LU Zaixin, FAN Lidan, WU Weili, et al. Efficient influence spread estimation for influence maximization under the linear threshold model[J]. Computational social networks, 2014, 1:2.
[4] MORONE F, MAKSE H A. Corrigendum:influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 527(7579):544.
[5] ZHU Zhiguo. Discovering the influential users oriented to viral marketing based on online social networks[J]. Physica A:statistical mechanics and its applications, 2013, 392(16):3459-3469.
[6] SADOVYKH V, SUNDARAM D, PIRAMUTHU S. Do online social networks support decision-making?[J]. Decision support systems, 2015, 70:15-30.
[7] SCHMITT P, SKIERA B, VAN DEN BULTE C. Referral programs and customer value[J]. Journal of marketing, 2011, 75(1):46-59.
[8] VERBRAKEN T, GOETHALS F, VERBEKE W, et al. Predicting online channel acceptance with social network data[J]. Decision support systems, 2014, 63:104-114.
[9] GUILLE A, HACID H, FAVRE C, et al. Information diffusion in online social networks:a survey[J]. ACM SIGMOD record, 2013, 42(1):17-28.
[10] GOLDENBERG J, LIBAI B, MULLER E. Talk of the network:a complex systems look at the underlying process of word-of-mouth[J]. Marketing letters, 2001, 12(3):211-223.
[11] KEMPE D, KLEINBERG J, TARDOS é. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, USA, 2003:137-146.
[12] NEMHAUSER G L, WOLSEY L A, FISHER M L. An analysis of approximations for maximizing submodular set functions-I[J]. Mathematical programming, 1978, 14(1):265-294.
[13] FISHER M L, NEMHAUSER G L, WOLSEY L A. An analysis of approximations for maximizing submodular set functions-II[M]//BALINSKI M L, HOFFMAN A J. Polyhedral Combinatorics:Dedicated to the Memory of D. R. Fulkerson. Berlin, Heidelberg:Springer, 1978:73-87.
[14] CORNUEJOLS G, FISHER M L, NEMHAUSER G L. Location of bank accounts to optimize float:an analytic study of exact and approximate algorithms[J]. Management science, 1977, 23(8):789-810.
[15] WILLIAMS H P. Integer and combinatorial optimization[J]. Journal of the operational research society, 1990, 41(2):177-178.
[16] CHEN Wei, WANG Chi, WANG Yajun. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, USA, 2010:1029-1038.
[17] LEE J R, CHUNG C W. A fast approximation for influence maximization in large social networks[C]//Proceedings of the 23rd International Conference on World Wide Web. Seoul, Korea, 2014:1157-1162.
[18] JUNG K, HEO W, CHEN Wei. IRIE:scalable and robust influence maximization in social networks[C]//Proceedings of IEEE 12th International Conference on Data Mining. Brussels, Belgium, 2012:918-923.
[19] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature physics, 2010, 6(11):888-893.
[20] CARMI S, HAVLIN S, KIRKPATRICK S, et al. A model of Internet topology using k-shell decomposition[J]. Proceedings of the national academy of sciences of the United States of America, 2007, 104(27):11150-11154.
[21] GAO Shuai, MA Jun, CHEN Zhumin, et al. Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A:statistical mechanics and its applications, 2014, 403:130-147.
[22] 王皓, 高立群, 欧阳海滨. 多种群随机差分粒子群优化算法及其应用[J]. 哈尔滨工程大学学报, 2017, 38(4):652-660 WANG Hao, GAO Liqun, OUYANG Haibin. Multi-population random differential particle swarm optimization and its application[J]. Journal of Harbin Engineering University, 2017, 38(4):652-660
[23] 刘畅, 刘利强, 张丽娜, 等. 改进萤火虫算法及其在全局优化问题中的应用[J]. 哈尔滨工程大学学报, 2017, 38(4):569-577 LIU CHANG, LIU Liqiang, ZHANG Lina, et al. An improved firefly algorithm and its application in global optimization[J]. Journal of Harbin Engineering University, 2017, 38(4):569-577
[24] JI Shenggong, Lü Linyuan, YEUNG C H, et al. Effective spreading from multiple leaders identified by percolation in the susceptible-infected-recovered (SIR) model[J]. New journal of physics, 2017, 19(7):073020.
[25] NEWMAN M E J. Spread of epidemic disease on networks[J]. Physical review E, 2002, 66(1):016128.
[26] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563):65-68.
[27] CHEN Shuo, FAN Ju, LI Guoliang, et al. Online topic-aware influence maximization[J]. Proceedings of the VLDB endowment, 2015, 8(6):666-677.
[28] LIU Bo, CONG Gao, XU Dong, et al. Time constrained influence maximization in social networks[C]//Proceedings of IEEE 12th International Conference on Data Mining. Brussels, Belgium, 2012:439-448.
[29] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4):452-473.
[30] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences of the United States of America, 2001, 99(12):7821-7826.
[31] ROSSANA M, JULIE F, ALAIN B, et al. Contact patterns in a high school:a comparison between data collected using wearable sensors, contact diaries and friendship surveys[J]. PLoS one, 2015, 10(9):e0136497.
[32] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations:can geographic isolation explain this unique trait?[J]. Behavioral ecology and sociobiology, 2003, 54(4):396-405.
[33] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1):35-41.
[34] 李阅志, 祝园园, 钟鸣. 基于k-核过滤的社交网络影响最大化算法[J]. 计算机应用, 2018, 38(2):464-470 LI Yuezhi, ZHU Yuanyuan, ZHONG Ming. k-core filtered influence maximization algorithms in social networks[J]. Journal of computer applications, 2018, 38(2):464-470
- 相似文献/References:
-
[1]孔庆超,毛文吉,张育浩.社交网站中用户评论行为预测[J].智能系统学报,2015,10(3):349.[doi:10.3969/j.issn.1673-4785.201403019]
KONG Qingchao,MAO Wenji,ZHANG Yuhao.User comment behavior prediction in social networking sites[J].CAAI Transactions on Intelligent Systems,2015,10():349.[doi:10.3969/j.issn.1673-4785.201403019]
[2]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报,2015,10(6):949.[doi:10.11992/tis.201507042]
WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,10():949.[doi:10.11992/tis.201507042]
[3]石磊,杜军平,周亦鹏,等.在线社交网络挖掘与搜索技术研究[J].智能系统学报,2016,11(6):777.[doi:10.11992/tis.201612007]
SHI Lei,DU Junping,ZHOU Yipeng,et al.A survey on online social network mining and search[J].CAAI Transactions on Intelligent Systems,2016,11():777.[doi:10.11992/tis.201612007]
[4]熊尧,李弼程,王子玥.基于两级传播理论的舆论超网络传播分析[J].智能系统学报,2020,15(5):870.[doi:10.11992/tis.201903011]
XIONG Yao,LI Bicheng,WANG Ziyue.Analysis of public opinions in network communication based on the two-level communication theory[J].CAAI Transactions on Intelligent Systems,2020,15():870.[doi:10.11992/tis.201903011]
[5]杨宇迪,周丽华,杜国王,等.异质信息网络中基于网络嵌入的影响力最大化[J].智能系统学报,2021,16(4):757.[doi:10.11992/tis.202009047]
YANG Yudi,ZHOU Lihua,DU Guowang,et al.Influence maximization based on network embedding in heterogeneous information networks[J].CAAI Transactions on Intelligent Systems,2021,16():757.[doi:10.11992/tis.202009047]
[6]陈伯伦,朱国畅,纪敏,等.代价约束下基于随机游走的负影响力传播抑制方法[J].智能系统学报,2022,17(2):266.[doi:10.11992/tis.202101037]
CHEN Bolun,ZHU Guochang,JI Min,et al.Negative influence propagation suppression method based on a random walk under cost constraint[J].CAAI Transactions on Intelligent Systems,2022,17():266.[doi:10.11992/tis.202101037]
[7]常新功,王金珏.基于图卷积集成的网络表示学习[J].智能系统学报,2022,17(3):547.[doi:10.11992/tis.202107048]
CHANG Xingong,WANG Jinjue.Network representation learning using graph convolution ensemble[J].CAAI Transactions on Intelligent Systems,2022,17():547.[doi:10.11992/tis.202107048]
[8]孟祥福,赖贞祥,崔江燕.集合空间关键字内聚组查询方法[J].智能系统学报,2024,19(3):707.[doi:10.11992/tis.202211013]
MENG Xiangfu,LAI Zhenxiang,CUI Jiangyan.Cohesive group query approach for collective spatial keywords[J].CAAI Transactions on Intelligent Systems,2024,19():707.[doi:10.11992/tis.202211013]
备注/Memo
收稿日期:2019-06-21。
基金项目:国家自然科学基金项目（61602202）；江苏省自然科学基金项目（BK20160428）.
作者简介:花勇,男,1994年生,硕士研究生,主要研究方向为影响力最大化与复杂网络;陈伯伦,男,1986年生,讲师,博士,主要研究方向为链接预测、推荐系统和数据挖掘。主持国家自然科学基金青年基金、江苏省自然科学基金青年基金多项。发表学术论文30余篇;朱国畅,男,1996年生,硕士研究生,主要研究方向为人工智能、数据挖掘与机器学习。
通讯作者:陈伯伦.E-mail:chenbolun1986@163.com
更新日期/Last Update:
2019-12-25