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

doi:10.19678/j.issn.1000-3428.0054340

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

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

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

云南大学 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 Jiang^a, BAO Chongming^b, WANG Chongyun^c, ZHOU Lihua^a, KONG Bing^a

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

摘要/Abstract

摘要： 结构洞通常指社交网络中处于信息扩散关键位置的节点，此类节点对社交网络舆情控制、影响力分析、信息传播等具有重要作用。为快速准确地找到社交网络中的结构洞，提出一种基于图最短路径增量的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

中图分类号:

TP391

朱江, 包崇明, 王崇云, 周丽华, 孔兵. 基于图结构特征分析的Top-k结构洞发现算法[J]. 计算机工程, 2020, 46(5): 94-101,108.

ZHU Jiang, BAO Chongming, WANG Chongyun, ZHOU Lihua, KONG Bing. Discovery Algorithm for Top-k Structure Holes Based on Graph Structure Feature Analysis[J]. Computer Engineering, 2020, 46(5): 94-101,108.

https://www.ecice06.com/CN/Y2020/V46/I5/94

图/表 12

20200513201241

20200513201245

20200513201249

20200513201254

20200513201259

20200513201305

20200513201309

20200513201313

20200513201317

20200513201321

20200513201324

20200513201329

参考文献

[1] BURT R S.Structural holes:the social structure of competition[M].Cambridge,USA:Harvard University Press,2009.
[2] HE Lifang,LU Chunta,MA Jiaqi,et al.Joint community and structural hole spanner detection via harmonic modularity[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2016:875-884.
[3] LIU Dayou,JIN Di,HE Dongxiao,et al.Community mining in complex networks[J].Journal of Computer Research and Development,2013,50(10):2140-2154.(in Chinese)刘大有,金弟,何东晓,等.复杂网络社区挖掘综述[J].计算机研究与发展,2013,50(10):2140-2154.
[4] XU W,LIANG W,YU J X,et al.Efficient algorithms for the identification of top-k structure holes spanners in large social networks[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(5):1017-1030.
[5] WANG Deguang,ZHOU Zhigang,LIANG Xu.Analysis of PageRank algorithm and its improvement[J].Computer Engineering,2010,36(22):291-292.(in Chinese)王德广,周志刚,梁旭.PageRank算法的分析及其改进[J].计算机工程,2010,36(22):291-292.
[6] NEWMAN M E.A measure of betweenness centrality based on random walks[J].Social Networks,2005,27(1):39-54.
[7] BRANDES U.A faster algorithm for betweenness centrality [J].Journal of Mathematical Sociology,2001,25(2):163-177.
[8] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks,1979,1(3):215-239.
[9] ROCHAT Y.Closeness centrality extended to unconnected graphs:the harmonic centrality index[EB/OL].[2019-01-16].http://pdfs.semanticscholar.org/a4ea/7b92421415674c6ed954914f0512935d0dfb.pdf.
[10] HAN Zhongming,WU Yang,TAN Xusheng,et al.Ranking key nodes in complex networks by considering structural holes[J].Acta Physica Sinica,2015,64(5):421-429.(in Chinese)韩忠明,吴杨,谭旭升,等.面向结构洞的复杂网络关键节点排序[J].物理学报,2015,64(5):421-429.
[11] CHEN Chuanyin.Research on key algorithms of complex network analysis based on cloud computing platform[D].Chendu:University of Electronic Science and Technology of China,2014.(in Chinese)陈传银.基于云计算平台的复杂网络分析关键算法研究[D].成都:电子科技大学,2014.
[12] REZVANI M,LIANG W,XU W,et al.Identifying top-k structure holes spanners in large-scale social networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Management.New York,USA:ACM Press,2015:263-272.
[13] LIU Shichao,ZHU Fuxi,FENG Xi.Identifying overlapping communities and structural holes between communities in complex networks[J].Acta Electronica Sinica,2016,44(11):2600-2606.(in Chinese)刘世超,朱福喜,冯曦.复杂网络的重叠及社区间的结构洞识别[J].电子学报,2016,44(11):2600-2606.
[14] FENG Jian,DING Yuanyuan.A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree[J].Computer Engineering and Science,2016,38(5):898-904.(in Chinese)冯健,丁媛媛.基于重叠社区和结构洞度的社会网络结构洞识别算法[J].计算机工程与科学,2016,38(5):898-904.
[15] SU Xiaoping,SONG Yurong.Leveraging neighborhood "structural holes" to identifying key spreaders in social networks[J].Acta Physica Sinica,2015,64(2):1-11.(in Chinese)苏晓萍,宋玉蓉.利用邻域"结构洞"寻找社会网络中最具影响力节点[J].物理学报,2015,64(2):1-11.
[16] GIRVAN M,NEWMAN M E.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[17] QIN Qiong,WANG Dongxia,WANG Jingchun.Evaluationg method for node importance in complex networks based on eccentricity of node[J].Journal of Qufu Normal University(Natural Science),2016,42(2):35-38.(in Chinese)秦琼,王东霞,王景春.基于节点离心率的复杂网络节点重要性评价方法[J].曲阜师范大学学报(自然科学版),2016,42(2):35-38.
[18] ZHANG Ke,ZHAO Haixing,LI Faxu,et al.A kind of deterministic small-world networks model and analysis of their characteristics[J].Computer Science and Application,2014,4(2):27-31.(in Chinese)张科,赵海兴,李发旭,等.一类确定性小世界网络模型及特性分析[J].计算机科学与应用,2014,4(2):27-31.
[19] ZANETTE D H.Criticality behavior of propagation on small-world networks[J].Physical Review E,2001,64(5):1-5
[20] JARVELIN K,KEKÄLÄINEN J.IR evaluation methods for retrieving highly relevant documents[C]//Proceedings of the 23th ACM SIGIR International Conference Research and Development in Information Retrieval.New York,USA:ACM Press,2000:41-48.
[21] LANCICHINETTI A,FORTUNATO S,RADICHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):96-110.
[22] ZHANG Fang,SI Guangya,LUO Pi.A survey for rumor propagation models[J].Complex Systems and Complexity Science,2009,6(4):1-11.(in Chinese)张芳,司光亚,罗批.谣言传播模型研究综述[J].复杂系统与复杂性科学,2009,6(4):1-11.
[23] HAVELIWALA T H.Topic-sensitive PageRank:a context-sensitive ranking algorithm for Web search[J].IEEE Transactions on Knowledge & Data Engineering,2007,15(4):784-796.
[24] LANCICHINETTI A,FORTUNATO S.Community detection algorithms:a comparative analysis[J].Physical Review E,2009,80(5):101-117.

选择文件类型/文献管理软件名称

选择包含的内容

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

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

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘宇航, 尹小庆, 林云. 基于网络资源流量的链路预测方法[J]. 计算机工程, 2022, 48(9): 78-88.
[2]	吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.
[3]	曾茜, 韩华, 马媛媛. 基于模体的朴素贝叶斯链路预测方法[J]. 计算机工程, 2022, 48(10): 95-102.
[4]	刘迪洋, 张震, 张进. 基于社区结构的复杂网络鲁棒性优化策略[J]. 计算机工程, 2021, 47(8): 84-92.
[5]	王帅, 宋玉蓉, 宋波. 考虑个体警觉行为的双层网络流行病传播模型[J]. 计算机工程, 2021, 47(3): 131-138.
[6]	吕少卿, 赵雪莉, 张潘, 任新成. 一种保留社区结构信息的网络嵌入算法[J]. 计算机工程, 2021, 47(12): 122-130.
[7]	孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.
[8]	李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.
[9]	邱少明, 於涛, 杜秀丽, 陈波. 基于节点多属性相似性聚类的社团划分算法[J]. 计算机工程, 2020, 46(7): 84-90,97.
[10]	张志敏, 柴变芳, 李文斌. 基于稀疏自编码器的属性网络嵌入算法[J]. 计算机工程, 2020, 46(7): 98-103,109.
[11]	谢菁, 羿舒文, 张毅. 基于双曲空间嵌入的极小值社区划分算法[J]. 计算机工程, 2020, 46(6): 73-80.
[12]	王曙燕, 韩雪, 孙家泽. 基于风险轨迹与复杂网络的缺陷定位方法[J]. 计算机工程, 2020, 46(6): 202-208.
[13]	吴涛, 任淑霞, 张书博. 基于三角形子图的复杂网络过滤压缩算法[J]. 计算机工程, 2020, 46(5): 70-77.
[14]	孟磊, 冶忠林, 赵海兴, 杨燕琳. 超网络模型构建中优先连接方法研究[J]. 计算机工程, 2020, 46(10): 103-111.
[15]	陆圣宇, 欧锋, 黄清元, 刘宝, 路振民, 汤凌韬. 基于资源分配与偏好连接的局部路径链路预测算法[J]. 计算机工程, 2019, 45(9): 316-320.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

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

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献

相关文章 15

编辑推荐

Metrics

本文评价