[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A review of clique-based overlapping community detection algorithms

  • Survey Paper
  • Published:
Knowledge and Information Systems Aims and scope Submit manuscript

Abstract

Detection of communities is one of the prominent characteristics of vast and complex networks like social networks, collaborative networks, and web graphs. In the modern era, new users get added to these complex networks, which results in an expansion of application-generated networks. Extracting relevant information from these large networks has become one of the most prominent research areas. Community detection tries to reduce the application-generated graph into smaller communities in which nodes within the community are similar. Most of the recent proposals are focused on detecting overlapping communities in the network with higher accuracy. An integral issue in graph theory is the enumeration of cliques in a larger graph. As clique is a group of completely connected nodes which shows the explicit communities means these nodes share the same types of information. Clique-based community detection algorithm utilizing the clique property of the graph also identifies the implicit communities, which is not directly shown in the graph. Many overlapping community detection algorithms are proposed by researchers that rely on cliques. The goal of this paper is to offer a comparative analysis of clique-based community detection algorithms. This paper provides a pervasive survey on research works identifying the cliques in a network for detecting overlapping communities. We bring together most of the state-of-the-art clique-based community detection algorithms into a single article with their accessible benchmark data sets. It presents a detailed description of methods based on K-cliques, maximal cliques, and triad percolation methods and addresses these approaches’ challenges. Finally, the comparative analysis of overlapping community detection methodologies is also reported.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Ahn YY, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466(7307):761–764

    Article  Google Scholar 

  2. Ahuja M, Singh J, Neha (2015) Overlapping community detection algorithms:-a review. Int Res J Eng Technol (IRJET) 02(9)

  3. Bader GD, Hogue CW (2003) An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinf 4(1):1–27

    Article  Google Scholar 

  4. Baluja S (1994) Population-based incremental learning. a method for integrating genetic search based function optimization and competitive learning. Tech. rep., Carnegie-Mellon Univ Pittsburgh Pa Dept Of Computer Science

  5. Baluja S, Davies S (1998) Fast probabilistic modeling for combinatorial optimization. In: AAAI/IAAI Madison, WI, USA, pp 469–476

  6. Bandyopadhyay S, Chowdhary G, Sengupta D (2015) Focs: fast overlapped community search. IEEE Trans Knowl Data Eng 27(11):2974–2985

    Article  Google Scholar 

  7. Battiti R, Protasi M (1997) Reactive local search for maximum clique. In: WAE, Citeseer, pp 74–83

  8. Bosman PA, Thierens D (2000) Expanding from discrete to continuous estimation of distribution algorithms: The idea. In: International Conference on Parallel Problem Solving from Nature, Springer, pp 767–776

  9. Bron C, Kerbosch J (1973) Algorithm 457: finding all cliques of an undirected graph. Commun ACM 16(9):575–577

    Article  MATH  Google Scholar 

  10. Chamberlain BP, Levy-Kramer J, Humby C et al (2018) Real-time community detection in full social networks on a laptop. PloS one 13(1):e0188702

    Article  Google Scholar 

  11. Cheng J, Wu X, Zhou M et al (2018) A novel method for detecting new overlapping community in complex evolving networks. IEEE Trans Syst Man Cybern Syst 49(9):1832–1844

    Article  Google Scholar 

  12. Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111

    Article  Google Scholar 

  13. Cristofor D, Simovici DA (2002) Finding median partitions using information-theoretical-based genetic algorithms. J Univ Comput Sci 8(2):153–172

    MathSciNet  MATH  Google Scholar 

  14. Cui L, Hu H, Yu S et al (2018) Ddse: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. J Netw Comput Appl 103:119–130

    Article  Google Scholar 

  15. Cui Y, Wang X, Li J (2014) Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient. Phys A 405:85–91

    Article  MATH  Google Scholar 

  16. De Bacco C, Power EA, Larremore DB et al (2017) Community detection, link prediction, and layer interdependence in multilayer networks. Phys Rev E 95(4):042317

    Article  Google Scholar 

  17. De Bonet JS, Isbell CL, Viola P et al (1997) Mimic: finding optima by estimating probability densities. Adv Neural Inf Process Syst 9:424–430

    Google Scholar 

  18. Derényi I, Palla G, Vicsek T (2005) Clique percolation in random networks. Phys Rev Lett 94(16):160202

    Article  Google Scholar 

  19. Despalatović L, Vojković T, Vukicevic D (2014) Community structure in networks: Girvan-newman algorithm improvement. In 2014 37th international convention on information and communication technology. Electronics and microelectronics (MIPRO) pp 997–1002

  20. Dougnon RY, Fournier-Viger P, Lin JCW, et al (2015) More accurate inference of user profiles in online social networks. In: Mexican international conference on artificial intelligence, Springer, pp 533–546

  21. Dougnon RY, Fournier-Viger P, Lin JCW et al (2016) Inferring social network user profiles using a partial social graph. J Intell Inf Syst 47(2):313–344

    Article  Google Scholar 

  22. Dunn R, Dudbridge F, Sanderson CM (2005) The use of edge-betweenness clustering to investigate biological function in protein interaction networks. BMC Bioinf 6(1):1–14

    Article  Google Scholar 

  23. Evans TS, Lambiotte R (2009) Line graphs, link partitions, and overlapping communities. Phys Rev E 80(1):016105

    Article  Google Scholar 

  24. Everett MG, Borgatti SP (1998) Analyzing clique overlap. Connections 21(1):49–61

    Google Scholar 

  25. Fagnan J, Zaïane O, Barbosa D (2014) Using triads to identify local community structure in social networks. In: 2014 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2014), IEEE, pp 108–112

  26. Filkov V, Skiena S (2004) Heterogeneous data integration with the consensus clustering formalism. In: international workshop on data integration in the life sciences, Springer, pp 110–123

  27. Fred AL, Jain AK (2005) Combining multiple clusterings using evidence accumulation. IEEE Trans Pattern Anal Mach Intell 27(6):835–850

    Article  Google Scholar 

  28. Gasparetti F, Sansonetti G, Micarelli A (2021) Community detection in social recommender systems: a survey. Appl Intell 51(6):3975–3995

    Article  Google Scholar 

  29. Ghosh S, Halappanavar M, Tumeo A, et al (2018) Distributed louvain algorithm for graph community detection. In: 2018 IEEE international parallel and distributed processing symposium (IPDPS), IEEE, pp 885–895

  30. Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8(1):156–166

    Article  Google Scholar 

  31. Gong M, Yan J, Shen B et al (2016) Influence maximization in social networks based on discrete particle swarm optimization. Inf Sci 367:600–614

    Article  Google Scholar 

  32. Greene D (2010) D. l. doyle, and p. cunningham, tracking the evolution of communities in dynamic social networks, advances in social networks analysis and mining (asonam). In: 2010 international conference on, IEEE, pp 176–183

  33. Gregory S (2010) Finding overlapping communities in networks by label propagation. New J Phys 12(10):103018

    Article  MATH  Google Scholar 

  34. Guo Z, Yu K, Li Y, et al (2021) Deep learning-embedded social internet of things for ambiguity-aware social recommendations. IEEE Trans Netw Sci Eng

  35. Gupta S, Singh DP (2020) Recent trends on community detection algorithms: a survey. Modern Phys Lett B 34(35):2050408

    Article  MathSciNet  Google Scholar 

  36. Hoffmann T, Peel L, Lambiotte R, et al (2020) Community detection in networks with unobserved edges. Sci Adv 6(4)

  37. Hore P, Hall LO, Goldgof DB (2009) A scalable framework for cluster ensembles. Pattern Recogn 42(5):676–688

    Article  MATH  Google Scholar 

  38. Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp 137–146

  39. King AD, Pržulj N, Jurisica I (2004) Protein complex prediction via cost-based clustering. Bioinformatics 20(17):3013–3020

    Article  Google Scholar 

  40. Konc J, Janezic D (2007) An improved branch and bound algorithm for the maximum clique problem. Proteins 4(5)

  41. Kumpula JM, Kivelä M, Kaski K et al (2008) Sequential algorithm for fast clique percolation. Phys Rev E 78(2):026109

    Article  Google Scholar 

  42. Kundu S, Murthy C, Pal SK (2011) A new centrality measure for influence maximization in social networks. In: international conference on pattern recognition and machine intelligence, Springer, pp 242–247

  43. Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110

    Article  Google Scholar 

  44. Lancichinetti A, Fortunato S, Kertész J (2009) Detecting the overlapping and hierarchical community structure in complex networks. New J Phys 11(3):033015

    Article  Google Scholar 

  45. Lancichinetti A, Radicchi F, Ramasco JJ et al (2011) Finding statistically significant communities in networks. PloS one 6(4):e18961

    Article  Google Scholar 

  46. Larrañaga P, Lozano JA (2001) Estimation of distribution algorithms: a new tool for evolutionary computation, vol 2. Springer, Cham

    MATH  Google Scholar 

  47. Lee C, Reid F, McDaid A, et al (2010) Detecting highly overlapping community structure by greedy clique expansion. arXiv preprint arXiv:1002.1827

  48. Lee G, Peng SL, Kuo SW, et al (2012) Mining frequent maximal cliques efficiently by global view graph. In: 2012 9th international conference on fuzzy systems and knowledge discovery, IEEE, pp 1362–1366

  49. Li H, Zhang R, Zhao Z et al (2019) An efficient influence maximization algorithm based on clique in social networks. IEEE Access 7:141083–141093

    Article  Google Scholar 

  50. Li J, Wang X, Cui Y (2014) Uncovering the overlapping community structure of complex networks by maximal cliques. Phys A 415:398–406

    Article  MathSciNet  MATH  Google Scholar 

  51. Lu L, Gu Y, Grossman R (2010) dmaximalcliques: a distributed algorithm for enumerating all maximal cliques and maximal clique distribution. In: 2010 IEEE international conference on data mining workshops, IEEE, pp 1320–1327

  52. Lu Z, Wahlström J, Nehorai A (2018) Community detection in complex networks via clique conductance. Sci Rep 8(1):1–16

    Google Scholar 

  53. Ma J, Fan J (2019) Local optimization for clique-based overlapping community detection in complex networks. IEEE Access 8:5091–5103

    Article  Google Scholar 

  54. Maity S (2014) Detection of overlapping communities in social network. PhD thesis

  55. Maity S, Rath SK (2014) Extended clique percolation method to detect overlapping community structure. 2014 international conference on advances in computing. Communications and informatics (ICACCI), IEEE, pp 31–37

  56. Marchiori E (1998) A simple heuristic based genetic algorithm for the maximum clique problem. In: symposium on applied computing: proceedings of the 1998 ACM symposium on applied computing, Citeseer, pp 366–373

  57. Mimaroglu S, Yagci M (2012) Clicom: cliques for combining multiple clusterings. Expert Syst Appl 39(2):1889–1901

    Article  Google Scholar 

  58. Mohammadi M, Nikanjam A, Rahmani A (2008) An evolutionary approach to clustering ensemble. In: 2008 fourth international conference on natural computation, IEEE, pp 77–82

  59. Mühlenbein H (1997) The equation for response to selection and its use for prediction. Evol Comput 5(3):303–346

    Article  Google Scholar 

  60. Mühlenbein H, Mahnig T, Rodriguez AO (1999) Schemata, distributions and graphical models in evolutionary optimization. J Heurist 5(2):215–247

    Article  MATH  Google Scholar 

  61. Newman ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133

    Article  Google Scholar 

  62. Nguyen HT, Thai MT, Dinh TN (2016) Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: proceedings of the 2016 international conference on management of data, pp 695–710

  63. Palla G, Derényi I, Farkas I et al (2005) Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043):814–818

    Article  Google Scholar 

  64. Palla G, Ábel D, Farkas IJ, et al (2008) k-clique percolation and clustering. In: Handbook of large-scale random networks. Springer, p 369–408

  65. Pelikan M, Goldberg DE, Cantú-Paz E, et al (1999) Boa: the bayesian optimization algorithm. In: proceedings of the genetic and evolutionary computation conference GECCO-99, Citeseer, pp 525–532

  66. Peña JM, Robles V, Larranaga P et al (2004) Ga-eda: hybrid evolutionary algorithm using genetic and estimation of distribution algorithms. In: international conference on industrial, engineering and other applications of applied intelligent systems. Springer, pp 361–371

  67. Pereira-Leal JB, Enright AJ, Ouzounis CA (2004) Detection of functional modules from protein interaction networks. Proteins Struct Funct Bioinf 54(1):49–57

    Article  Google Scholar 

  68. Pinheiro CAR (2012) Community detection to identify fraud events in telecommunications networks. SAS SUGI proceedings: customer intelligence

  69. 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

    Article  Google Scholar 

  70. Reid F, McDaid A, Hurley N (2012) Percolation computation in complex networks. In: 2012 IEEE/ACM international conference on advances in social networks analysis and mining, IEEE, pp 274–281

  71. Rezvani M, Liang W, Liu C et al (2018) Efficient detection of overlapping communities using asymmetric triangle cuts. IEEE Trans Knowl Data Eng 30(11):2093–2105

    Google Scholar 

  72. Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci 105(4):1118–1123

    Article  Google Scholar 

  73. Samhitha KK, Sajeev G, Narayanan J (2018) A novel community detection method for collaborative networks. In: 2018 international conference on advances in computing. Communications and informatics (ICACCI), IEEE, pp 866–872

  74. Sarr I, Ndong J, Missaoui R (2014) Overlaying social networks of different perspectives for inter-network community evolution. In: Social network analysis-community detection and evolution. Springer, p 45–70

  75. Schmidt MC, Samatova NF, Thomas K et al (2009) A scalable, parallel algorithm for maximal clique enumeration. J Parallel Distrib Comput 69(4):417–428

    Article  Google Scholar 

  76. Schmitt R, Ramos P, Santiago R, et al (2017) Novel clique enumeration heuristic for detecting overlapping clusters. In: 2017 IEEE congress on evolutionary computation (CEC), IEEE, pp 1390–1397

  77. Shang J, Wu H, Zhou S et al (2018) Impc: influence maximization based on multi-neighbor potential in community networks. Phys A 512:1085–1103

    Article  MATH  Google Scholar 

  78. Shen HW, Cheng XQ, Guo JF (2009) Quantifying and identifying the overlapping community structure in networks. J Statist Mech Theory Exp 2009(07):P07042

    Article  Google Scholar 

  79. Spirin V, Mirny LA (2003) Protein complexes and functional modules in molecular networks. Proceed Natl Acad Sci 100(21):12123–12128

    Article  Google Scholar 

  80. Strehl A, Ghosh J (2002) Cluster ensembles–a knowledge reuse framework for combining multiple partitions. J Mach Learn Res 3:583–617

    MathSciNet  MATH  Google Scholar 

  81. Svendsen M, Mukherjee AP, Tirthapura S (2015) Mining maximal cliques from a large graph using mapreduce: tackling highly uneven subproblem sizes. J Parallel Distrib Comput 79:104–114

    Article  Google Scholar 

  82. Tang L, Liu H (2010) Graph mining applications to social network analysis. In: Managing and mining graph data. Springer, p 487–513

  83. Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. In: international conference on discrete mathematics and theoretical computer science, Springer, pp 278–289

  84. Tomita E, Tanaka A, Takahashi H (2006) The worst-case time complexity for generating all maximal cliques and computational experiments. Theoret Comput Sci 363(1):28–42

    Article  MathSciNet  MATH  Google Scholar 

  85. Tumer K, Agogino AK (2008) Ensemble clustering with voting active clusters. Pattern Recogn Lett 29(14):1947–1953

    Article  Google Scholar 

  86. Wang J, Zeng Z, Zhou L (2006) Clan: an algorithm for mining closed cliques from large dense graph databases. In: 22nd international conference on data engineering (ICDE’06), IEEE, pp 73–73

  87. Wang L (2011) Using the relationship of shared neighbors to find hierarchical overlapping communities for effective connectivity in iot. In: 2011 6th international conference on pervasive computing and applications, IEEE, pp 400–406

  88. Wang X, Liu G, Li J (2017) Overlapping community detection based on structural centrality in complex networks. IEEE Access 5:25258–25269

    Article  Google Scholar 

  89. Whang JJ, Gleich DF, Dhillon IS (2016) Overlapping community detection using neighborhood-inflated seed expansion. IEEE Trans Knowl Data Eng 28(5):1272–1284

    Article  Google Scholar 

  90. Wu B, Yang S, Zhao H, et al (2009) A distributed algorithm to enumerate all maximal cliques in mapreduce. In: 2009 fourth international conference on frontier of computer science and technology, IEEE, pp 45–51

  91. Wu H, Shang J, Zhou S et al (2018) Laim: a linear time iterative approach for efficient influence maximization in large-scale networks. IEEE Access 6:44221–44234

    Article  Google Scholar 

  92. Wu P, Pan L (2014) Detecting highly overlapping community structure based on maximal clique networks. In: 2014 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM 2014), IEEE, pp 196–199

  93. Xie J, Szymanski BK, Liu X (2011) Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: 2011 IEEE 11th international conference on data mining workshops, IEEE, pp 344–349

  94. Xie J, Kelley S, Szymanski BK (2013) Overlapping community detection in networks: the state-of-the-art and comparative study. ACM Comput Surv (csur) 45(4):1–35

    Article  MATH  Google Scholar 

  95. Zhang BT (1999) A bayesian framework for evolutionary computation. In: proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), IEEE, pp 722–728

  96. Zhang J, Tan L, Tao X, et al (2018) Slind: identifying stable links in online social networks. In: international conference on database systems for advanced applications, Springer, pp 813–816

  97. Zhang J, Tao X, Tan L, et al (2018) On link stability detection for online social networks. In: international conference on database and expert systems applications, Springer, pp 320–335

  98. Zhang Q, Sun J, Tsang E (2005) An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Trans Evol Comput 9(2):192–200

    Article  Google Scholar 

  99. Zhang S, Ning X, Zhang XS (2006) Identification of functional modules in a ppi network by clique percolation clustering. Comput Biol Chem 30(6):445–451

    Article  MATH  Google Scholar 

  100. Zhang X, Wang C, Su Y et al (2017) A fast overlapping community detection algorithm based on weak cliques for large-scale networks. IEEE Trans Comput Soc Syst 4(4):218–230

    Article  Google Scholar 

  101. Zhang Z, Wang Z (2015) Mining overlapping and hierarchical communities in complex networks. Phys A 421:25–33

    Article  Google Scholar 

  102. Zhang Z, Cui L, Pan Z, et al (2018) A triad percolation method for detecting communities in social networks. Data Sci J 17

  103. Zhao X, Liang J, Wang J (2021) A community detection algorithm based on graph compression for large-scale social networks. Inf Sci 551:358–372

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Author notes

  1. These authors contributed equally to this work.

Authors and Affiliations

  1. Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal, 462001, MP, India

    Sumit Kumar Gupta, Dhirendra Pratap Singh & Jaytrilok Choudhary

Authors
  1. Sumit Kumar Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dhirendra Pratap Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jaytrilok Choudhary
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sumit Kumar Gupta.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gupta, S.K., Singh, D.P. & Choudhary, J. A review of clique-based overlapping community detection algorithms. Knowl Inf Syst 64, 2023–2058 (2022). https://doi.org/10.1007/s10115-022-01704-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10115-022-01704-6

Keywords

Search

Navigation