[1]花勇,陈伯伦,朱国畅,等.基于渗流模型的影响力最大化算法[J].智能系统学报,2019,14(06):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(06):1262-1270.[doi:10.11992/tis.201906039]
点击复制

基于渗流模型的影响力最大化算法(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第14卷
期数:
2019年06期
页码:
1262-1270
栏目:
出版日期:
2019-11-05

文章信息/Info

Title:
An influence maximization algorithm based on percolation model
作者:
花勇 陈伯伦 朱国畅 袁燕 金鹰
淮阴工学院 计算机与软件工程学院, 江苏 淮安 223003
Author(s):
HUA Yong CHEN Bolun ZHU Guochang YUAN Yan JIN Yin
School of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 223003, China
关键词:
社交网络影响力最大化种子节点集合渗流传播概率主连通分量相变点相变值
Keywords:
social networkinfluence maximizationseed setpercolationpropagation probabilitygiant componentphase pointphase value
分类号:
TP301.6
DOI:
10.11992/tis.201906039
摘要:
多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优,忽略网络自身传播影响力的固有能力。本文对网络进行渗流模拟,计算渗流后网络的主连通分量随着传播概率改变的趋势,并且求得主连通分量大小增加开始变快的相变点,从而计算网络自身传播影响力的固有能力。通过相变值与种子节点集合大小的换算,求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范围内即可获得最佳的影响力。在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(03):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(06):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(06):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(06):777.[doi:10.11992/tis.201612007]

备注/Memo

备注/Memo:
收稿日期:2019-06-21。
基金项目:国家自然科学基金项目(61602202);江苏省自然科学基金项目(BK20160428);江苏省六大人才高峰项目(XYDXX-034).
作者简介:花勇,男,1994年生,硕士研究生,主要研究方向为影响力最大化与复杂网络;陈伯伦,男,1986年生,讲师,博士,主要研究方向为链接预测、推荐系统和数据挖掘。主持国家自然科学基金青年基金、江苏省自然科学基金青年基金多项。发表学术论文30余篇;朱国畅,男,1996年生,硕士研究生,主要研究方向为人工智能、数据挖掘与机器学习。
通讯作者:陈伯伦.E-mail:chenbolun1986@163.com
更新日期/Last Update: 2019-12-25