Abstract
Community detection is a well-observed problem in the complex network domain for the last two decades. Newman-Girvan is one of the most popular methods in this field. The algorithm is based on the repetitive deletion of edges from a complex graph with high betweenness centrality. In several real-life networks, Newman-Girvan has failed to produce desired results due to ambiguity as more than one edge can have the same betweenness centrality. Also, the average run time complexity of the said algorithm is high than expected. In this manuscript, we have modified the popular community detection technique by introducing clustering co-efficient metrics. Clustering co-efficient would introduce the neighborhood contribution and make stable communities even for a large network. The experimental results are satisfactory over the benchmark data and can be used as an alternative solution in this domain.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Muhuri S, Chakraborty S, Chakraborty SN (2018) Extracting social network and character categorization from Bengali literature. IEEE Trans Comput Soc Syst 5(2):371–381
Chowdhury T, Muhuri S, Chakraborty S, Chakraborty SN (2019) Analysis of adapted films and stories based on social network. IEEE Trans Comput Soc Syst 6(5):858–869
Muhuri S, Chakraborty S, Setua SK (2020) Differentiate the game maker in any soccer match based on social network approach. IEEE Trans Comput Soc Syst 7(6):1399–1408
Liu W, Suzumura T, Chen L, Hu G (2017) A generalized incremental bottom-up community detection framework for highly dynamic graphs. In: 2017 IEEE international conference on big data (Big Data), pp 3342–3351. https://doi.org/10.1109/BigData.2017.8258319
Newman MEJ (2004) Detecting community structure in networks. Eur Phys J B 38(2):321–330
Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69:026113. https://doi.org/10.1103/PhysRevE.69.026113
Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826. https://doi.org/10.1073/pnas.122653799
Newman MEJ (2006) Modularity and community structure in networks. Proc Natl Acad Sci USA 103(23):8577–8582
Pan Y, Li DH, Liu JG, Liang JZ (2010) Detecting community structure in complex networks via node similarity. Physica A: Stat Mech Appl 389(14):2849–2857. https://doi.org/10.1016/j.physa.2010.03.006
Piccardi C (2011) Finding and testing network communities by lumped Markov chains. PLOS ONE 6(11):1–13. https://doi.org/10.1371/journal.pone.0027028
Jin D, Yang B, Baquero C, Liu D, He D, Liu J (2011) A Markov random walk under constraint for discovering overlapping communities in complex networks. J Stat Mech 2011(05):P05031
Reichardt J, Bornholdt S (2006) Statistical mechanics of community detection. Phys Rev E 74:016110. https://doi.org/10.1103/PhysRevE.74.016110
Karrer B, Newman MEJ (2011) Stochastic blockmodels and community structure in networks. Phys Rev E 83:016107. https://doi.org/10.1103/PhysRevE.83.016107
Choudhury D, Bhattacharjee S, Das A (2013) An empirical study of community and sub-community detection in social networks applying Newman-Girvan algorithm. In: 2013 1st international conference on emerging trends and applications in computer science, pp 74–77. https://doi.org/10.1109/ICETACS.2013.6691399
Zhang XS, Wang RS, Wang Y, Wang J, Qiu Y, Wang L, Chen L (2009) Modularity optimization in community detection of complex networks. EPL (Europhys Lett) 87(3):38002. https://doi.org/10.1209/0295-5075/87/38002
Chen S, Wang ZZ, Tang L, Tang YN, Gao YY, Li HJ, Xiang J, Zhang Y (2018) Global vs local modularity for network community detection. PLoS One 13(10):e0205284
Jin D, Yu Z, Jiao P, Pan S, He D, Wu J, Yu P, Zhang W (2021) A survey of community detection approaches: from statistical modeling to deep learning. IEEE Trans Knowl Data Eng
Su X, Xue S, Liu F, Wu J, Yang J, Zhou C, Hu W, Paris C, Nepal S, Jin D, Sheng QZ, Yu PS (2022) A comprehensive survey on community detection with deep learning. IEEE Trans Neural Netw Learn Syst 1–21. https://doi.org/10.1109/TNNLS.2021.3137396
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473. https://doi.org/10.1086/jar.33.4.3629752
Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54(4):396–405. https://doi.org/10.1007/s00265-003-0651-y
Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: Theory Exp 2008(10):P10008
Yazdani M, Moeini A, Mazoochi M, Rahmani F, Rabiei L (2020) A new follow based community detection algorithm. In: 2020 6th international conference on web research (ICWR). IEEE, pp 197–202
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Muhuri, S., Vatsa, D. (2023). A Modified Newman-Girvan Technique for Community Detection. In: Khanna, A., Polkowski, Z., Castillo, O. (eds) Proceedings of Data Analytics and Management . Lecture Notes in Networks and Systems, vol 572. Springer, Singapore. https://doi.org/10.1007/978-981-19-7615-5_21
Download citation
DOI: https://doi.org/10.1007/978-981-19-7615-5_21
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-7614-8
Online ISBN: 978-981-19-7615-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)