基于社交网络结构的节点影响力度量方法

doi:10.3969/j.issn.0372-2112.2016.12.022

电子学报 ›› 2016, Vol. 44 ›› Issue (12): 2967-2974.DOI: 10.3969/j.issn.0372-2112.2016.12.022

基于社交网络结构的节点影响力度量方法

李泽鹏^1,2, 左杨^1,2, 王宏宇^1,2

1. 北京大学高可信软件技术教育部重点实验室, 北京 100871;
2. 北京大学信息科学技术学院, 北京 100871

收稿日期:2015-01-30 修回日期:2016-01-20 出版日期:2016-12-25
- 通讯作者:
- 李泽鹏
- 作者简介:
- 左杨,男,1990年出生于安徽安庆.北京大学信息科学技术学院硕士研究生,主要研究方向为社交网络结构分析;王宏宇,女,1988年出生于黑龙江牡丹江.北京大学信息科学技术学院博士研究生,主要研究方向为图论与组合优化,社交网络结构.
- 基金资助:
- 国家自然科学基金 (No.61672050，No.61372191，No.61572492，No.61572046，No.61502012）; 国家973重点基础研究发展计划 (No.2013CB329600）; 中国博士后科学基金 (No.2016M591013）; 江西省教育厅项目 (No.GJJ150686）

An Influence Measure of Nodes Based on Structures of Social Networks

LI Ze-peng^1,2, ZUO Yang^1,2, WANG Hong-yu^1,2

1. Key Laboratory of High Confidence Software Technologies(Peking University), Ministry of Education, Beijing 100871, China;
2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

Received:2015-01-30 Revised:2016-01-20 Online:2016-12-25 Published:2016-12-25
- Supported by:
- National Natural Science Foundation of China (No.61672050, No.61372191, No.61572492, No.61572046, No.61502012); National Key Basic Research Program of China (973 Program) (No.2013CB329600); China Postdoctoral Science Foundation (No.2016M591013); Program of Education Department of Jiangxi Province (No.GJJ150686)

摘要/Abstract

摘要：

度量社交网络节点影响力是社交网络结构分析的关键问题之一.目前研究社交网络节点影响力的方法主要有两大类：中心度方法和节点删除方法.前者主要通过度或最短路径等因素来判断节点的影响力，不考虑网络的连通性；后者通过节点删除后对网络结构的破坏程度来判断，计算复杂性很高，不适用于较大规模的社交网络.通过结合社交网络的局部连通度及节点间的最短路径，提出了连通中心度来度量社交网络中节点的影响力，并给出了连通中心度的计算方法和一些特殊网络中节点的连通中心度的值.最后，通过实验说明该指标能很好地度量社交网络中节点的影响力.

关键词: 社交网络, 节点影响力, 中心度方法, 连通中心度, 最短路

Abstract:

Identifying the influence of nodes is one of the major research topics in the structural analysis of social networks.The current measures of researching the node influence can be divided into two categories:centrality measure and node removal measure.The former mainly identifies the influence of the node by degree or shortest path,without considering the connectivity of social networks; while the latter by the damage of the structure of a social network when some nodes are removed.The node removal measure is incapable to be applied in large-scale since the computational complexity.We propose a new parameter,connectedness centrality,to identify the influence of nodes in networks by combining the local connectivity and shortest paths.We give a method to compute the connectedness centrality of the node and obtain the precise values in some specific networks.Finally,an experiment using a real-word network shows that our method can well identify the influence of the node in social networks.

Key words: social networks, node influence, centrality measure, connectedness centrality, shortest path

中图分类号:

TP399

李泽鹏, 左杨, 王宏宇. 基于社交网络结构的节点影响力度量方法[J]. 电子学报, 2016, 44(12): 2967-2974.

LI Ze-peng, ZUO Yang, WANG Hong-yu . An Influence Measure of Nodes Based on Structures of Social Networks[J]. Acta Electronica Sinica, 2016, 44(12): 2967-2974.

参考文献

[1] Newman M E.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[2] Boccaletti S,Latora V,Moreno Y,et al.Complex networks:Structure and dynamics[J].Physics Reports,2006,424(4):175-308.
[3] Zhang J,Zhou C,Xu X,et al.Mapping from structure to dynamics:A unified view of dynamical processes on networks[J].Physical Review E,2010,82(2):026116.
[4] Zhou T,Wang B H.Catastrophes in scale-free networks[J].Chinese Physics Letters,2005,22(5):1072-1075.
[5] Pastor-Satorras R,Vespignani A.Immunization of complex networks[J].Physical Review E,2002,65(3):036104.
[6] Freeman L C.Centrality in social networks conceptual clarification[J].Social Networks,1979,1(3):215-239.
[7] Sabidussi G.The centrality index of a graph[J].Psychometrika,1966,31(4):581-603.
[8] Freeman L C.A set of measures of centrality based on betweenness[J].Sociometry,1977,40(1):35-41.
[9] Bonacich P.Factor and weighting approaches to status scores and clique identification[J].Journal of Mathematical Socilogy,1972,2(1):113-120.
[10] Bonacich P.Some unique properties of eigenvector centrality[J].Social Networks,2007,29(4):555-564.
[11] Borgatti S P,Everett M G.A graph-theoretic perspective on centrality[J].Social Networks,2006,28(4):466-484.
[12] Chen D B,Lü L Y,Shang M S,et al.Identifying influential nodes in complex networks[J].Physica A,2012,391(4):1777-1787.
[13] Chvátal V.Tough graphs and Hamiltonian circuits[J].Discrete Mathematics,1973,5(3):215-228.
[14] 许进,席酉民,汪应洛.系统的核与核度(I)[J].系统科学与数学,1993,13(2):102-110. Xu J,Xi Y M,Wang Y L.On system core and coritivity (1)[J].Journal of System Science and Mathematical Science,1993,13(2):102-110.(in Chinese)
[15] Jung H A.On a class of posets and the corresponding comparability graphs[J].Journal of Combinatorial Theory Series B,1978,24(2):125-133.
[16] Sun J,Tang J.A survey of models and algorithms for social influence analysis[A].Social Network Data Analytics[C].New York:Springer,2011.177-214.
[17] 吴信东,李毅,李磊.在线社交网络影响力分析[J].计算机学报,2014,37(4):735-752. Wu X D,Li Y,Li L.Influence analysis of online social networks[J].Chinese Journal of Computers,2014,37(4):735-752.(in Chinese)
[18] Ma S J,Ren Z M,Ye C M,et al.Node influence identification via resource allocation dynamics[J].International Journal of Modern Physics C,2014,25(11):1450065.
[19] Saito K,Kimura M,Ohara K,et al.Super mediator-A new centrality measure of node importance for information diffusion over social network[J].Information Sciences,2016,329:985-1000.
[20] Hu F,Liu Y H.Multi-index algorithm of identifying important nodes in complex networks based on linear discriminant analysis[J].Modern Physics Letters B,2015,29(03):1450268.
[21] Kim H,Anderson R.Temporal node centrality in complex networks[J].Physical Review E,2012,85(2):605-624.
[22] Kas M,Wachs M,Carley K M,et al.Incremental algorithm for updating betweenness centrality in dynamically growing networks[A].Advances in Social Networks Analysis and Mining (ASONAM),2013 IEEE/ACM International Conference on IEEE[C].Niagara Falls,Canada:IEEE/ACM,2013.33-40.
[23] Gao Z X,Shi Y,Chen S Z.Measures of node centrality in mobile social networks[J].International Journal of Modern Physics C,2015,26(09):1550107.
[24] Zhang X,Zhu J,Wang Q,et al.Identifying influential nodes in complex networks with community structure[J].Knowledge-Based Systems,2013,42(2):74-84.
[25] Shakarian P,Salmento J,Pulleyblank W,et al.Reducing gang violence through network influence based targeting of social programs[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA:ACM,2014.1829-1836.
[26] He X,Kempe D.Stability of influence maximization[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. New York,USA:ACM,2014.1256-1265.
[27] Zhou C,Zhang P,Zang W,et al.Maximizing the long-term integral influence in social networks under the voter model[A].Proceedings of the 23rd International Conference on World Wide Web Conferences Steering Committee[C].Seoul,Korea:ACM,2014.423-424.
[28] Morone F,Makse H A.Influence maximization in complex networks through optimal percolation[J].Nature,2015,524(7563):65-68.
[29] Lamba H,Narayanam R.A model-independent approach for efficient influence maximization in social networks[J].Social Network Analysis & Mining,2015,5(1):1-11.
[30] Menger K.Zur allgemeinen Kurventheorie[J].Fundamenta Mathematicae,1927,10:96-115.
[31] Ford L P,Fulkerson D R.Maximal flow through a network[J].Canadian Journal of Mathematics,1956,8(3):399-404.
[32] Ford L P,Fulkerson D R.Flows in Networks[M].Princeton NJ:Princeton University Press,1962.
[33] Edmonds J,Karp R M.Theoretical improvements in algorithmic efficiency for network flow problems[J].Journal of the ACM,1972,19(2):248-264.
[34] Goldberg V A,Tarjan E R.A new approach to the maximum flow problem[J].Journal of the ACM,1988,35(4):921-940.
[35] Floyd R W.Algorithm 97:Shortest path[J].Communications of the ACM,1962,5(6):345.
[36] Johnson D B.Efficient algorithms for shortest paths in sparse networks[J].Journal of the ACM,1977,24(1):1-13.
[37] Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

基于社交网络结构的节点影响力度量方法

An Influence Measure of Nodes Based on Structures of Social Networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王飞扬, 冀鹏欣, 孙笠, 危倩, 李根, 张忠宝. 一种基于深度学习的动态社交网络用户对齐方法[J]. 电子学报, 2022, 50(8): 1925-1936.
[2]	高鹏, 柴鹏翔, 郎俊. 基于0-1背包算法的社交网络行为隐写术[J]. 电子学报, 2022, 50(3): 753-758.
[3]	王志晓, 张磊, 孙成成, 芮晓彬, 黄珍珍, 张孙贤. 基于社区划分与连边逆序放回的网络分解算法[J]. 电子学报, 2022, 50(3): 540-547.
[4]	焦贤龙, 郭松涛, 黎勇, 李艳涛, 向朝参. 基于相继干扰消除和跨层并发传输的物联网数据聚合调度[J]. 电子学报, 2021, 49(10): 1982-1992.
[5]	郭荣梅, 胡小兵. 求解时间窗口网络中前k条最短路径的方法[J]. 电子学报, 2020, 48(7): 1387-1395.
[6]	宋宇琦, 高旻, 李骏东, 荣文戈, 熊庆宇. 网络欺凌检测综述[J]. 电子学报, 2020, 48(6): 1220-1229.
[7]	刘露, 胡封晔, 牛亮, 彭涛. 异质网络中基于节点影响力的相似度度量方法[J]. 电子学报, 2019, 47(9): 1929-1936.
[8]	於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
[9]	肖云鹏, 孙华超, 戴天骥, 李茜, 李暾. 一种基于云模型的社交网络推荐系统评分预测方法[J]. 电子学报, 2018, 46(7): 1762-1767.
[10]	肖云鹏, 刘晏驰, 刘红, 刘媛妮. 一种基于动态角色标识和张量分解的推荐模型[J]. 电子学报, 2018, 46(3): 569-574.
[11]	于建业, 王元卓, 靳小龙, 程学旗. 基于社交演化博弈的社交网络用户信息分享行为演化分析[J]. 电子学报, 2018, 46(1): 223-229.
[12]	陈杰, 刘学军, 李斌, 章玮. 一种基于用户动态兴趣和社交网络的微博推荐方法[J]. 电子学报, 2017, 45(4): 898-905.
[13]	肖云鹏, 刘瀚松, 刘宴兵. 一种基于二部图和节点角色划分的社交网络推荐方案[J]. 电子学报, 2017, 45(10): 2425-2433.
[14]	王锐, 吴玲玲, 石川, 吴斌. 基于社团结构的链接预测和属性推断联合解决方法[J]. 电子学报, 2016, 44(9): 2062-2067.
[15]	许文文, 时鹏, 于留宝, 胡长军. 一种在线社交网络的自适应观点引导模型及实现[J]. 电子学报, 2016, 44(7): 1714-1720.