[1]郑文萍,张浩杰,王杰.基于稠密子图的社区发现算法[J].智能系统学报编辑部,2016,11(3):426-432.[doi:10.11992/tis.201603045]
ZHENG Wenping,ZHANG Haojie,WANG Jie.Community detection algorithm based on dense subgraphs[J].CAAI Transactions on Intelligent Systems,2016,11(3):426-432.[doi:10.11992/tis.201603045]
点击复制
ZHENG Wenping,ZHANG Haojie,WANG Jie.Community detection algorithm based on dense subgraphs[J].CAAI Transactions on Intelligent Systems,2016,11(3):426-432.[doi:10.11992/tis.201603045]
基于稠密子图的社区发现算法
《智能系统学报》编辑部[ISSN 1673-4785/CN 23-1538/TP] 卷:
11
期数:
2016年第3期
页码:
426-432
栏目:
学术论文—机器学习
出版日期:
2016-06-25
- Title:
- Community detection algorithm based on dense subgraphs
- Keywords:
- complex network; community detection; graph clustering; soft clustering; density; core extended strategy; vertex betweenness; modularity
- 分类号:
- TP18
- 摘要:
- 基于密度的图聚类算法在社区发现中得到了广泛应用,然而由于其通过搜索网络中局部稠密子图来识别社区,使得大量结点因不能构成稠密子图而未被聚类。针对此问题,给出了一种基于稠密子图的软聚类算法(community detection based dense subgraphs,BDSG)。首先给出一种中心社区发现方法;进而定义了一种结点的社区归属度,并给出中心社区扩展策略;最终得到聚类结果。通过与CPM(clique percolation method)、k-dense算法在空手道俱乐部、海豚社交网络、大学生足球网络、电子邮件网络和合作网络等数据进行比较,表明BDSG算法在模块性指标与时间效率方面体现了良好性能, 同时中心社区扩展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚类有效性。
- Abstract:
- The density-based graph clustering algorithm has been widely used in community detection. However, because it identifies a community by searching a partially dense subgraph in the network, many nodes do not constitute a dense subgraph and are therefore difficult to cluster. In this paper, we present a soft clustering algorithm based on dense subgraphs (BDSG) for detecting communities in complex networks. First, we propose a method for detecting the central communities. Next, we define the degree of community attribution of a node, and put forward a core community extended strategy. Finally, we obtain the clustering results of a network. Compared with the clique percolation method (CPM), k-dense algorithms from Zachary’s Karate Club, the dolphin social network, the American college football network, the email network, and the collaboration network, BDSG shows considerably better performance with respect to modularity and time efficiency. In addition, the proposed core community extended strategy may improve the effectiveness of the clustering-methods-based density, such as that in CPM, k-dense algorithms, and others.
- 参考文献/References:
-
[1] FORTUNATO S. Community detection in graphs[J]. Physics reports, 2010, 486(3/4/5): 75-174.
[2] NEPUSZ T, YU Haiyuan, PACCANARO A. Detecting overlapping protein complexes in protein-protein interaction networks[J]. Nature methods, 2012, 9(5): 471-472.
[3] DEYLAMI H A, ASADPOUR M. Link prediction in social networks using hierarchical community detection[C]//Proceedings of the 7th conference on information and knowledge technology. Urmia, Iran, 2015: 1-5.
[4] SCHAEFFER S E. Graph clustering[J]. Computer science review, 2007, 1(1): 27-64.
[5] 杨博, 刘大有, LIU Jiming, 等. 复杂网络聚类方法[J]. 软件学报, 2009, 20(1): 54-66. YANG Bo, LIU Dayou, LIU Jiming, et al. Complex network clustering algorithms[J]. Journal of software, 2009, 20(1): 54-66.
[6] 冀俊忠, 刘志军, 刘红欣, 等. 蛋白质相互作用网络功能模块检测的研究综述[J]. 自动化学报, 2014, 40(4): 577-593. JI Junzhong, LIU Zhijun, LIU Hongxin, et al. An overview of research on functional module detection for protein-protein interaction networks[J]. Acta automatica sinica, 2014, 40(4): 577-593.
[7] PALLA G, BARABáSI A L, VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[8] SIDIROPOULOS A, PALLIS G, KATSAROS D, et al. Prefetching in content distribution networks via web communities identification and outsourcing[J]. World wide web, 2008, 11(1): 39-70.
[9] 陈克寒, 韩盼盼, 吴健. 基于用户聚类的异构社交网络推荐算法[J]. 计算机学报, 2013, 36(2): 349-359. CHEN Kehan, HAN Panpan, WU Jian. User clustering based social network recommendation[J]. Chinese journal of computers, 2013, 36(2): 349-359.
[10] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.
[11] NEWMAN M E J. Community detection and graph partitioning[J]. Europhysics letters, 2013, 103(2): 28003.
[12] NEWMAN M E J. Spectral methods for community detection and graph partitioning[J]. Physical review E, 2013, 88(4): 042822.
[13] LIN Chuncheng, KANG Jiarong, CHEN J Y. An integer programming approach and visual analysis for detecting hierarchical community structures in social networks[J]. Information sciences, 2015, 299: 296-311.
[14] REN Jun, WANG Jianxin, LI Min, et al. Identifying protein complexes based on density and modularity in protein-protein interaction network[J]. BMC systems biology, 2013, 7(S4): S12.
[15] LI Xiaoli, FOO C S, NG S K. Discovering protein complexes in dense reliable neighborhoods of protein interaction networks[C]//Proceedings of the computational systems bioinformatics conference. San Diego, USA, 2007, 6: 157-168.
[16] 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.
[17] SAITO K, YAMADA T, KAZAMA K. Extracting communities from complex networks by the k-dense method[J]. IEICE transactions on fundamentals of electronics, communications and computer sciences, 2008, E91-A(11): 3304-3311.
[18] SUN Penggang, GAO Lin. Fast algorithms for detecting overlapping functional modules in protein-protein interaction networks[C]//Proceedings of the IEEE computational intelligence in bioinformatics and computational biology. Nashville, TN, USA, 2009: 247-254.
[19] LIU Guimei, WONG L, CHUA H N. Complex discovery from weighted PPI networks[J]. Bioinformatics, 2009, 25(15): 1891-1897.
[20] BADER G D, HOGUE C W V. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC bioinformatics, 2003, 4(1): 2.
[21] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.
[22] CUI Yaizu, WANG Xingyuan, EUSTACE J. Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks[J]. Physica A: statistical mechanics and its applications, 2014, 416: 198-207.
[23] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452-473.
[24] 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.
[25] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical review E, 2006, 74(3): 036104.
[26] GUIMERà R, DANON L, DíAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical review E, 2003, 68(6): 065103.
[27] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical review E, 2004, 69(2): 026113.
[28] SHEN Huawei, CHENG Xueqi, CAI Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A: statistical mechanics and its applications, 2009, 388(8): 1706-1712.
- 相似文献/References:
-
[1]王 龙,伏 锋,陈小杰,等.复杂网络上的群体决策[J].智能系统学报编辑部,2008,3(2):95.
WANG Long,FU Feng,CHEN Xiao-jie,et al.Collective decision-making over complex networks[J].CAAI Transactions on Intelligent Systems,2008,3():95.
[2]夏承遗,刘忠信,陈增强,等.复杂网络上的传播动力学及其新进展[J].智能系统学报编辑部,2009,4(5):392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
XIA Cheng-yi,LIU Zhong-xin,CHEN Zeng-qiang,et al.Transmission dynamics in complex networks[J].CAAI Transactions on Intelligent Systems,2009,4():392.[doi:10.3969/j.issn.1673-4785.2009.05.002]
[3]李伟,杨晓峰,张重阳,等.复杂网络社团的投影聚类划分[J].智能系统学报编辑部,2011,6(1):57.
LI Wei,YANG Xiaofeng,ZHANG Chongyang,et al.A clustering method for community detection on complex networks[J].CAAI Transactions on Intelligent Systems,2011,6():57.
[4]孙世温,夏承遗,王莉.基于复杂网络的软件结构度量方法综述[J].智能系统学报编辑部,2011,6(3):208.
SUN Shiwen,XIA Chengyi,WANG Li.Survey of the measurement of software structures based on complex networks[J].CAAI Transactions on Intelligent Systems,2011,6():208.
[5]赵敬,夏承遗,孙世温,等.复杂网络上同时考虑感染延迟和非均匀传播的SIR模型[J].智能系统学报编辑部,2013,8(2):128.[doi:10.3969/j.issn.1673-4785.201210027]
ZHAO Jing,XIA Chengyi,SUN Shiwen,et al.A novel SIR model with infection delay and nonuniform transmission in complex networks[J].CAAI Transactions on Intelligent Systems,2013,8():128.[doi:10.3969/j.issn.1673-4785.201210027]
[6]仇建平,陈立潮,潘理虎.牵制控制下复杂网络的同步性研究[J].智能系统学报编辑部,2014,9(6):734.[doi:10.3969/j.issn.1673-4785.201311014]
QIU Jianping,CHEN Lichao,PAN Lihu.Synchronization in complex networks via pinning control[J].CAAI Transactions on Intelligent Systems,2014,9():734.[doi:10.3969/j.issn.1673-4785.201311014]
[7]刘富,姜奕含,邹青宇.复杂网络结构比对算法研究进展[J].智能系统学报编辑部,2015,10(4):508.[doi:10.3969/j.issn.1673-4785.201408006]
LIU Fu,JIANG Yihan,ZOU Qingyu.Advances in algorithms for construction alignment of complex networks research[J].CAAI Transactions on Intelligent Systems,2015,10():508.[doi:10.3969/j.issn.1673-4785.201408006]
[8]晁永翠,纪志坚,王耀威,等.复杂网络在路形拓扑结构下可控的充要条件[J].智能系统学报编辑部,2015,10(4):577.[doi:10.3969/j.issn.1673-4785.201411031]
CHAO Yongcui,JI Zhijian,WANG Yaowei,et al.Necessary and sufficient conditions for the controllability of complex networks with path topology[J].CAAI Transactions on Intelligent Systems,2015,10():577.[doi:10.3969/j.issn.1673-4785.201411031]
[9]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报编辑部,2015,10(6):949.[doi:10.11992/tis.201507042]
WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,10():949.[doi:10.11992/tis.201507042]
[10]闫玲玲,陈增强,张青.基于度和聚类系数的中国航空网络重要性节点分析[J].智能系统学报编辑部,2016,11(5):586.[doi:10.11992/tis.201601024]
YAN Lingling,CHEN Zengqiang,ZHANG Qing.Analysis of key nodes in China’s aviation network basedon the degree centrality indicator and clustering coefficient[J].CAAI Transactions on Intelligent Systems,2016,11():586.[doi:10.11992/tis.201601024]
备注/Memo
收稿日期:2016-3-19;改回日期:。
基金项目:国家自然科学基金项目(61572005,61272004),山西省煤基重点科技攻关项目(MQ2014-09).
作者简介:郑文萍,1979年生,女,副教授,中国计算机学会会员,主要研究方向为图论算法、生物信息学等。主持多项国家级项目,发表学术论文多篇。张浩杰,1991年8月生,男,硕士研究生,主要研究方向为数据挖掘、图聚类等。王杰,1988年8月生,男,博士研究生,主要研究方向为数据挖掘,生物信息学。
通讯作者:郑文萍.E-mail:wpzheng@sxu.edu.cn.
更新日期/Last Update:
1900-01-01