ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Community detection based on structure and fitness

  • Beijing Key Lab of Traffic Data Analysis and Mining, Beijing Jiaotong University, Beijing 100044, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2014.07.004
  • Received Date: 21 March 2014
  • Accepted Date: 15 June 2014
  • Rev Recd Date: 15 June 2014
  • Publish Date: 30 July 2014
    Abstract

  • Abstract

    Many systems can be described as complex social networks, and increasing attention has been paid to the detection of social communities out of complex social networks. Structured-based community detection can be achieved locally without knowledge of the overall situation. The community fitness characteristics of social networks can help to identify community structures at different fitnesses. A new algorithm based on structure and fitness was proposed to test large generated networks and real networks. Experiments had shown its better efficiency and higher accuracy.

    Abstract

    Many systems can be described as complex social networks, and increasing attention has been paid to the detection of social communities out of complex social networks. Structured-based community detection can be achieved locally without knowledge of the overall situation. The community fitness characteristics of social networks can help to identify community structures at different fitnesses. A new algorithm based on structure and fitness was proposed to test large generated networks and real networks. Experiments had shown its better efficiency and higher accuracy.
    • FullText(HTML)
  • loading
    • References(19)
  • [1]
    汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京:清华大学出版社, 2006.
    [2]
    Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
    [3]
    Li Y D, Liu J, Liu C L. A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks[J]. Soft Computing, 2014, 18(2): 329-348.
    [4]
    Bu Z, Zhang C C, Xia Z Y, et al. A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social network[J]. Knowledge-Based Systems, 2013, 50: 246-259.
    [5]
    Shi C, Cai Y N, Fu D, et al. A link clustering based overlapping community detection algorithm[J]. Data & Knowledge Engineering, 2013, 87: 394-404.
    [6]
    Li K, Pang Y. A unified community detection algorithm in complex network[J]. Neurocomputing, 2014, 130(1): 36-43.
    [7]
    Bennetta L, Liub S S, Papageorgioub L G, et al. A mathematical programming approach to community structure detection in complex networks[C]// Proceedings of the 22nd European Symposium on Computer Aided Process Engineering. London, UK: Elsevier, 2012: 1 387-1 391.
    [8]
    Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7 821-7 826.
    [9]
    Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174.
    [10]
    Wu F, Huberman B A. Finding communities in linear time: A physics approach[J]. The European Physical Journal B, 2004, 38(2): 331-338.
    [11]
    Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133(1-5).
    [12]
    Zhou H J, Lipowsky R. Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[C]//Proceedings of the International Conference on Computational Science. Springer, 2004: 1 062-1 069.
    [13]
    Xu X W, Yuruk N, Feng Z D, et al. SCAN: A structural clustering algorithm for networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2007: 824-833.
    [14]
    Martelot E L, Hankin C. Fast multi-scale community detection based on local criteria within a multi-threaded algorithm[EB/OL]. http://arxiv.org/abs/1301.0955.
    [15]
    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(1-18).
    [16]
    Serrano M , Bogu M, Vespignani A. Extracting the multiscale backbone of complex weighted networks[J]. Proceedings of the National Academy of Sciences, 2009, 106(16): 6 483-6 488.
    [17]
    Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1): 016118(1-9).
    [18]
    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(1-20).
    [19]
    Hubert L, Arabie P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京:清华大学出版社, 2006.
    [2]
    Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
    [3]
    Li Y D, Liu J, Liu C L. A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks[J]. Soft Computing, 2014, 18(2): 329-348.
    [4]
    Bu Z, Zhang C C, Xia Z Y, et al. A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social network[J]. Knowledge-Based Systems, 2013, 50: 246-259.
    [5]
    Shi C, Cai Y N, Fu D, et al. A link clustering based overlapping community detection algorithm[J]. Data & Knowledge Engineering, 2013, 87: 394-404.
    [6]
    Li K, Pang Y. A unified community detection algorithm in complex network[J]. Neurocomputing, 2014, 130(1): 36-43.
    [7]
    Bennetta L, Liub S S, Papageorgioub L G, et al. A mathematical programming approach to community structure detection in complex networks[C]// Proceedings of the 22nd European Symposium on Computer Aided Process Engineering. London, UK: Elsevier, 2012: 1 387-1 391.
    [8]
    Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7 821-7 826.
    [9]
    Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174.
    [10]
    Wu F, Huberman B A. Finding communities in linear time: A physics approach[J]. The European Physical Journal B, 2004, 38(2): 331-338.
    [11]
    Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133(1-5).
    [12]
    Zhou H J, Lipowsky R. Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities[C]//Proceedings of the International Conference on Computational Science. Springer, 2004: 1 062-1 069.
    [13]
    Xu X W, Yuruk N, Feng Z D, et al. SCAN: A structural clustering algorithm for networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2007: 824-833.
    [14]
    Martelot E L, Hankin C. Fast multi-scale community detection based on local criteria within a multi-threaded algorithm[EB/OL]. http://arxiv.org/abs/1301.0955.
    [15]
    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(1-18).
    [16]
    Serrano M , Bogu M, Vespignani A. Extracting the multiscale backbone of complex weighted networks[J]. Proceedings of the National Academy of Sciences, 2009, 106(16): 6 483-6 488.
    [17]
    Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E, 2009, 80(1): 016118(1-9).
    [18]
    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(1-20).
    [19]
    Hubert L, Arabie P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218.
    Recommended articles
    TrendMD
    Volume 44 Issue 7 page: 563-569
    Cover

    Article Metrics

    Article views (35) PDF downloads(70)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return