基于3-layer中心度的社交网络影响力最大化算法

摘要/Abstract

摘要： 社交网络影响最大化问题是指如何寻找网络中有限的初始节点,使得影响的传播范围最广。一些贪心算法可以得到较好的影响范围,但是因时间复杂度太高而不适用于大型社交网络。基于度中心性的启发式算法简单但准确度不高；基于介数中心性、接近中心性等全局指标的启发式算法可以较好地识别影响力最大的节点,但计算复杂度也过高。考虑网络节点深层次结构对影响扩散的作用并权衡计算复杂度与准确度,定义了3-layer局部中心度,以计算节点的潜在影响力值。基于线性阈值模型,启发选择一部分种子节点:每一次都选取潜在影响力最大的节点作为种子节点进行激活；运用贪心算法选取剩下的一部分种子节点:每一次都选取具有最大影响增量的节点作为种子节点进行激活。实验表明,该混合算法具有很好的激活范围以及非常低的时间复杂度。

关键词: 社交网络,影响力最大化,启发式算法,3-layer局部中心度,贪心算法

Abstract: Influential maximization in a social network is the problem of finding the limited initial nodes which can maximize the spread of influence．Some greedy algorithms can get wide spread of influence,but have too high cost to be applied in large-scale social networks．The heuristic method based on degree centrality is simple but of low accuracy．Heuristic algorithms based on global metrics such as betweenness centrality and closeness centrality can better identify the most influential nodes,but the computational complexity of which is much high too．As a tradeoff between the low-accurate degree centrality and other time-consuming measures,we defined the 3-layer local centrality for computing the potential influence of nodes．Based on linear threshold model,we selected some seed nodes through the heuristic algorithm in which the node with maximal potential influence is selected at each step,and we chose another seed nodes by the greedy algorithm in which the node with the largest influence increment is chosen at each time．The experimental results show that our hybrid algorithm has good spread of influence and low time complexity．

Key words: Social network,Influence maximization,Heuristic algorithm,3-layer local centrality,Greedy algorithm

王俊,余伟,胡亚慧,李石君. 基于3-layer中心度的社交网络影响力最大化算法[J]. 计算机科学, 2014, 41(1): 59-63. https://doi.org/

WANG Jun,YU Wei,HU Ya-hui and LI Shi-jun. Heuristic Algorithm Based on 3-layer Centrality for Influence Maximization in Social Networks[J]. Computer Science, 2014, 41(1): 59-63. https://doi.org/

参考文献

[1] Leskovec J,Adamic L A,Huberman B A．The dynamics of viral marketing[J]．ACM Transactions on the Web,2007,1(1)
[2] Richardson M,Domingos P．Mining knowledge-sharing sites for viral marketing[C]∥Preceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining．KDD,2002:61-70
[3] Kempe D,Kleinberg J,Tardos E．Maximizing the spread of influence through a social network[C]∥Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining．Washington,USA,2003:137-146
[4] Tian Jia-tang,Wang Yi-tong,Feng Xiao-jun．A new hybrid algorithm for influence maximization in social networks[J]．Chinese Journal of Computers,2011,4(10):1956-1965
[5] Chen Hao,Wang Yi-tong．Threshold-Based Heuristic Algorithm for Influence Maximization[J]．Journal of Computer Research and Development,2012,9(10):2181-2188
[6] Nicosia V,Criado R,Nunes M,et al．Controlling centrality incomplex networks[J]．Scientific Reports,2012(2):218-223
[7] Okamoto K,Chen W,Li X-Y．Ranking of closeness centrality for large-scale social networks[C]∥Proceedings of the 2nd Annual International Workshop on Frontiers in Alogorithmics,FAW’08．2008:186-195
[8] Freeman L．Centrality in social networks conceptual clarification[J]．Social Networks,1979(1):215-239
[9] Bonacich P,Lloyd P．Eigenvector-like measures of centrality for asymmetric relations[J]．Social Networks,2001(23):191-201
[10] kosch D,Lehmann K A,Peeters L,et al．Centrality indices[J]．Network,2005,3418:16-61
[11] Chen Duan-bing,Lü Lin-yuan,Shang Ming-sheng,et al．Identi-fying in fluential nodes in complex networks[J]．Physica A:Statistical Mechanics and its Applications,2012(391):1777-1787
[12] Lü Lin-yuan,Zhang Yi-cheng,Yeung Chi-Ho,et al．Leaders in social networks,the delicious case[J]．PloSOne,2011,6(6):e21202
[13] Brin S,Page L．The anatomy of a large-scale hyper textual web search engine[J]．Computer Networks and ISDN Systems,1998(30):107-117
[14] Hou Bo-nan,Yao Yi-ping,Liao Dong-sheng．Indentifying all-round nodes for spreading dynamics in complex networks[J]．Physica A,2012(391):4012-4017
[15] Wei Dai-jun,Deng Xin-yang,Zhang Xiao-ge,et al．Identifying influential nodes in weighted nodes in weighted networks based on evidence theory[J]．Physica A:Statistical Mechanics and its Applications,2013,2(10):2564-2575
[16] Chen Yi-cheng,Chang Su-hua,Chou Chien-li,et al．ExploringCommunity Structures for Influence Maximization in Social Networks[C]∥The 6th SNA-KDD Workshop’12(SNA-KDD’12)
[17] Zhang Xiao-hang,Zhu Ji,Wang Qi,et al．Identifying influential nodes in complex networks with community structure[J]．Knowledge-Based Systems,2013(42):74-84
[18] Aggarwal C C,Lin Shu-yang,Yu P S．On influential node discovery in dymamic social networks[C]∥ Proceedings of the Eleventh SIAM International Conference on Data Ming,SDM 2011.Mesa,Arizona,USA,2011:636-647
[19] Yong H P．The diffusion of innovations in social networks[C]∥Blume L,Durlauf S．The Ecomomy as a Complex System III．USA:Qoford University Press,2003:1-19
[20] Watts D J．A simple model of global cascades on random networks[J]．National Academy of Sciences,2002,9(9):5766-5571
[21] Glodenberg J,Libai B,Muller E．Talk of the network:A com-plex systems look at the underlying process of word-of-mouth[J]．Marketing Letters,2001,2(3):211-223

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed