[1]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]
Copy
An influence maximization algorithm based on percolation model
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
14
Number of periods:
2019 6
Page number:
1262-1270
Column:
学术论文—智能系统
Public date:
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
- CLC:
- TP301.6
- DOI:
- 10.11992/tis.201906039
- 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
- Similar References:
Memo
-
Last Update:
2019-12-25