Abstract
In social networks, the community detection algorithm is very important for understanding the structures and the functions of these networks. A lot of researches have been done on the overlapping community detection algorithms as the overlapping is a significant feature of such networks. However, though many algorithms have been introduced to detect overlapping communities, the detection of the overlapping community is still a challenging task. In fact, the traditional static methods which partitioned the network structure could not efficiently obtain the latest community structure. The problems of high computational complexity and low identification accuracy need to be solved. To address these issues, in this paper, we propose a New Overlapping Community Detection algorithm based on improved KNN (called NOCD), which can timely adjust the community structure based on different network changes, and ultimately obtains the results of the community partitions with a high degree of Q module. To deal with the weighted social networks, NOCD adopts similarity instead of distance to evaluate the network. The experimental results show that the proposed NOCD algorithm compared with the COPRA, the CPM, the DeCom, the PLPA, and the AI-LPA algorithms can effectively improve the detection accuracy, the efficiency of parallel computing, and reduce the time complexity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data availability statement
The LFR (Lancichinetti-Fortunato-Radicchi) model introduced in [36] is the most widely used synthetic benchmark for the comparison of community detection algorithms.
References
Ahn YY, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466(7307):761–764
Ball B, Karrer B, Newman ME (2011) Efficient and principled method for detecting communities in networks. Phys Rev E 84(3):036103
Bhatia V, Rani R (2019) A distributed overlapping community detection model for large graphs using autoencoder. Fut Gen Comput Syst 94:16–26
Blondel VD, Guillaume JL, Lambiotte R et al (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008
Bu Z, Wu Z, Cao J et al (2015) Local community mining on distributed and dynamic networks from a multiagent perspective. IEEE Trans Cybern 46(4):986–999
Clauset A (2005) Finding local community structure in networks. Phys Rev E 72(2):026132
Coscia M, Rossetti G, Giannotti F, et al (2012) Demon: a local-first discovery method for overlapping communities. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 615–623
El Kouni IB, Karoui W, Romdhane LB (2020) Node importance based label propagation algorithm for overlapping community detection in networks. Expert Syst Appl 162(113):020
Farkas I, Abel D, Palla G et al (2007) Weighted ´ network modules. New J Phys 9(6):180
Gao Y, Yu X, Zhang H (2021) Overlapping community detection by constrained personalized pagerank. Expert Syst Appl 173(114):682
Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826
Gleiser PM, Danon L (2003) Community structure in jazz. Adv Complex Syst 6(04):565–573
Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phy 12(10):103018
Guimera R, Danon L, Diaz-Guilera A et al (2003) Self-similar community structure in a network of human interactions. Phys Rev E 68(6):065103
Jeh G, Widom J (2002) Simrank: a measure of structural-context similarity. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp 538–543
Jiang JQ, Dress AW, Yang G (2009) A spectral clustering-based framework for detecting community structures in complex networks. Appl Math Lett 22(9):1479–1482
Khorasgani RR, Chen J, Zaiane OR (2010) Top leaders community detection approach in information networks. In: 4th SNA-KDD workshop on social network mining and analysis, Citeseer
Kim Y, Jeong H (2011) Map equation for link communities. Phys Rev E 84(2):026110
Kumpula JM, Kivela M, Kaski K et al (2008) Sequential algorithm for fast clique percolation. Phys Rev E 78(2):026109
Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110
Lancichinetti A, Fortunato S, Kertesz J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015
Lancichinetti A, Radicchi F, Ramasco JJ et al (2011) Finding statistically significant communities in networks. PloS One 6(4):e18961
Lee J, Gross SP, Lee J (2012) Modularity optimization by conformational space annealing. Phys Rev E 85(5):056702
Li X, Hu Z, Wang H (2018) Combining nonnegative matrix factorization and sparse coding for functional brain overlapping community detection. Cogn Comput 10(6):991–1005
Liu Z, Xiang B, Guo W et al (2019) Overlapping community detection algorithm based on coarsening and local overlapping modularity. IEEE Access 7:57943–57955
Lusseau D, Schneider K, Boisseau OJ et al (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav Ecol Sociobiol 54(4):396–405
Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113
Nicosia V, Mangioni G, Carchiolo V et al (2009) Extending the definition of modularity to directed graphs with overlapping communities. J Stat Mech Theory Exp 2009(03):P03024
Palla G, Derenyi I, Farkas I et al (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818
Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106
Ramesh A, Srivatsun G (2021) Evolutionary algorithm for overlapping community detection using a merged maximal cliques representation scheme. Appl Soft Comput 112(107):746
Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105(4):1118–1123
Sathyakala M, Sangeetha M (2021) A weak clique based multi objective genetic algorithm for overlapping community detection in complex networks. J Ambient Intell Humaniz Comput 12(6):6761–6771
Shang R, Bai J, Jiao L et al (2013) Community detection based on modularity and an improved genetic algorithm. Phys A 392(5):1215–1231
Shen HW, Cheng XQ (2010) Spectral methods for the detection of network community structure: a comparative analysis. J Stat Mech Theory Exp 10:P10020
Shen H, Cheng X, Cai K et al (2009) Detect overlapping and hierarchical community structure in networks. Phys A 388(8):1706–1712
Sheng J, Wang K, Sun Z et al (2019) Overlapping community detection via preferential learning model. Phys A 527(121):265
Subelj L, Bajec M (2011) Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction. Phys Rev E 83(3):036103
Van Lierde H, Chow TW, Chen G (2019) Scalable spectral clustering for overlapping community detection in large-scale networks. IEEE Trans Knowl Data Eng 32(4):754–767
Wang Y, Bu Z, Yang H et al (2021) An effective and scalable overlapping community detection approach: integrating social identity model and game theory. Appl Math Comput 390(125):601
Wu ZH, Lin YF, Gregory S et al (2012) Balanced multi-label propagation for overlapping community detection in social networks. J Comput Sci Technol 27(3):468–479
Xie J, Szymanski BK (2012) Towards linear time overlapping community detection in social networks. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp 25–36
Xu M, Li Y, Li R et al (2019) Eadp: an extended adaptive density peaks clustering for overlapping community detection in social networks. Neurocomputing 337:287–302
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473
Acknowledgements
The authors would like to thank the anonymous reviewers for their comments which helped them in improving the quality of the paper. This paper is supported by the Key Scientific and Technological Research Projects in Henan Province (Grand No. 192102210125) and Open Foundation of State key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications) (SKLNST-2020-2-01) .
Funding
The funding has been received from Key Scientific and Technological Research Projects in Henan Province with Grant no. 192102210125; Open Foundation of State key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications) with Grant no. SKLNST-2020-2-01.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors of the paper certify that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Dong, S., Sarem, M. NOCD: a new overlapping community detection algorithm based on improved KNN. J Ambient Intell Human Comput 13, 3053–3063 (2022). https://doi.org/10.1007/s12652-022-03774-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12652-022-03774-4