﻿ 基于渗流模型的影响力最大化算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (6): 1262-1270  DOI: 10.11992/tis.201906039 0

### 引用本文

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.

### 文章历史

An influence maximization algorithm based on percolation model
HUA Yong , CHEN Bolun , ZHU Guochang , YUAN Yan , JIN Yin
School of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 223003, China
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.
Key words: social network    influence maximization    seed set    percolation    propagation probability    giant component    phase point    phase value

1 问题描述 1.1 影响力最大化问题

1.2 独立级联模型

1.3 影响力函数

2 算法思想与步骤

1) For i=1:1:len(plist)

2) 　For j=1:1: R

3) 　　根据plist (i)对G'进行渗流模拟，形成　　　渗流后网络GP，并且获得GP的最大连通　　　子图GP'

4) 　　 C(j,i)=num(GP')；

End

End

5) C' =avg(C)；

6) 对plistC进行多项式拟合，求得拟合　　　函数F(x)；

7) 求F(x)的导函数dF(x)；

8) 通过函数dF(x)求得相变值pc

9) 最优种子集合大小 $k' = {p_c} \times n$

1)函数len(x)用来计算数组的长度，所以len(plist)的值等于1 000，此步骤具体是：在传播概率 $p \in {p_{list}}$ 的情况下，对网络G' 进行渗流；

2)采用当前传播概率p对网络G' 进行R次渗流；

3)渗流模型的定义如下：在网络G' 中，网络每条边具有统一的传播概率值p。我们对每条边产生独立的随机值pr，如果pr<p，那么此边处于占有状态，如果pr>p，那么此边处于非占有状态，也就是此边从网络中删除。通过改变统一的传播概率值p，那么存在一个值pc，当p>pc时，GP中的节点倾向于紧密的连接在一起，形成一个主团块。当p<pc时，GP中的节点倾向于形成多个零散的小团块。pc便称为网络G'的相变值。图1为渗流实验例图，图1(a)为2维晶格网络，网络中边的概率统一为p图1(b)图1(d)为渗流模拟后的网络，并且边的概率逐渐提高，我们发现当边的概率较低时，渗流模拟后的网络倾向于形成零散的团块，当边的概率较大时，渗流模拟后的网络倾向于形成一个主团块，其存在一个过度值，即网络由零散的团块到形成一个主团块的值，即相变值。图1(d)为2维晶格网络发生渗流时的状态，相变值pc=0.6。在3)中，通过对网络G' 进行渗流模拟，可以得到渗流后的网络GP并且计算求得GP的最大连通子图GP'

4)函数num(x)用于计算网络中节点的个数，所以此步骤是将GP'的节点个数存入到C中；

5)函数avg(x)用于计算矩阵每列的平均值，所以此步骤是对传播概率pR个num(GP')求平均值，并且存入到C' 中，也就是说，每个传播概率p，我们都会对G' 进行R次渗流模拟，从而产生R个num(GP')，最后将其求平均，即得到每个传播概率p所对应GP'的平均大小；

6)采用多项式拟合的方法对plistC' 进行拟合。多项式拟合是使用多项展开式去近似数据点的函数关系，并使用最小二乘法来得到多项展开式的系数，最终求得数据点函数关系的方法。多项式拟合公式为

 $F(x) = {a_0} + {a_1}x + {a_2}{x^2} + \cdots + {a_l}{x^l}，$ (1)

7)求函数F(x)的导函数dF(x)；

8)相变值pcpm的左邻域中，其中dF(pm)的值为函数dF(x)的最大值，dF(pc)的值为靠近dF(pm)最近的最小值，相变值pc为函数F(x)变化速率开始加快的起点位置；

9)求取最优种子集合大小。

 Download: 图 1 渗流实验例图 Fig. 1 The example of percolation experiment
3 实验结果及分析

3.1 渗流实验

 Download: 图 2 渗流实验 Fig. 2 The percolation experiment
3.2 相变值

 Download: 图 3 拟合函数变化速率 Fig. 3 The changing rate of fitting function

3.3 影响力模拟

 Download: 图 4 影响力模拟 Fig. 4 The influence simulation
3.4 平均影响力分析

 Download: 图 5 平均影响力 Fig. 5 The average influence

4 结束语

 [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. DOI:10.1038/nature11421 (0) [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. (0) [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. DOI:10.1186/s40649-014-0002-3 (0) [4] MORONE F, MAKSE H A. Corrigendum: influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 527(7579): 544. (0) [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. DOI:10.1016/j.physa.2013.03.035 (0) [6] SADOVYKH V, SUNDARAM D, PIRAMUTHU S. Do online social networks support decision-making?[J]. Decision support systems, 2015, 70: 15-30. DOI:10.1016/j.dss.2014.11.011 (0) [7] SCHMITT P, SKIERA B, VAN DEN BULTE C. Referral programs and customer value[J]. Journal of marketing, 2011, 75(1): 46-59. DOI:10.1509/jmkg.75.1.46 (0) [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. DOI:10.1016/j.dss.2013.08.011 (0) [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. DOI:10.1145/2503792.2503797 (0) [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. DOI:10.1023/A:1011122126881 (0) [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. (0) [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. DOI:10.1007/BF01588971 (0) [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. (0) [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. DOI:10.1287/mnsc.23.8.789 (0) [15] WILLIAMS H P. Integer and combinatorial optimization[J]. Journal of the operational research society, 1990, 41(2): 177-178. DOI:10.1057/jors.1990.26 (0) [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. (0) [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. (0) [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. (0) [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. DOI:10.1038/nphys1746 (0) [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. DOI:10.1073/pnas.0701175104 (0) [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. DOI:10.1016/j.physa.2014.02.032 (0) [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. (0) [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. (0) [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. DOI:10.1088/1367-2630/aa76b0 (0) [25] NEWMAN M E J. Spread of epidemic disease on networks[J]. Physical review E, 2002, 66(1): 016128. DOI:10.1103/PhysRevE.66.016128 (0) [26] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563): 65-68. DOI:10.1038/nature14604 (0) [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. DOI:10.14778/2735703.2735706 (0) [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. (0) [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. DOI:10.1086/jar.33.4.3629752 (0) [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. (0) [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. DOI:10.1371/journal.pone.0136497 (0) [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. DOI:10.1007/s00265-003-0651-y (0) [33] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41. DOI:10.2307/3033543 (0) [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. (0)