计算机工程

作者：朱江, 包崇明, 王崇云, 周丽华, 孔兵

单位：云南大学 a. 信息学院;b. 软件学院;c. 生态学与环境学院, 昆明 650091

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

基金：国家自然科学基金（61762090，31760152）；云南省教育厅科学研究基金（2019J0005）。

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

来源：2020年第5期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第5期