一种基于信息扩散的复杂网络重叠社区发现算法

J4 ›› 2016, Vol. 38 ›› Issue (04): 792-799.

一种基于信息扩散的复杂网络重叠社区发现算法

吴永亮,郑伟涛,郭芳琳,闫光辉

（兰州交通大学电子与信息工程学院，甘肃兰州 730070）

收稿日期:2015-04-28 修回日期:2015-06-18 出版日期:2016-04-25 发布日期:2016-04-25
基金资助:
国家自然科学基金（61163010,11461038）；兰州市科技计划项目（20141171）；金川公司预研基金（JCYY2013012）

An overlapping community detection algorithm in
complex networks based on information dissemination

WU Yongliang,ZHENG Weitao,GUO Fanglin,YAN Guanghui

(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

Received:2015-04-28 Revised:2015-06-18 Online:2016-04-25 Published:2016-04-25

摘要/Abstract

摘要：

社区结构可以为网络的其他分析挖掘提供中观尺度的分析视角,在大规模复杂网络的各项研究中是一项非常重要而基础的工作。社区的重叠是真实世界网络中常见的一种现象，重叠社区结构可以更准确地描述网络中真实的结构信息，因此，复杂网络重叠社区发现具有更加突出的现实意义。在综合对比分析了当前主要的重叠社区发现算法的基础上，结合信息论的相关知识，给出了一种基于信息论的社区定义，并进一步借鉴信息传播理论，从单个节点对关于某种主题的信息的掌握程度的角度出发提出了一种复杂网络重叠社区结构发现算法。基于实际数据集的相关实验表明，与传统的社区定义和社区发现算法相比，本算法发现的重叠社区从内容角度来看具有更加明确的实际意义，并且具有较低的时间复杂度。

关键词: 重叠社区发现, 社区定义, 信息论, 信息扩散

Abstract:

Community structure can provide a mediumscale analysis perspective for other analysis in the networks, and its research is fundamental and important in complex networks. In complex networks, the overlapping community structure is a more actual description of the structure of social networks. So analyzing the structure of overlapping communities has practical significance. After studying the existing overlapping community detection algorithms combined with certain knowledge of information theory, we define the concept of community from the perspective of information theory, and present an algorithm which can detect the overlapping community structure in complex networks on the basis of information dissemination theory. Experiments show that compared with the traditional definition of community and detection algorithms, the proposed algorithm has a more accurate physical meaning and a lower time complexity.

Key words: overlapping community detection;definition of community;information theory;information dissemination

吴永亮,郑伟涛,郭芳琳,闫光辉. 一种基于信息扩散的复杂网络重叠社区发现算法[J]. J4, 2016, 38(04): 792-799.

WU Yongliang,ZHENG Weitao,GUO Fanglin,YAN Guanghui. An overlapping community detection algorithm in
complex networks based on information dissemination [J]. J4, 2016, 38(04): 792-799.

参考文献［16］

［1］	Albert R,Barabasi A L.Statistical mechanics of complex networks［D］.South Bend,Indiana:University of Notre Dame,2002.
［2］	Newman M E J.The structure and function of complex networks［J］.SIAM Review,2003,45(2):167256.
［3］	Watts D J,Strogatz S H.Collective dynamics of small world networks［J］.Nature,1998,393(6684):440442.
［4］	Milgram S.The small world problem［J］.Psychology Today,1967,32(2):185195.
［5］	Barabasi A L,Albert R.Emergence of scaling in random networks［J］.Science,1999,286(5439):509512.
［6］	Barabasi A L,Albert R,Jeong H.Meanfield theory for scalefree random networks［J］.Physica A,1999,272(12):173187.
［7］	Girvan M,Newman M E J.Community structure in social and biological networks［J］.Proc of the National Academy of Sciences of the USA,2002,99(12):78217826.
［8］	Fortunato S.Community detection in graphs［J］.Physics Reports,2010,486(35):75174.
［9］	Newman M E J. Fast algorithm for detecting community structure in networks［J］.Physical Review E,2004,69(06133):15.
［10］	Xie J,Kelley S,Szymanski B K.Overlapping community detection in networks:The state of the art and comparative study［C］∥Proc of ACM Computing Surveys,2012:115123.
［11］	Palla G,Derenyi I,Farkas I,et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature,2005,435(7043):814818.
［12］	Gregory S. An algorithm to find overlapping community structure in networks［C］∥Proc of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases,2007:91102.
［13］	Gregory S.Finding overlapping communities in networks by label propagation［J］.New Journal of Physics,2010,12(10):20112024.
［14］	Zhang Junli， Chang Yanli， Shi Wen. Overview on label propagation algorithm and applications［J］.Application Research of Computers,2013,30(1):2125.(in Chinese)
［15］	Liu Dayou,Jin Di,He Dongxiao,et al.Community mining in complex networks［J］.Journal of Computer Research and Development,2013,50(10):21402154.(in Chinese)
［16］	Li Zhiying, Yang Wu, Xie Zhijun. Research on PageRank algorithm［J］.Computer Science,2011,38(10A):185188.(in Chinese)
［17］	Freeman L C.A set of measures of centrality based on betweenness［J］.Sociometry,1977,40(1):3541.
［18］	Freeman L C.Centrality in social networks:ii.Experimental Results［J］.Social Networks,1979,1(2):119141.
［19］	Freeman L C.Centrality in social networks:Conceptual clarification［J］.Social Networks,1979,1(3):215239.
［20］	Brandes U.A faster algorithm for betweenness centrality［J］. Journal of Mathematical Sociology,2001,25(2):163177.
［21］	Newman M E J.A measure of betweeness centrality based on random walks［J］.Social Networks,2005,27(1):3954.
［22］	Estrada E,RodriguezVelazquez J A.Subgraph centrality in complex networks［J］.Phys Rev E Stat Nonlin Soft Matter Phys,2005,71(5):122133.
［23］	Shen Huawei, Cheng Xueqi, Cai Kai. Detect overlapping and hierarchical community structure in networks［J］.Physical A:Statistical Mechanics and its Applications,2009,388(8):17061712.
［24］	Wang Xiaohua,Jiao Licheng,Wu Jianshe.Adjusting from disjoint to overlapping community detection of complex networks［J］.Physica A:Statistical Mechanics and its Applications,2009,388(24):50455056.
［25］	Lusseau D.The emergent properties of a dolphin social network［J］.Proceedings of the Royal Society B Biological Sciences,2003,270(suppl 2):186188.
［26］	Lee C, Reid F, Mcdaid A, et al. Detecting highly overlapping community structure by greedy clique expansion［C］∥Proc of the 4th Workshop on Social Network Mining and Analysis held in Conjunction with the International Conference on Knowledge Discovery and Data Mining,2010:1.
	附中文参考文献：
［14］	张俊丽,常艳丽,师文.标签传播算法理论及其应用研究综述［J］.计算机应用研究,2013,30(1):2125.
［15］	刘大有,金弟,何东晓,等.复杂网络社区挖掘综述［J］.计算机研究与发展,2013,50(10):21402154.
［16］	李稚楹,杨武,谢治军.PageRank算法研究综述［J］.计算机科学,2011,38(10A):185188.

[1]	苏金凤，张贵仓，汪凯. 图像差与加权核范数最小化的压缩图像融合[J]. 计算机工程与科学, 2019, 41(10): 1785-1794.
[2]	李慧，杨青泉，王慧慧. 一种基于局部扩展优化的重叠社区发现算法[J]. 计算机工程与科学, 2018, 40(12): 2258-2264.
[3]	胡学先1，刘文芬1，张启慧2. 信息安全专业信息论课程教学方法探讨[J]. 计算机工程与科学, 2016, 38(增刊): 224-227.
[4]	吴国清,莫则尧,陈虹. 基于信息理论的时间序列非线性检测方法[J]. J4, 2010, 32(7): 83-85.
[5]	喻晓锋, 秦春影. 一种改进的贝叶斯网弧定向算法研究[J]. J4, 2010, 32(3): 82-84.