有向网络重叠社区的快速划分算法

计算机科学 ›› 2014, Vol. 41 ›› Issue (Z6): 258-261.

有向网络重叠社区的快速划分算法

李莉杰,陈端兵,王冠楠

电子科技大学互联网科学中心计算机科学与工程学院成都611731;电子科技大学互联网科学中心计算机科学与工程学院成都611731;电子科技大学互联网科学中心计算机科学与工程学院成都611731

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金(60973069,90924011,60903073,60973120),华为高校合作基金(YBCB2011057)资助

Fast Algorithm for Overlapping Community Detection in Directed Networks

LI Li-jie,CHEN Duan-bing and WANG Guan-nan

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 随着社会的发展,数据量越来越大,网络规模也在迅速增长。作为一种研究网络结构的有效方法,社区划分对于深刻认识超大规模网络有重要的意义。在分析研究有向网络的非重叠社区划分算法和无向网络的重叠社区划分算法的基础上,提出了一种有向网络重叠社区划分的快速算法。算法根据节点的有向权值和归属度进行社区划分,并分析了有向权值和归属度对划分结果的影响,在此基础上得到了一组最优的有向权值和归属度参数。使用2个实际网络和1个人工构建网络对算法的性能进行了测试并与已有算法进行了对比。实验结果表明,所提出的算法能够有效地划分出有向网络中的重叠社区。

关键词: 有向网络,社区划分,模块度,重叠社区中图法分类号TP301.6文献标识码A

Abstract: With the development of the society,the scale of data and networks are increasing rapidly．As one of the effective ways of studying network structure,community detecting is a significant issue in deep understanding of large scale networks．Based on the methods of non-overlapping community detecting in directed networks and overlapping community detecting in undirected networks,an overlapping community detecting algorithm in directed networks was proposed in this paper．The basic idea of this method is to divide a network according to two parameters:directed weight and belonging degree of nodes．The influences of these parameters on partition are discussed and the optimal parameters are obtained．The performance of the proposed algorithm was tested and compared with other algorithms on two real networks and one computer-generated network．Experimental results show that the algorithm presented in this paper is rather efficient to detect overlapping communities of directed network.

Key words: Directed networks,Community detection,Modularity,Overlapping community

李莉杰,陈端兵,王冠楠. 有向网络重叠社区的快速划分算法[J]. 计算机科学, 2014, 41(Z6): 258-261. https://doi.org/

LI Li-jie,CHEN Duan-bing and WANG Guan-nan. Fast Algorithm for Overlapping Community Detection in Directed Networks[J]. Computer Science, 2014, 41(Z6): 258-261. https://doi.org/

参考文献

[1] Rosvall M,Bergstrom T C．Maps of random walks on complex networks reveal community structure[J]．Proceedings of the National Academy of Sciences of the United States of America,2008,105(4):1118-1123
[2] Kernighan B W,Lin S．An efficient heuristic procedure for partitioning graphs[J]．Bell System Technical Journal,1970,49(2):291-307
[3] Barnes E R．An Algorithm for partitioning the nodes of a graph[J]．SIAM J．Alg．Disc．Meth,1982,4(3):541-550
[4] Girvan M,Newman M E J．Community structure in social and biological networks[J]．Proceedings of the National Academy of Sciences of the United States of America,2001,99:7821-7826
[5] Leicht E A,Newman M E J．Community structure in directed networks[J]．Physical Review Letters,2008,100(11):118703
[6] Newman M E J．Modularity and community structure in net-works[J]．Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582
[7] Nicosia V,Mangioni G,Carchiolo V,et al．Extending the definition of modularity to directed graphs with overlapping communities[J]．Journal of Statistical Mechanics:Theory and Experiment,2009:1742-5468
[8] Chauhan S,Girvan M,Ott E．A network function-based definition of communities in complex networks[J]．Chaos:An Interdisciplinary Journal of Nonlinear Science,2012,22(3):033129
[9] Newman M E J．Community detection and graph partitioning[J]．Europhys.Lett.,2013,3:28003
[10] Blondel V D,Guillaume J L,Lambiotte R,et al．Fast unfolding of communities in larger networks[J]．Journal of Statistical Mechanics:Theory and Experiment,2008,10:P10008
[11] Chen D B,Shang M S,Lv Z H,et al．Detecting overlapping communities of weighted networks via a local algorithm[J]．Physica A:Statistical Mechanics and its Applications,2010,389(19):4177-4187
[12] Liu H T,Qin X,Yun H F,et al．A Community Detecting Algorithm in Directed Weighted Networks[J]． Lecture Notes in Electrical Engineering,2011,8:11-17
[13] 陈端兵,尚明生,李霞．重叠社区划分的两阶段策略[J]．计算机科学,2013,40(1):225-228
[14] Newman M E J,Girvan M．Finding and evaluating communitystructure in networks[J]．Physical Review E,2004,69(2):026113
[15] Leskovec J,Huttenlocher D,Kleinberg J．Predicting Positive and Negative Links in Online Social Networks [C]∥Proceedings of the 19th international conference on World Wide Web．ACM,2010:641-650
[16] Leskovec J,Kleinberg J,Faloutsos C．Graph evolution:Densification and shrinking diameters[J]．ACM Transactions on Knowledge Discovery from Data,2007,1(1):2
[17] Ripeanu M,Foster I,Iamnitchi A．Mapping the Gnutella Network:Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design[J].IEEE Internet Computing Journal,2002,6:50-57
[18] Holme P,Saramki J．Temporal networks[J]．Physics Reports,2012,519:97-125

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed