计算机工程 ›› 2020, Vol. 46 ›› Issue (5): 94-101,108.doi: 10.19678/j.issn.1000-3428.0054340

• 人工智能与模式识别 • 上一篇    下一篇

基于图结构特征分析的Top-k结构洞发现算法

朱江a, 包崇明b, 王崇云c, 周丽华a, 孔兵a   

  1. 云南大学 a. 信息学院;b. 软件学院;c. 生态学与环境学院, 昆明 650091
  • 收稿日期:2019-03-22 修回日期:2019-05-10 发布日期:2019-05-31
  • 作者简介:朱江(1992-),男,硕士研究生,主研方向为社交网络安全;包崇明,副教授、硕士;王崇云,副教授、博士;周丽华,教授、博士;孔兵(通信作者),副教授、博士。
  • 基金项目:
    国家自然科学基金(61762090,31760152);云南省教育厅科学研究基金(2019J0005)。

Discovery Algorithm for Top-k Structure Holes Based on Graph Structure Feature Analysis

ZHU Jianga, BAO Chongmingb, WANG Chongyunc, ZHOU Lihuaa, KONG Binga   

  1. a. School of Information Science and Engineering;b. School of Software;c. School of Ecology and Environmental Science, Yunnan University, Kunming 650091, China
  • Received:2019-03-22 Revised:2019-05-10 Published:2019-05-31

摘要: 结构洞通常指社交网络中处于信息扩散关键位置的节点,此类节点对社交网络舆情控制、影响力分析、信息传播等具有重要作用。为快速准确地找到社交网络中的结构洞,提出一种基于图最短路径增量的Top-k结构洞发现算法。通过计算并分析节点的图最短路径增量、连通分量个数和节点方差确定其结构洞属性值,并依据该属性值对节点进行排序,从而发现Top-k结构洞。同时,结合中介中心性算法进行节点的过滤与筛选,大幅降低算法的时间复杂度。在真实网络和不同规模LFR人工合成网络上的实验结果表明,与经典结构洞发现算法相比,该算法具有更高的结构洞检测效率。

关键词: 结构洞, 图最短路径增量, 中介中心性, 信息扩散, 复杂网络

Abstract: Structure holes refer to the nodes located in the key positions for information diffusion in social network,which have significant influence on public opinion control,influence analysis and information promotion in social network.In order to find structure holes in social network quickly and accurately,this paper proposes a discovery algorithm for Top-k structure holes based on the Shortest Path Increment of Graph(SPIG).The algorithm calculates and analyzes the SPIG of nodes,the Number of Connected Components(NCC) and VAR,so as to determine the value of structure hole attributes.Based on this value,the nodes are sorted to find the Top-k structure holes.Also,the Betweenness Centrality(BC) algorithm is used to filter and select the nodes,so as to significantly reduce the time complexity of the proposed algorithm.Experimental results on real networks and different sizes of LFR simulated complex networks show that the proposed algorithm is more efficient in structure hole detection than classic structure hole discovery algorithms.

Key words: structure hole, Shortest Path Increment of Graph(SPIG), Betweenness Centrality(BC), information diffusion, complex network

中图分类号: