Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A fast divisive community detection algorithm based on edge degree betweenness centrality

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Many complex systems in the real world such as social networks can be modeled by complex networks. The complex network analysis and especially community detection is an important research topic in graph analysis that aims to identify the structure of a graph and its similar groups of nodes. In recent years, various algorithms such as Girvan and Newman’s method (GN) is introduced which is based on a divisive approach for graph clustering. Although GN is a highly popular and widely used method, it suffers from scalability and computational complexity. GN needs O(m3) and O(m3 + m3logm) time to detects communities in unweighted and weighted graphs respectively. Hence, in this paper, a faster method is suggested that detects communities in O(m2) for both weighted and unweighted graphs. In this paper, firstly, we define degree for each edge and then we propose a new and fast approach for the calculation of edges betweenness that is based on edge degree centrality. Furthermore, in order to boost the speed of the algorithm, we suggest instead of just one edge, multiple edges can be removed in each iteration. Since the proposed method wants to enhance the GN method, in the evaluation section the quality of detected communities, the accuracy and speed of the suggested method are assessed by the comparison with the GN method. Results prove that our proposed method is extremely faster than plain GN and the detected communities often have better quality than the plain GN method. Furthermore, we compare our proposed method with meta-heuristic algorithms which are a novel approach for community detection. Results clarify that the suggested method is notably faster, scalable, stable, reliable, and efficient than meta-heuristic algorithms.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Chapela V, et al (2015) Mathematical foundations: complex networks and graphs (a review). Intentional risk management through complex networks analysis. Springer, Cham, pp 9–36

    Book  Google Scholar 

  2. Mochón M (2016) Social network analysis and big data tools applied to the systemic risk supervision. Int J Interact Multimed Artif Intell (Ijimai) 3(6):34–37

    Google Scholar 

  3. Lee H, Shao B, Kang U (2015) Fast graph mining with HBase. Inform Sci 315:56–66

    Article  MathSciNet  Google Scholar 

  4. Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D (2004) Defining and identifying communities in networks. Proc Natl Acad Sci 101(9):2658–2663

    Article  Google Scholar 

  5. Fortunato S (2010) Community detection in graphs. Phys Rep 486(3–5):75–174

    Article  MathSciNet  Google Scholar 

  6. Khan K, Sahai A, Campus A (2012) A fuzzy c-means bi-sonar-based metaheuristic optimization algorithm. Int J Artif Intell Interac Multimed (IJIMAI) 1(7):26–32

    Google Scholar 

  7. Papadopoulos S, Kompatsiaris Y, Vakali A, Spyridonos P (2012) Community detection in social media. Data Min Knowl Disc 24(3):515–554

    Article  Google Scholar 

  8. Plantié M, Crampes M (2013) Survey on social community detection. In social media retrieval. Springer, London, pp 65–85

    Book  Google Scholar 

  9. Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, Wagner D (2008) On modularity clustering. IEEE Trans Knowl Data Eng 20(2):172–188

    Article  MATH  Google Scholar 

  10. Waltman L, Van Eck N (2013) A smart local moving algorithm for large-scale modularity-based community detection. Europ Phys J B 86(11):471

    Article  Google Scholar 

  11. Schaeffer S (2007) Graph clustering. Comput Sci Rev 1(1):27–64

    Article  MATH  Google Scholar 

  12. Bedi P, Sharma C (2016) Community detection in social networks. Wiley Interdiscip Rev Data Mining Knowl Discov 6(3):115–135

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  15. Newman M (2004) Analysis of weighted networks. Phys Rev E 70(5):056131

    Article  Google Scholar 

  16. Hurajová J, Madaras T (2016) Revising the Newman-Girvan algorithm. In: ITAT Proceedings, CEUR workshop proceedings, pp 200–205

  17. Kernighan B, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49 (2):291–307

    Article  MATH  Google Scholar 

  18. Blondel V, Guillaume J, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Statist Mech Theory Exper 10:10008

    Article  Google Scholar 

  19. JSuaris P, Kedem G (1988) An algorithm for quadrisection and its application to standard cell placement. IEEE Trans Circ Syst 35(3):294–303

    Article  Google Scholar 

  20. Rotta R, Noack A (2011) Multilevel local search algorithms for modularity clustering. J Exper Algor (JEA) 16:2–3

    MathSciNet  MATH  Google Scholar 

  21. Lu H, Halappanavar M, Kalyanaraman A (2015) Parallel heuristics for scalable community detection. Parallel Comput 47:19–37

    Article  MathSciNet  Google Scholar 

  22. Liu W, Yue K, Wu H, Fu X, Zhang Z, Huang W (2018) Markov-network based latent link analysis for community detection in social behavioral interactions. Appl Intell 48(8):2081–2096

    Article  Google Scholar 

  23. Guimera R, Sales-Pardo M, Amaral LA (2004) Modularity from fluctuations in random graphs and complex networks. Phys Rev E 70(2):025101

    Article  Google Scholar 

  24. Massen C, Doye J (2005) Identifying communities within energy landscapes. Phys Rev E 71(4):046101

    Article  Google Scholar 

  25. Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Phys Rev E 72(2):027104

    Article  Google Scholar 

  26. Tasgin M, Herdagdelen A, Bingol H (2007) Community detection in complex networks using genetic algorithms. arXiv:0711.0491

  27. Pizzuti C (2008) Ga-net: a genetic algorithm for community detection in social networks. In: International conference on parallel problem solving from nature. Springer, Berlin, pp 1081–1090

  28. Shang R, Bai J, Jiao L, Jin C (2013) Community detection based on modularity and an improved genetic algorithm. Physica A: Statist Mech Appl 392(5):1215–1231

    Article  Google Scholar 

  29. Gong M, Fu B, Jiao L, Du H (2011) Memetic algorithm for community detection in networks. Phys Rev E 84(5):056101

    Article  Google Scholar 

  30. Fan H, Zhong Y, Zeng G (2018) Overlapping community detection based on discrete biogeography optimization. Appl Intell 48(5):1314–1326

    Google Scholar 

  31. Guendouz M, Amine A, Hamou R (2017) A discrete modified fireworks algorithm for community detection in complex networks. Appl Intell 46(2):373–385

    Article  Google Scholar 

  32. Pizzuti C (2012) A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans Evol Comput 16(3):418–430

    Article  Google Scholar 

  33. Shi C, Yan Z, Cai Y, Wu B (2012) Multi-objective community detection in complex networks. Appl Soft Comput 12(2):850–859

    Article  Google Scholar 

  34. Gong M, Ma L, Zhang Q, Jiao L (2012) Community detection in networks by using multiobjective evolutionary algorithm with decomposition. Physica A: Statist Mech Appl 391(15):4050–4060

    Article  Google Scholar 

  35. Gong M, Cai Q, Chen X, Ma L (2014) Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Trans Evol Comput 18(1):82–97

    Article  Google Scholar 

  36. Meza J, Espitia H, Montenegro C, Giménez E, González-Crespo R (2017) MOVPSO: vortex multi-objective particle swarm optimization. Appl Soft Comput 52:1042–1057

    Article  Google Scholar 

  37. Zhou X, Zhao X, Liu Y (2018) A multiobjective discrete bat algorithm for community detection in dynamic networks. Appl Intell 48(9):3081–3093

    Article  Google Scholar 

  38. Li Z, He L, Li Y (2016) A novel multiobjective particle swarm optimization algorithm for signed network community detection. Appl Intell 44(3):621–633

    Article  Google Scholar 

  39. Brandes U, Fleischer D (2005) Centrality measures based on current flow. In: Annual symposium on theoretical aspects of computer science. Springer, Berlin, pp 533–544

  40. Mason O, Verwoerd M (2007) Graph theory and networks in biology. IET Syst Biol 1(2):89–119

    Article  Google Scholar 

  41. Estrada E (2006) Virtual identification of essential proteins within the protein interaction network of yeast. Proteomics 6(1):35–40

    Article  Google Scholar 

  42. Freeman L (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35–41

    Article  Google Scholar 

  43. Newman ME (2005) A measure of betweenness centrality based on random walks. Soc Netw 27(1):39–54

    Article  Google Scholar 

  44. Ahajjam S, El Haddad M, Badir H (2018) A new scalable leader-community detection approach for community detection in social networks. Soc Netw 54:41–49

    Article  Google Scholar 

  45. Lancichinetti A, Fortunato S (2009) Community detection algorithms: a comparative analysis. Phys Rev E 80(5):056117

    Article  Google Scholar 

  46. Newman M, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69 (2):026113

    Article  Google Scholar 

  47. Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177

    Article  MATH  Google Scholar 

  48. Brandes U (2008) On variants of shortest-path betweenness centrality and their generic computation. Soc Netw 30(2):136–145

    Article  Google Scholar 

  49. Wagner S, Wagner D (2007) Comparing clusterings: an overview Karlsruhe. Universität Karlsruhe, Fakultät für Informatik

    Google Scholar 

  50. Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2017) Metrics for community analysis: a survey. ACM Comput Surv (CSUR) 50(4):54

    Article  Google Scholar 

  51. Talbi EG (2009) Metaheuristics: from design to implementation. mplementation, vol 74. Wiley

Download references

Author information

Authors and Affiliations

  1. Faculty of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

    Majid Arasteh & Somayeh Alizadeh

Authors
  1. Majid Arasteh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Somayeh Alizadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Somayeh Alizadeh.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Arasteh, M., Alizadeh, S. A fast divisive community detection algorithm based on edge degree betweenness centrality. Appl Intell 49, 689–702 (2019). https://doi.org/10.1007/s10489-018-1297-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-018-1297-9

Keywords

Search

Navigation