Overlapping Community Detection Algorithms: A Comparative Study

  • Authors

    • Subham Datta
    • R. Dinesh
    • Tapas Saha
    • R. Subramanian
    https://doi.org/10.14419/ijet.v7i4.6.30915
  • Overlapping Community Detection, Greedy Clique Expansion, Complex Networks, Extended Greedy Clique Expansion.

  • Abstract

    In complex networks a node may belong to many communities resulting in a highly overlapping community structure. This provides multiple information about such nodes by analyzing the communities they belong to. Recent advances in benchmarking haslead to the fact that most of the popular CAA (Community Assignment Algorithms) works only when the extent of overlap in a network is modest. GCE happens to be one such CAA with the ability to report communities in a network graph with huge accuracy. In this paper, we have discussed several existing state of art methods for detecting of overlapping communities with their approaches and disadvantages. Also we presented experimental evidence of how the extension of GCE algorithm (EGCE) outperforms the other existing overlapping community detection algorithm. At the same time we have analyzed the performances of the other existing algorithms.

     

     

  • References

    1. [1] Santo Fortunato(2010),“Community detection in graphsâ€.Physics Reports, 486(3-5),pp.75-174.

      [2] Newman, Mark EJ(2006),“Modularity and community structure in networksâ€,Proceedings of the National Academy of Sciences, 103(23),pp.8577- 8582.

      [3] JieruiXie, Stephen Kelley, and Boleslaw K Szymanski(2013),Overlapping community detection in networks: the state of the art and comparative study. Acm computing surveys (csur), 45(4), 43.

      [4] Conrad Lee, Fergal Reid, Aaron McDaid, and Neil Hurley(2010), Detecting highly overlapping community structure by greedy clique expansion. arXiv preprint arXiv:1002.1827,

      [5] Paul, M., Anand, R., & Anand, A. (2015). Detection of Highly Overlapping Communities in Complex Networks. Journal of Medical Imaging and Health Informatics,5, 1099–1103.

      [6] GergelyPalla, ImreDer´enyi, Ill´esFarkas, and Tam´asVicsek(2005),Uncovering the overlapping community structure of complex networks in nature and society. Nature,435, 814-818.

      [7] Andrea Lancichinetti, Santo Fortunato, and J´anosKert´esz (2009), Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics11, 033015.

      [8] Yong-YeolAhn, James P Bagrow, and Sune Lehmann (2010), Link communities reveal multiscale complexity in networks.Nature 466, 761-764.

      [9] Steve Gregory (2010), Finding overlapping communities in networks by label propagation. New Journal of Physics12, 103018.

      [10] Nepusz, Tamás, Haiyuan Yu, and Alberto Paccanaro 2012), Detecting overlapping protein complexes in protein-protein interaction networks. Nature methods 9, 471.

      [11] Lancichinetti A, Fortunato S.(2009), Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical ReviewE 80, 016118.

      [12] Lancichinetti A, Fortunato S, Kertész J.( 2009) Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics11, 033015.

      [13] SubhamDatta, Dinesh Karunanidy, J. Amudhavel, ThamizhSelvamDatchinamurthy, Subramanian Ramalingam (2017), A study on Identification of Static as well as Dynamic Protein Complex and Functional Modules in PPI Network. IIOAB Journal 8, 239- 251.

  • Downloads

  • How to Cite

    Datta, S., Dinesh, R., Saha, T., & Subramanian, R. (2018). Overlapping Community Detection Algorithms: A Comparative Study. International Journal of Engineering & Technology, 7(4.6), 306-313. https://doi.org/10.14419/ijet.v7i4.6.30915

    Received date: 2020-06-20

    Accepted date: 2020-06-20