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

作     者：朱江 包崇明 王崇云 周丽华 孔兵 ZHU Jiang;BAO Chongming;WANG Chongyun;ZHOU Lihua;KONG Bing

作者机构：云南大学信息学院昆明650091 云南大学软件学院昆明650091 云南大学生态学与环境学院昆明650091 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2020年第46卷第5期

页      面：94-101,108页

学科分类：08[工学] 081203[工学-计算机应用技术] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61762090,31760152) 云南省教育厅科学研究基金(2019J0005)。 

主　　题：结构洞 图最短路径增量 中介中心性 信息扩散 复杂网络 

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