基于桥系数的分裂社区检测算法研究

冀庆斌;康 茜;李德玉;王素格

PDF(4566 KB)
PDF(4566 KB)
中文信息学报 ›› 2017, Vol. 31 ›› Issue (3) : 205-212.
情感分析与社会计算

基于桥系数的分裂社区检测算法研究

  • 冀庆斌;康 茜;李德玉;王素格
作者信息 +

A Community Detection Algorithm Based on Bridgeness

  • JI Qingbin; KANG Qian; LI Deyu; WANG Suge
Author information +
History +

摘要

研究社区结构有助于揭示网络结构和功能之间的关系,而社区检测是社区结构研究的基础和核心。该文定义了一种聚集度桥系数,将其应用到社区检测中,设计出一种分裂社区检测方法,包括分裂和合并两个算法。分裂算法使用桥系数识别社区间边,通过迭代删除社区间边分解网络,从而发现网络中的社区结构;合并算法根据社区连接强度合并社区,可以揭示社区结构中的分层嵌套的现象。在六个社会网络数据集上的实验表明,本文算法可以有效的将网络分裂为有意义的社区,并且准确性接近或超过经典的社区检测算法。

Abstract

Study of community structure is of help to reveal the relationship between network structure and function, and community detection is essential to the community structure research. A bridgeness index based on clustering degree is defined in this paper, and applied to the community detection. The proposed algorithm includes two parts splitting and merging. The splitting algorithm identifies inter-community by bridgeness, and decomposes network by iterative removing inter-community edges until the community structure is discovered; The merging algorithm merges communities according to the community connection strength, so that the hierarchical nesting in community is revealed. Experiments on six social networks show that the proposed algorithm can effectively detect interesting communities for the whole network, and the accuracy is close to or even better than the classical algorithms.

关键词

社区检测 / 分裂算法 / 桥系数

Key words

community detection / divisive algorithm / bridgeness index

引用本文

导出引用
冀庆斌;康 茜;李德玉;王素格. 基于桥系数的分裂社区检测算法研究. 中文信息学报. 2017, 31(3): 205-212
JI Qingbin; KANG Qian; LI Deyu; WANG Suge. A Community Detection Algorithm Based on Bridgeness. Journal of Chinese Information Processing. 2017, 31(3): 205-212

参考文献

[1] Strogatz S H. Exploring complex networks[J]. Nature, 2001, (410): 268-276.
[2] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[3] Cheng X Q, Shen H W. Uncovering the community structure associated with the diffusion dynamics on networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2010, 33(2):147-167.
[4] 程学旗, 沈华伟. 复杂网络的社区结构[J]. 复杂系统与复杂性科学, 2011, 08(1):57-70.
[5] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5):75-174.
[6] 闵亮,邵良棚,赵永刚. 基于节点相似度的社团检测[J]. 计算机工程与应用,2015,51(9),77-81.
[7] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 264-277.
[8] Nascimento M C V. Community detection in networks via a spectral heuristic based on the clustering coefficient[J]. Discrete Applied Mathematics, 2014, 176(3):89-99.
[9] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, (435): 814-818.
[10] Karrer B, Newman M E J. Stochastic block models and community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 83(1 Pt 2):211-222.
[11] Nandini R Usha, Réka A, Soundar K. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.
[12] Sun P G, Yang Y. Methods to find community based on edge centrality[J]. Physical A Statistical Mechanics & Its Applications, 2013, 392(9):1977-1988.
[13] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, (12): 7821-7826.
[14] Sun P G, Yang Y. Methods to find community based on edge centrality[J]. Physical A Statistical Mechanics & Its Applications, 2013, 392(9):1977-1988.
[15] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automated discovery of community structure within organizations[J]. The Information Society, 2003, 21(2): 143-153.
[16] Green O, Bader D A. Faster betweenness centrality based on data structure experimentation[J]. Procedia Computer Science, 2013, 18(1):399-408.
[17] Li L, Li S H, Li H J, et al. A community divisive algorithm based on local weak edges[J]. Journal of Information & Computational Science, 2014, 11(11):3727-3737.
[18] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences, 2004, (101): 2658-2663.
[19] Cheng X Q, Ren F X, Shen H W, et al. Bridgeness: a local index on edge significance in maintaining global connectivity[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010, 2010(10): P10011.
[20] 王玙, 高琳. 动态网络桥系数增量聚类算法[J]. 西安电子科技大学学报(自然科学版), 2013, 40(1): 30-35.
[21] 胡新, 王丽珍, 何瓦特,等. 度数法求解最大团问题[J]. Journal of Frontiers of Computer Science & Technology, 2013, 7(3):262-271.
[22] Ding Z, Zhang X, Sun D, et al. Overlapping community detection based on network decomposition[J]. Scientific Reports, 2016, (6):24115.
[23] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory and Experiment. 2008, 30(2): 155-168.
[24] Fortunato S, Barthélemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[25] Lancichinetti A, Fortunato S. Limits of modularity maximization in community detection[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 84(84):2184-2188.
[26] 沈华伟, 程学旗, 陈海强, 等. 基于信息瓶颈的社区发现[J]. 计算机学报, 2008, 31(4): 677-686.
[27] Chertkov M,Chernyak V Y, Teodorescu R. Evaluating local community methods in networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 49(5): P05001.
[28] Cheng X, Ren F, Zhou S, et al. Triangular clustering in document networks[J]. New Journal of Physics, 2009, 11(3):033019.
[29] Watts D J, Strogatz S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393:440-442.
[30] Amaral L A N, Scala A, Barthélémy M, et al. Classes of small-world networks[J]. Proceedings of the National Academy of Sciences, 2000, (97): 11149-11152.
[31] Kulli V R, Warad N S. On the total closed neighbourhood graph of a graph[J]. Journal of Discrete Mathematical Sciences & Cryptography, 2001, 4(2):109-114.
[32] Newman M E J. Networks: an introduction[M]. OUP Oxford, 2010.
[33] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research. 1977, (33): 452-473.
[34] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait[J]. Behavioral Ecology and Sociobiology. 2003, 54(4): 396-405.
[35] Gleiser P M, Danon L. Community structure in jazz[J]. Advances in Complex Systems, 2003, 6(4):565-573.
[36] Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1):29-123.
[37] L Danon, A Díaz-Guilera , J Duch , et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(09):09008.

基金

国家自然科学基金(61175067, 61272095, 61432011,61573231);山西省科技基础条件平台计划项目(2015091001-0102);山西省回国留学人员科研项目(2013-014)
PDF(4566 KB)

641

Accesses

0

Citation

Detail

段落导航
相关文章

/