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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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-peng1,2, ZUO Yang1,2, WANG Hong-yu1,2   

  1. 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:

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

中图分类号: