• Computer Network and Internet • Previous Articles     Next Articles

Community Detection in Complex Networks

Nan Du, Bai Wang, and Bin Wu   

  1. Key Laboratory of Intelligent Telecommunications Software and Multimedia\, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2007-05-09 Revised:2008-02-01 Online:2008-07-10 Published:2008-07-10

With the rapidly growing evidence that various systems in nature and society can be modeled as complex networks, community detection in networks becomes a hot research topic in physics, sociology, computer society, etc. Although this investigation of community structures has motivated many diverse algorithms, most of them are unsuitable when dealing with large networks due to their computational cost. In this paper, we present a faster algorithm {ComTector,} which is more efficient for the community detection in large complex networks based on the nature of overlapping cliques. This algorithm does not require any priori knowledge about the number or the original division of the communities. With respect to practical applications, {ComTector} is challenging with five different types of networks including the classic {Zachary Karate Club}, {Scientific Collaboration Network}, {South Florida Free Word Association Network}, {Urban Traffic Network}, {North America Power Grid} and the {Telecommunication Call Network}. Experimental results show that our algorithm can discover meaningful communities that meet both the objective basis and our intuitions.

Key words: model checking; duration calculus; real-time system;


[1] Watts D J, Strogatz S H. Collective dynamics of ``small-world'' networks. {\it Nature}, 393(6684): 440--442.
[2]} Watts D J. Small Worlds: The Dynamics of Networks Between Order and Randomness. Levin S A, Strogatz S H (eds.), Princeton: Princeton University Press, 1999.
[3]} Boccaletti S, Latora V, Moreno Y. Complex networks: Structure and dynamics. {\it Physics Reports}, 424(4/5): 175--308.
[4]} Newman M E J. The structure and function of complex networks. {\it SIAM Review}, 45(2): 167--256.
[5]} Wasserman S, Faust K. Social Network Analysis. Cambridge: Cambridge University Press, 1994.
[6]} Scott J. Social Network Analysis: A Handbook. London: Sage Publications, 2002.
[7]}Milo R, Itzkovitz S {\it et al}. Network motifs: Simple building blocks of complex networks. {\it Science}, 298(5594): 824--827.
[8]} Newman M E J. Modularity and community structure in networks. {\it PNAS}, 103(23): 8577.
[9]} Girvan M, Newman M E J. Community structure in social and biological networks. {\it PNAS}, 99(12): 7821--7826.
[10]} Duch J, Arenas A. Community detection in complex networks using extremal optimization. {\it Physical Review E}, 72(2): 027104.
[11]}Palla G, Dernyi I, Farkas I. Uncovering the overlapping community structure of complex network in nature and society. {\it Nature}, 435(7043): 814--818.
[12]} Fiedler M. Algebraic connectivity of graphs. {\it Czechoslovak Mathematical Journal}, 23(98): 298--305.
[13]} Pothen A, Simon H, Liou K-P. Partitioning sparse matrices with eigenvectors of graphs. {\it SIAM J Matrix Anal App.}, 11(33): 430--452.
[14]}Kernighan B W, Lin S. A efficient heuristic procedure for partitioning graphs. {\it Bell System Technical Journal}, 49(2): 291--307.
[15]} Newman M E J. Detecting community structure in networks. {\it Eur. Phys. J. B}, 38(2): 321--330.
[16]} Bron C, Kerbosch J. Finding all cliques of an undirected graph. {\it Communications of the ACM }, 16(9): 575--577.
[17]} Du N, Wu B, Wang B \it et al. \rm A parallel algorithm for enumerating all maximal cliques in complex networks. In {\it Proc. The 6th ICDM2006 Workshop}, Hong Kong, 2006, pp.320--324.
[18]} Wu B, Pei X \it et al. \rm A parallel algorithm for enumerating all the maximal $k$-plexes. In {\it Proc. PAKDD07 Workshops}, Nanjing, 2007, pp.476--483.
[19]} Abello J, Resende M G C, Sudarsky S \it et al. \rm Massive quasi-clique detection. In {\it Proc. the 5th Latin American Symposium on Theoretical Informatics}, Mexico, 2002, pp.598--612.
[20]} Pei J, Jiang D X, Zhang A D \it et al. \rm On mining cross-graph quasi-cliques. In {\it Proc. The 12th ACM SIGKDD}, Philadelphia, 2006, pp.228--237.
[21]} Zeng Z, Wang J, Karypis G \it et al. \rm Coherent closed quasi-clique discovery from large dense graph databases. In {\it Proc. The 12th ACM SIGKDD}, Philadelphia, 2006, pp.797--802.
[22]}Han J W, Kamber M. Data Mining: Concepts and Techniques. 2nd Edition, Morgan Kaufmann Publishers, 2006.
[23]}Luca Donetti, Miguel A. Munoz detecting network communities: A new systematic and efficient algorithm. {\it Electric} {\it Journal of Statistical Mechanics}, doi:10.1088/1742-5468/2004/10/P10012, http://www. iop.org/EJ/abstract/1742-5468/2004/10/P10012.
[24]} Girvan M, Newman M E J. Finding and evaluating community structure in networks. {\it Physical Review E}, 69(2): 026113.
[25]} Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. {\it PNAS}, 101(9): 2658--2663.
[26]} Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. {\it Physical Review E}, 70(6): 066111.
[27]} Pons P, Latapy M. \rm Computing communities in large networks using random walks. In {\it Proc. ISCIS2005}, Istanbul, 2005, pp.284--293.
[28]} Clauset A. Finding local community structure in networks. {\it Physical Review E}, 72(2): 026132.
[29]} Yang B, Liu D Y. Force-based incremental algorithm for mining community structure in dynamic network. {\it Journal of Computer Science and Technology}, 21(3): 393--400.
[30]} Gunes I, Bingol H. Community detection in complex networks using agents. {\it Cornell University Library e-prints}, arXiv:cs/0610129v1, http://arxiv.org/abs/cs/0610129v1.
[31]} Fortunato S, Barthelemy M. Resolution limit in community detection. {\it PNAS}, 2007, 104(1): 36--41.
[32]} http://w3.usf.edu/FreeAssociation/.
[1] Einollah Pira. Using Markov Chain Based Estimation of Distribution Algorithm for Model-Based Safety Analysis of Graph Transformation [J]. Journal of Computer Science and Technology, 2021, 36(4): 839-855.
[2] Wan-Wei Liu, Fu Song, Tang-Hao-Ran Zhang, Ji Wang. Verifying ReLU Neural Networks from a Model Checking Perspective [J]. Journal of Computer Science and Technology, 2020, 35(6): 1365-1381.
[3] Hoon Park, Anping He, Marly Roncken, Xiaoyu Song, Ivan Sutherland. Modular Timing Constraints for Delay-Insensitive Systems [J]. , 2016, 31(1): 77-106.
[4] Yang Liu, Xuan-Dong Li, Yan Ma. A Game-Based Approach for PCTL* Stochastic Model Checking with Evidence [J]. , 2016, 31(1): 198-216.
[5] Yang Liu, Huai-Kou Miao, Hong-Wei Zeng, Yan Ma, and Pan Liu. Nondeterministic Probabilistic Petri Net — A New Method to Study Qualitative and Quantitative Behaviors of System [J]. , 2013, 28(1): 203-216.
[6] Seong Woo Kwak and Jung-Min Yang. Optimal Checkpoint Placement on Real-Time Tasks with Harmonic Periods [J]. , 2012, 27(1): 105-112.
[7] Sa'ed Abed, Member, ACM, IEEE, Yassine Mokhtari, Otmane Ait-Mohamed, Member, ACM, IEEE, and Sofiène Tahar, Senior Member, IEEE, Member, ACM. NuMDG: A New Tool for Multiway Decision Graphs Construction [J]. , 2011, 26(1): 139-152.
[8] Dian-Xiang Xu, Senior Member, IEEE, Omar El-Ariss, Wei-Feng Xu, Senior Member, IEEE, and Lin-Zhang Wang, Member, CCF, ACM, IEEE. Aspect-Oriented Modeling and Verification with Finite State Machines [J]. , 2009, 24(5): 949-961.
[9] Hai-Bin Zhang and Zhen-Hua Duan, Senior Member, CCF, IEEE. Symbolic Algorithmic Analysis of Rectangular Hybrid Systems [J]. , 2009, 24(3): 534-543.
[10] Patrick H. S. Brito, Rogerio de Lemos, Cecilia M. F. Rubira, and Eliane Martins. Architecting Fault Tolerance with Exception Handling: Verification and Validation [J]. , 2009, 24(2): 212-237.
[11] Liang Xu, Wei Chen, Yan-Yan Xu, and Wen-Hui Zhang. Improved Bounded Model Checking for the Universal Fragment of CTL [J]. , 2009, 24(1 ): 96-109 .
[12] Yong Liao, Xu-Dong Chen, Guang-Ze Xiong, Qing-Xin Zhu, and Nan Sang. End-to-End Utilization Control for Aperiodic Tasks in Distributed Real-Time Systems [J]. , 2007, 22(1): 135-146 .
[13] Zhi-Hong Tao, Cong-Hua Zhou, Zhong Chen, and Li-Fu Wang. Bounded Model Checking of CTL^* [J]. , 2007, 22(1): 39-43 .
[14] Zhi-Hong Tao, Hans Kleine Büning, and Li-Fu Wang. Direct Model Checking Matrix Algorithm [J]. , 2006, 21(6): 944-949 .
[15] Hong Pan, Hui-Min Lin, and Yi Lv. Model Checking Data Consistency for Cache Coherence Protocols [J]. , 2006, 21(5): 765-775 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhang Zhongyun; Li Guojie;. Optimal Partitioning and Granularity of Uniform Task Graphs[J]. , 1991, 6(2): 185 -194 .
[2] Fei Xianglin; Liao Lei; Wang Hezhen; Wang Chengzao;. Structured Development Environment Based on the Object-Oriented Concepts[J]. , 1992, 7(3): 193 -201 .
[3] Chen Ke; Masumi Ishikawa;. A Parallel Voting Scheme for Aspect Recovery[J]. , 1995, 10(5): 385 -402 .
[4] Heng Li, Jin-Song Liu, Zhao Xu et al.. Test Data Sets and Evaluation of Gene Prediction Programs on the Rice Genome[J]. , 2005, 20(4): 446 -453 .
[5] Yohan D. Fougerolle, Andrei Gribok, Sebti Foufou, Frederic Truchetet, and Mongi A. Abidi. Radial Supershapes for Solid Modeling[J]. , 2006, 21(2): 238 -243 .
[6] Ian Foster. Globus Toolkit Version 4: Software for Service-Oriented Systems[J]. , 2006, 21(4): 513 -520 .
[7] Hong-Ding Wang, Yun-Hai Tong, Shao-Hua Tan, Shi-Wei Tang, Dong-Qing Yang, and Guo-Hui Sun. An Adaptive Approach to Schema Classification for Data Warehouse Modeling[J]. , 2007, 22(2): 252 -260 .
[8] Gang Xu and Guo-Zhao Wang. AHT Bézier Curves and NUAHT B-Spline Curves[J]. , 2007, 22(4): 597 -607 .
[9] Xin-De Li, Member, IEEE, Florentin Smarandache, Jean Dezert, and Xian-Zhong Dai. Combination of Qualitative Information with 2-Tuple Linguistic Representation in DSmT[J]. , 2009, 24(4): 786 -797 .
[10] Lin Cong, Ruo-Feng Tong, Member, CCF, and Jin-Xiang Dong. Making Slide Shows with Zoomquilts[J]. , 2010, 25(3): 572 -582 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved