We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 26 Issue 5
September  2011
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Chuan Shi, Zhen-Yu Yan, Xin Pan, Ya-Nan Cai, Bin Wu. A Posteriori Approach for Community Detection[J]. Journal of Computer Science and Technology, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
Citation: Chuan Shi, Zhen-Yu Yan, Xin Pan, Ya-Nan Cai, Bin Wu. A Posteriori Approach for Community Detection[J]. Journal of Computer Science and Technology, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
shu

A Posteriori Approach for Community Detection

  • 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.

Funds: 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.
More Information
  • Author Bio:

    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.

  • Received Date: October 04, 2010
  • Revised Date: June 27, 2011
  • Published Date: September 04, 2011
    Abstract
  • 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.
    • FullText(HTML)
    • References (33)
  • [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.
    • Relative Articles

  • Related Articles

    [1]Yu-Xin Ma, Jia-Yi Xu, Di-Chao Peng, Ting Zhang, Cheng-Zhe Jin, Hua-Min Qu, Wei Chen, Qun-Sheng Peng. A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks[J]. Journal of Computer Science and Technology, 2013, 28(5): 797-809. DOI: 10.1007/s11390-013-1378-5
    [2]Najwa Altwaijry, Mohamed El Bachir Menai. Data Structures in Multi-Objective Evolutionary Algorithms[J]. Journal of Computer Science and Technology, 2012, 27(6): 1197-1210. DOI: 10.1007/s11390-012-1296-y
    [3]Zhi-Hao Wu, You-Fang Lin, Steve Gregory, Huai-Yu Wan, Student, Sheng-Feng Tian. Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J]. Journal of Computer Science and Technology, 2012, 27(3): 468-479. DOI: 10.1007/s11390-012-1236-x
    [4]Mao-Guo Gong, Ling-Jun Zhang, Jing-Jing Ma, Li-Cheng Jiao. Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467. DOI: 10.1007/s11390-012-1235-y
    [5]Seong Woo Kwak, Kwan-Ho You, Jung-Min Yang. Checkpoint Management with Double Modular Redundancy Based on the Probability of Task Completion[J]. Journal of Computer Science and Technology, 2012, (2): 273-280. DOI: 10.1007/s11390-012-1222-3
    [6]Nan Du, Bai Wang, Bin Wu. Community Detection in Complex Networks[J]. Journal of Computer Science and Technology, 2008, 23(4): 672-683.
    [7]Lam Thu Bui, Kalyanmoy Deb, Hussein A. Abbass, Daryl Essam. Interleaving Guidance in Evolutionary Multi-Objective Optimization[J]. Journal of Computer Science and Technology, 2008, 23(1): 44-63.
    [8]Bo Yang, Da-You Liu. A Heuristic Clustering Algorithm for Mining Communities in Signed Networks[J]. Journal of Computer Science and Technology, 2007, 22(2): 320-328.
    [9]Bo Yang, Da-You Liu. Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network[J]. Journal of Computer Science and Technology, 2006, 21(3): 393-400.
    [10]Jin Zhi, Hu Shouren. SCKE:Combining Logic- with Object-Oriented Paradigm[J]. Journal of Computer Science and Technology, 1993, 8(1): 38-48.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (47) PDF downloads (1755) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return