《计算机应用研究》|Application Research of Computers

基于局部扩充优化的重叠社群检测方法的改进

Improvement of overlapping community detection based on local expansion and optimization

免费全文下载 (已被下载 次)  
获取PDF全文
作者 王茜,张晨
机构 重庆大学 计算机学院,重庆 400044
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2015)04-1056-04
DOI 10.3969/j.issn.1001-3695.2015.04.023
摘要 生物信息学、社会网络、Web分析等方面的发展积累了大量的复杂网络数据信息,在对这些复杂网络进行社群检测时,往往会将一些节点归类于多个社群,目前已经提出了一些处理此类问题的算法(如LFK、GCE等),然而这类算法对局部扩充函数中参数α的选取过程复杂,无法一次性获取最优α,直接影响到了算法的可应用性。针对该缺点,提出了一种基于局部扩展的重叠社群检测的改进算法。该算法通过将α参数考虑进社群的成长过程中,使算法在保持原有速度与精度的情况下自适应地选取最优α。
关键词 数据挖掘;重叠社群检测;局部聚类
基金项目
本文URL http://www.arocmag.com/article/01-2015-04-023.html
英文标题 Improvement of overlapping community detection based on local expansion and optimization
作者英文名 WANG Qian, ZHANG Chen
机构英文名 College of Computer Science, Chongqing University, Chongqing 400044, China
英文摘要 Large amounts of complex networks data have been accumulated in the development of bioinformatics, social networks, Web analysis, etc. This paper tended to classify some of the nodes into multiple communities for some complex network community detection. Recently, scholars raised the issue of such processing algorithms (such as LFM, GCE, etc.).However, this kind of algorithm couldn’t obtain the optimal α in one time and it had a complex process while selecting parameter α in the local expansion function which directly affected the applicability of the algorithm. To get rid of the shortage, this paper presented an improved method based on local expanding to detect overlapping community. In this method, it considered α in the growth process of communities, so that it could select parameter α in an adaptive waywhile maintaining the speed and accuracy.
英文关键词 data mining; overlapping community detection; local clustering
参考文献 查看稿件参考文献
  [1] FORTUNATO S. Community detection in graphs[J] . Physics Reports, 2010, 486(3):75-174.
[2] HAN Jia-wai, KAMBER M. 数据挖掘:概念与技术[M] . 北京:机械工业出版社, 2001:300-403.
[3] XIE Jie-rui, KELLEY S, SZYMANSKI B K. Over lapping community detection in networks:the state of the art and comparative study[J] . ACM Computing Surveys, 2013, 45(4):1-37.
[4] LANCICHINETTI A, FORTUNATO S, KERTSZ J. Detecting the overlapping and hierarchical community structure in complex networks[J] . New Journal of Physics, 2009, 11(3):033015.
[5] LEE C, REID F, McDAID A, et al. Detecting highly over lapping community structure by greedy clique expansion[C] //Proc of the 4th SNA-KDD Workshop. 2010.
[6] WU Bin, YANG Sheng-qi, ZHAO Hai-zhou, et al. A distributed algorithm to enumerate all maximal cliques in MapReduce[C] //Proc of the 4th International Conference on Frontier of Computer Science and Technolgy. [S. l. ] :IEEE Press, 2009:45-51.
[7] BAUMES J, GOLDBERG M K, KRISHNAMOORTHY M S, et al. Finding communities by clustering a graph into overlapping subgraphs[C] //Proc of IADIS International Conference on Applied Computing. 2005:97-104.
[8] LEE C, REID F, McDAID A, et al. Seeding for pervasively over lapping communities[J] . Physical Review E, 2011, 83(6):066107.
[9] BRON C, KERBOSCH J. Algorithm 457:finding all cliques of an undirected graph[J] . Communications of the ACM, 1973, 16(9):575-577.
[10] CLAUSET A. Finding local community structure in networks[J] . Physical Review E, 2005, 72(2):026132.
[11] BAGROW J P, BOLLT E M. Local method for detecting communities[J] . Physical Review E, 2005, 72(4):046108.
[12] CHEN Ji-yang, ZAANE O, GOEBEL R. Local community identification in social networks[C] //Proc of International Conference on Advances in Social Network Analysis and Mining. [S. l. ] :IEEE Press, 2009:237-242.
[13] TIBLY G. Criterions for locally dense subgraphs[J] . Physica A:Statistical Mechanics and its Applications, 2012, 391(4):1831-1847.
[14] HAVEMANN F, HEINZ M, STRUCK A, et al. Identification of over lapping commuinities and their hierarchy by locally calculating community-changing resolution levels[J] . Journal of Statistical Mechanics:Theory and Experiment, 2011, 2011(1):01023.
[15] LIANG S, GUO Y. Local oriented efficient detection of over lapping communities in large networks[C] //Proc of International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. [S. l. ] :IEEE Press, 2012:31-38.
[16] LANCICHINETTI A, FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weigted graphs with over lapping communities[J] . Physical Review E, 2009, 80(1):016118.
[17] DANON L, DIAZ-GUILERA A, Duch J, et al. Comparing community structure identification[J] . Journal of Statistical Mechanics:Theory and Experiment, 2005, 2005(9):09008.
[18] COLLINS S R, KEMMEREN P, ZHAO X C, et al. Toward a comprehensive atlas of the physical interactome of Saccharomyces cerevi-siae[J] . Molecular & Cellular Proteomics, 2007, 6(3):439-450.
收稿日期 2014/3/19
修回日期 2014/4/28
页码 1056-1059,1064
中图分类号 TP391.4
文献标志码 A