›› 2011, Vol. 26 ›› Issue (5): 792-805.doi: 10.1007/s11390-011-0178-z

• Special Section on Community Analysis and Information Recommendation • Previous Articles     Next Articles

A Posteriori Approach for Community Detection

Chuan Shi1 (石川), Member, CCF, IEEE, Zhen-Yu Yan2 (闫震宇), Member, IEEE, Xin Pan1 (潘欣), Ya-Nan Cai1 (蔡亚男), and Bin Wu1 (吴斌), Member, CCF   

  1. 1. School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China
    2. Research Department, Fair Isaac Corporation (FICO), San Rafael, CA, 94903, U.S.A.
  • Received:2010-10-05 Revised:2011-06-28 Online:2011-09-05 Published:2011-09-05
  • Contact: Chuan Shi E-mail:shichuan@bupt.edu.cn; yan zhen yu@hotmail.com; panyx2006@qq.com; diandacainan@gmail.com; wubin@bupt.edu.cn
  • About author:Chuan Shi received the Ph.D. degree from the Institute of Computing Technology, Chinese Academic of Sciences, Beijing, in 2007. He is a member of CCF. He joined the School of Computer of Beijing University of Posts and Telecommunications as a lecturer in 2007, and is an associate professor at present. His research interests are in machine learning, data mining, and evolutionary computing. He has published more than 20 papers in refereed journals and conferences.
    Zhen-Yu Yan received the Ph.D. degree in systems engineering in 2007 from the University of Virginia, USA. He is currently a lead scientist in the Research Department at Fair Isaac Corporation (FICO). His research interests include risk analysis, multi-objective optimization and decision making, and data mining. He has published more than 20 research papers on the related areas.
    Xin Pan is an undergraduate student in Beijing University of Posts and Telecommunications. His research interests are in machine learning, data mining, and evolutionary computing.
    Ya-Nan Cai is a Master's candidate in Beijing University of Posts and Telecommunications. Her research interests are in machine learning, data mining, and evolutionary computing.
    Bin Wu received the Ph.D. degree from the Institute of Computing Technology, Chinese Academic of Sciences, Beijing, in 2002. He is a member of CCF. He joined the School of Computer of Beijing University of Posts and Telecommunications as a lecturer in 2002, and is an associate professor at present. His research interests are in data mining, complex network, and cloud computing. He has published more than 40 papers in refereed journals and conferences.
  • Supported by:

    Supported by the National Natural Science Foundation of China under Grant Nos. 60905025, 61074128, 61035003, the National High Technology Research and Development 863 Program of China under Grant No. 2009AA04Z136.

PDF

1765

Cited

3

Conventional community detection approaches in complex network are based on the optimization of a priori decision, i.e., a single quality function designed beforehand. This paper proposes a posteriori decision approach for community detection. The approach includes two phases: in the search phase, a special multi-objective evolutionary algorithm is designed to search for a set of tradeoff partitions that reveal the community structure at different scales in one run; in the decision phase, three model selection criteria and the Possibility Matrix method are proposed to aid decision makers to select the preferable solutions through differentiating the set of optimal solutions according to their qualities. The experiments in five synthetic and real social networks illustrate that, in one run, our method is able to obtain many candidate solutions, which effectively avoids the resolution limit existing in priori decision approaches. In addition, our method can discover more authentic and comprehensive community structures than those priori decision approaches.

[1] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Physics Review E, 2004, 69(2): 026113

[2] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U. Complex networks: Structure and dynamics. Physics Report, 2006, 424(4/5): 175-308.

[3] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks. Nature, 2005, 433: 895-900.

[4] Palla G, Dereyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814-818.

[5] Danon L, Diaaz-Guilera A, Duch J, Arenas A. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiments, 2005, (9): p09008.

[6] Pothen A, Sinmon H, Liou K-P. Partitioning sparse matrices with eigenvectors of graphs. SIAM J.Matrix Anal App., 1990, 11(3): 430-452.

[7] Martin R, Carl T B. An information-theoretic framework for resolving community structure in complex networks. PNAS, 2007, 104(18): 7327-7331.

[8] Fortunato S, Barthelemy M. Resolution limit in community detection. In Proc. the National Academy of Sciences, 2007, 104(1): 36-41.

[9] Reichardt J, Bornholdt S. Statistical mechanics of community detection. Physics Review E, 2006, 74(1): 016110.

[10] Arenas A, Fernandez A, Gomez A. Multiple resolution of modular structure of complex networks. arXiv:physics/0703218v 1, 2007.

[11] Kumpula J M, Saramaki J, Kaski K, Kertesz J. Limit resolution and multiresolution models in complex network community detection. arXiv:0706. 2230v2, Jan. 25, 2008.

[12] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multi-scale complexity in networks. Nature, 2010, 466: 761- 764.

[13] Hwang C L, Masud A S M. Multiple Objective Decision Making-Methods and Applications. Berlin: Springer Verlag, Germany, 1979.

[14] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. PNAS, 2004, 101(9): 2658-2663.

[15] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Physical Review E, 2004, 70(6): 06611.

[16] Brandes U, Delling D, Gaetler M et al. On modularity clustering. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(2): 172-188.

[17] Duch J, Arenas A. Community detection in complex networks using extremal optimization. arXiv:condmat/0501368, 2005.

[18] Tasgin M, Bingol H. Community detection in complex networks using genetic algorithm,. arXiv:cond-mat/0604419, 2006.

[19] Shen H, Cheng X, Fang B. Covariance, correlation matrix, and the multiscale community structure of networks. Phys. Rev. E, 82(1): 016114.

[20] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 2009, 11(3): 033015.

[21] Shen H, Cheng X, Kai C, Hu M. Detect overlapping and hierarchical community structure in networks. Physica A, 2009, 388: 1706-1712.

[22] Shen H, Cheng X, Guo J. Quantifying and identifying the overlapping community structure in networks. Journal of Statistical Mechanics: Theory and Experiment, 2009, P07042.

[23] Shi C, Wang Y, Wu B, Zhong C. A new genetic algorithm for community detection. Complex Sciences, 2009, 5(1): 1298- 1309.

[24] Pizzuti C, GA-Net: A genetic algorithm for community detection in social networks. In Proc. PPSN2008, Dortmund, Germany, Sept. 13-17, 2008, pp.1081-1090.

[25] Pizzuti C. Community detection in social networks with genetic algorithms. In Proc. GECCO2008, Alanta, USA, Jul. 12-16, 2008, pp.1137-1138.

[26] Shi C, Zhong C, Yan Z, Cai Y, Wu B. A multi-objective optimization approach for community detection in complex network. In Proc. CEC2010, Barcelona, Spain, Jul. 18-23, 2010, pp.1-8.

[27] Pizzuti C. A multi-objective genetic algorithm for community detection in networks. In Proc. ICTAI 2009, Newark, USA, Nov. 2-4, 2009, pp.379-386.

[28] Handle J, Knowles J. An evolutionary approach to multiobjective clustering. Transaction on Evolutionary Computation, 2007, 11(1): 56-76.

[29] Deb K. Multiobjective Optimization Using Evolutionary Algorithms. Wiley, UK, 2001.

[30] Deb K, Pratab A, Agarwal S, MeyArivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transaction on Evolutionary Computation, 2002, 6(2): 182-197.

[31] Shi C, Yan Z, Wang Y, Cai Y, Wu B. A genetic algorithm for detecting communities in large scale complex networks. Advances in Complex Systems, 2010, 13(1): 3-17.

[32] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4): 046110.

[33] Du N, Wang B, Wu B. Community detection in complex networks. Journal of Computer Science and Technology, 2008, 23(4): 672-683.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Shen Li; Stephen Y.H.Su;. Generalized Parallel Signature Analyzers with External Exclusive-OR Gates[J]. , 1986, 1(4): 49 -61 .
[2] Xie Li; Chen Peipei; Yang Peigen; Sun Zhongxiu;. The Design and Implementation of an OA System ZGL1[J]. , 1988, 3(1): 75 -80 .
[3] Xu Zhiming;. Discrete Interpolation Surface[J]. , 1990, 5(4): 329 -332 .
[4] Harald E. Otto;. UNDO, An Aid for Explorative Learning?[J]. , 1992, 7(3): 226 -236 .
[5] Xu Meirui; Liu Xiaolin;. A VLSI Algorithm for Calculating the Tree to Tree Distance[J]. , 1993, 8(1): 68 -76 .
[6] Zhang Bo; Zhang Ling;. On Memory Capacity of the Probabilistic Logic Neuron Network[J]. , 1993, 8(3): 62 -66 .
[7] Zhao Zhaokeng; Dai Jun; Chen Wendan;. Automated Theorem Proving in Temporal Logic:T-Resolution[J]. , 1994, 9(1): 53 -62 .
[8] Lu Bo; Cai Shijie;. A Skeleton-Based Approach of Automatically Generating Some Chinese Typefaces[J]. , 1996, 11(1): 30 -38 .
[9] WANG Jian; ZHANG Fuyan;. Multicast Address Management and Connection Control Based on Hierarchical Autonomous Structure[J]. , 1999, 14(1): 64 -73 .
[10] CHEN Haiming;. Function Definition Language FDL andIts Implementation[J]. , 1999, 14(4): 414 -421 .

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