Abstract
Community structure is an integral characteristic of real world networks whichever processes or areas they emerge from. This paper addresses the problem of community structure detection theoretically as well as computationally. The authors introduce a number of concepts such as the neighbourhood and strength of a subgraph, p-community, local maximal p-community, hubs, and outliers that play elemental role in formalising the concept of community structure in complex networks. A few preliminary results have been derived that lead to the development of an algorithm for community structure detection in undirected unweighted networks. The algorithm is based on a local seed expansion strategy that uses the concept of interaction coefficient. The authors have analysed the algorithm on a number of parameters such as accuracy, stability, and quality on synthetic and real world networks from different areas.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Qi Y and Ge H, Modularity and dynamics of cellular networks, PLOS Computational Biology, 2006, 2(12): e174.
Newman M E J, Detecting community structure in networks, Eur. Phys. J. B, 2004, 38(2): 321–330.
Newman M E J, Communities, modules and large-scale structure in networks, Nat. Phys., 2012, 8(1): 25–31.
Yang J and Leskovec J, Defining and evaluating network communities based on ground-truth, Knowl. Inf. Syst., 2013, 42(1): 181–213.
Luce R D and Perry A D, A method of matrix analysis of group structure, Psychometrika, 1949, 14(2): 95–116.
Lawler E L, Cutsets and partitions of hypergraphs, Networks, 1973, 3(3): 275–285.
Alba R D, A graphtheoretic definition of a sociometric clique, The Journal of Mathematical Sociology, 1973, 3(1): 113–126.
Mokken R J, Cliques, clubs and clans, Quality and Quantity, 1979, 13(2): 161–173.
Seidman S B, Network structure and minimum degree, Social Networks, 1983, 5(3): 269–287.
Borgatti S P, Everett M G, and Shirey P R, LS sets, lambda sets and other cohesive subsets, Social Networks, 1990, 12(4): 337–357.
Flake G W, Lawrence S, and Giles C L, Efficient identification of web communities, Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’00, New York, NY, USA, ACM, 2000, 150–160.
Radicchi F, Castellano C, Cecconi F, et al., Defining and identifying communities in networks, PNAS, 2004, 101(9): 2658–2663.
Newman M E J and Girvan M, Finding and evaluating community structure in networks, Phys. Rev. E, 2004, 69(2): 026113.
Fortunato S and Barthlemy M, Resolution limit in community detection, PNAS, 2007, 104(1): 36–41.
Traag V A, Van Dooren P, and Nesterov Y, Narrow scope for resolution-limit-free community detection, Phys. Rev. E, 2011, 84(1): 016114.
Towlson E K, Vrtes P E, Ahnert S E, et al., The rich club of the c. elegans neuronal connectome, J. Neurosci., 2013, 33(15): 6380–6387.
van den Heuvel M P and Sporns O, Network hubs in the human brain, Trends Cogn. Sci. (Regul. Ed.), 2013, 17(12): 683–696.
Sporns O, Structure and function of complex brain networks, Dialogues Clin. Neurosci., 2013, 15(3): 247–262.
Rombach P, Porter M, Fowler J, et al., Core-periphery structure in networks (revisited), SIAM Rev., 2017, 59(3): 619–646.
Sporns O and Betzel R F, Modular brain networks, Annu. Rev. Psychol., 2016, 67: 613–640.
West D B, Introduction to Graph Theory, Pearson, 2nd Edition, Prentice Hall, Inc. Upper Saddle River, NJ, 2000.
Kempe D, Kleinberg J, and Tardos E, Maximizing the spread of influence through a social network, Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’ 03, New York, NY, USA, ACM, 2003, 137–146.
Nicosia V, Mangioni G, Carchiolo V, et al., Extending the definition of modularity to directed graphs with overlapping communities, J. Stat. Mech., 2009, (3): P03024.
Kumar P and Dohare R, A neighborhood proximity based algorithm for overlapping community structure detection in weighted networks, Front. Comput. Sci., 2019, 13(6): 1353–1355.
Newman M E J, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 2006, 74(3): 036104.
Clauset A, Finding local community structure in networks, Phys. Rev. E, 2005, 72(2): 026132.
Lancichinetti A, Fortunato S, and Kertsz J, Detecting the overlapping and hierarchical community structure in complex networks, New J. Phys., 2009, 11(3): 033015.
Adamic L A and Glance N, The political blogosphere and the 2004 U.S. election: Divided they blog, Proceedings of the 3rd International Workshop on Link Discovery, LinkKDD’ 05, New York, NY, USA, ACM, 2005, 36–43. DOI: https://doi.org/10.1145/1134271.1134277.
Bu D B, Zhao Y, Cai L, et al., Topological structure analysis of the proteinprotein interaction network in budding yeast, Nucleic Acids. Res., 2003, 31(9): 2443–2450.
Leskovec J and Krevl A, SNAP Datasets: Stanford large network dataset collection, http://snap.stanford.edu/data, 2014.
Watts D J and Strogatz S H, Collective dynamics of small-world networks, Nature, 1998, 393(6684): 440–442.
Newman M E J, The structure of scientific collaboration networks, PNAS, 2001, 98(2): 404–409.
Newman M E J, Network datasets from newman, http://www-personal.umich.edu/mejn/netdata/.
Leskovec J, Lang K J, Dasgupta A, et al., Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, Internet Mathematics, 2009, 6(1): 29–123.
Cho E, Myers S A, and Leskovec J, Friendship and mobility: User movement in location-based social networks, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’ 11, New York, NY, USA, ACM, 2011, 1082–1090.
Danon L, Daz-Guilera A, Duch J, et al., Comparing community structure identification, J. Stat. Mech., 2005, (9): P09008.
Xie J R, Szymanski B K, and Liu X M, SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process, IEEE, 2011, 344–349.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper was supported by the Science and Engineering Research Board, D.S.T., Govt. of India, India under Grant No. EEQ/2016/000509.
This paper was recommended for publication by Editor DI Zengru.
Rights and permissions
About this article
Cite this article
Kumar, P., Dohare, R. Formalising and Detecting Community Structures in Real World Complex Networks. J Syst Sci Complex 34, 180–205 (2021). https://doi.org/10.1007/s11424-020-9252-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-020-9252-3