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

KO: Modularity optimization in community detection

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

Many algorithms have been developed to detect communities in networks. The success of these developed algorithms varies according to the types of networks. A community detection algorithm cannot always guarantee the best results on all networks. The most important reason for this is the approach algorithms follow when dividing any network into communities (sub-networks). The modularity of the network determines the quality of communities in networks. It is concluded that networks with high modularity values are divided into more successful communities (clusters, sub-networks). This study proposes a modularity optimization algorithm to increase clustering success in any network without being dependent on any community detection algorithm. The basic approach of the proposed algorithm is to transfer nodes at the community boundary to neighboring communities if they meet the specified conditions. The method called KO (Karcı–Oztemiz) optimization algorithm maximizes the modularity value of any community detection algorithm in the best case, while it does not change the modularity value in the worst case. For the KO algorithm’s test, in this study, Walktrap, Cluster Edge Betweenness, Label Propagation, Fast Greedy, and Leading Eigenvector community detection algorithms have been applied on three popular networks that were unweighted and undirected previously used in the literature. The community structures created by five community detection algorithms were optimized via the KO algorithm and the success of the proposed method was analyzed. When the results are examined, the modularity values of the community detection algorithms applied on the three different networks have increased at varying rates (0%, …,14.73%).

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
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Explore related subjects

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

Data Availability

The datasets used in the study are presented in many different sources. Relevant data can be accessed at www.konect.cc/networks/ and www.kaggle.com (public repository). At the same time, the datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

References

  1. Fortunato S, Hric D (2016) Community detection in networks: a user guide. Phys Rep 659:1–44. https://doi.org/10.1016/j.physrep.2016.09.002

    Article  MathSciNet  Google Scholar 

  2. Chakraborty T, Dalmia A, Mukherjee A, Ganguly N (2018) Metrics for community analysis: a survey. ACM Comput Surv 50(4):37. https://doi.org/10.1145/3091106

    Article  Google Scholar 

  3. Kaur S, Singh S, Kaushal S, Sangaiah AK (2016) Comparatıve analysis of quality metrics for community detection in social networks using genetic algorithm. Neural Network World 26(6):625–641. https://doi.org/10.14311/NNW.2016.26.036

    Article  Google Scholar 

  4. Akbari H (2021) Exploratory social-spatial network analysis of global migration structure. Social Networks 64:181–193. https://doi.org/10.1016/j.socnet.2020.09.007

    Article  Google Scholar 

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

    Article  Google Scholar 

  6. Mengdi L, Ying X (2022) Community detection via network node vector label propagation. Phys A: Statis Mech Appl 593:126931. https://doi.org/10.1016/j.physa.2022.126931

    Article  Google Scholar 

  7. Labatut V, Balasque J-M (2012) Detection and interpretation of communities in complex networks. Pract Method Appl. https://doi.org/10.1007/978-1-4471-4048-1_4

    Article  Google Scholar 

  8. Zarei M, Samani KA (2009) Eigenvectors of network complement reveal community structure more accurately. Physica A 388(8):1721–1730. https://doi.org/10.1016/j.physa.2009.01.007

    Article  Google Scholar 

  9. Öztemiz F (2021) Karmaşık ağlarda hakim düğümlerin belirlenmesi için yeni bir yöntem. İnönü University Institute of Science Ph.D. Thesis

  10. Chintalapudi SR, Prasad MHMK (2015) A survey on community detection algorithms in large scale real-world networks. In: 2nd international conference on computing for sustainable global development (INDIACom) 2015, pp. 1323–1327

  11. Dickinson B, Hu W (2015) The effects of centrality ordering in label propagation for community detection. Social Networking 4:103–111. https://doi.org/10.4236/sn.2015.44012

    Article  Google Scholar 

  12. Bu Z, Zhang C, Xia Z, Wang J (2013) A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social network. Knowl-Based Syst 50:246–259. https://doi.org/10.1016/j.knosys.2013.06.014

    Article  Google Scholar 

  13. Shırzad M, Feızı-Derakhshı M-R (2016) Communıty detection in social networks based on modularity optimization. Int J Adv Electron Comput Sci Vol. 3 (4)

  14. Fang W, Wang X, Liu L, Wu Z, Tang S, Zheng Z (2022) Community detection through vector-label propagation algorithms. Chaos, Solitons & Fractals 158:456. https://doi.org/10.1016/j.chaos.2022.112066

    Article  MathSciNet  Google Scholar 

  15. Hamann M, Strasser B, Wagner D, Zeitz T (2018) Distributed graph clustering using modularity and map equation. Lect Notes Comput Sci 11014:688–702. https://doi.org/10.1007/978-3-319-96983-1_49

    Article  Google Scholar 

  16. Souam F, Aïtelhadj A, Baba-Ali R (2014) Dual modularity optimization for detecting overlapping communities in bipartite networks. Knowl Inf Syst 40:455–488. https://doi.org/10.1007/s10115-013-0644-8

    Article  Google Scholar 

  17. Newman MEJ (2006) Modularity and community structure in networks. Proc Natl Acad Sci 8577–8582(103):23. https://doi.org/10.1073/pnas.0601602103

    Article  Google Scholar 

  18. Aloise D, Caporossi G, Hansen P, Liberti L, Perron S, Ruiz M (2012) Modularity maximization in networks by variable neighborhood search. Graph Partitioning Graph Clustering. https://doi.org/10.1090/conm/588/11705

    Article  MATH  Google Scholar 

  19. Lee J, Gross SP, Lee J (2012) Modularity optimization by conformational space annealing. Phys Rev E 85:056702. https://doi.org/10.1103/PhysRevE.85.056702

    Article  Google Scholar 

  20. Zhang XS, Wang RS, Wang Y, Wang J, Qiu Y, Wang L, Chen L (2009) Modularity optimization in community detection of complex networks. EPL (Europhysics Letters). https://doi.org/10.1209/0295-5075/87/38002

    Article  Google Scholar 

  21. Hollocou A, Bonald T, Lelarge M (2019) Modularity-based Sparse Soft Graph Clustering. In: Proceedings of the Twenty-Second international conference on artificial intelligence and statistics in proceedings of machine learning research 89: 323–332. Available from https://proceedings.mlr.press/v89/hollocou19a.html

  22. Liu X, Murata T (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A 389(7):1493–1500. https://doi.org/10.1016/j.physa.2009.12.019

    Article  Google Scholar 

  23. Wu L, Zhang Q, Chen C, Guo K, Wang D (2020) Deep learning techniques for community detection in social networks. IEEE Access 8:96016–96026. https://doi.org/10.1109/ACCESS.2020.2996001

    Article  Google Scholar 

  24. Waltman L, van Eck NJ (2013) A smart local moving algorithm for large-scale modularity-based community detection. Eur Phys J B 86:471. https://doi.org/10.1140/epjb/e2013-40829-0

    Article  Google Scholar 

  25. Schuetz P, Caflisch A (2008) Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Phys Rev E 77:046112. https://doi.org/10.1103/PhysRevE.77.046112

    Article  Google Scholar 

  26. Chen M, Kuzmin K, Szymanski BK (2014) Community detection via maximization of modularity and its variants. IEEE Trans Comput Social Syst 1(1):46–65. https://doi.org/10.1109/TCSS.2014.2307458

    Article  Google Scholar 

  27. Lehmann S, Hansen L (2007) Deterministic modularity optimization. Eur Phys J B 60:83–88. https://doi.org/10.1140/epjb/e2007-00313-2

    Article  Google Scholar 

  28. Nascimento MCV, Pitsoulis L (2013) Community detection by modularity maximization using GRASP with path relinking. Comput Oper Res 40(12):3121–3131. https://doi.org/10.1016/j.cor.2013.03.002

    Article  MATH  MathSciNet  Google Scholar 

  29. Aung TT, Nyunt TTS (2020) Modularity based ABC algorithm for detecting communities in complex networks. Int J Mach Learn Comput 10(2):323–329. https://doi.org/10.18178/ijmlc.2020.10.2.938

    Article  Google Scholar 

  30. Xu G, Guo J, Yang P (2021) TNS-LPA: An improved label propagation algorithm for community detection based on two-level neighbourhood similarity. IEEE Access 9:23526–23536. https://doi.org/10.1109/ACCESS.2020.3045085

    Article  Google Scholar 

  31. Yan M and Guoqiang C (2021) Label propagation community detection algorithm based on density peak optimization. In: 17th International conference on computational intelligence and security (CIS) pp 80–84. https://doi.org/10.1109/CIS54983.2021.00025

  32. Brandes U et al (2008) On modularity clustering. IEEE Trans Knowl Data Eng 20(2):172–188. https://doi.org/10.1109/TKDE.2007.190689

    Article  Google Scholar 

  33. Trajanovski S, Kuipers FA, Martín-Hernández J, Van Mieghem P (2013) Generating graphs that approach a prescribed modularity. Comput Commun 36(4):363–372

    Article  Google Scholar 

  34. Igraph Library. https://igraph.org/. Accessed 19.08.2022

  35. Öztemiz F, Karci A (2022) Bağlı Graflarda Etkili Düğümlerin Belirlenmesinde Yeni Bir Yaklaşım. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 24(70):143–155. https://doi.org/10.21205/deufmd.2022247014

    Article  Google Scholar 

  36. Cerdeira JO, Silva PC (2021) A centrality notion for graphs based on Tukey depth. Appl Math Comput 409:545. https://doi.org/10.1016/j.amc.2021.126409

    Article  MATH  MathSciNet  Google Scholar 

  37. Laassem B, Idarrou A, Boujlaleb L, Iggane M (2022) Label propagation algorithm for community detection based on Coulomb’s law. Phys A: Statis Mech Appl 593:35435. https://doi.org/10.1016/j.physa.2022.126881

    Article  Google Scholar 

  38. Acharya DB, Zhang H (2020) Community detection clustering via gumbel softmax. SN Comput Sci 1:262. https://doi.org/10.1007/s42979-020-00264-2

    Article  Google Scholar 

  39. Konect. http://konect.cc/networks/. Accessed: 20.08.2022

  40. Harenberg S, Bello G, Gjeltema L, Ranshous S, Harlalka J, Seay R, Padmanabhan K, Samatova N (2014) Community detection in large-scale networks: a survey and empirical evaluation. WIREs Comput Stat 6:426–439

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  42. Öztemiz F ve Karci A (2021) Topluluk Tespiti Yöntemi ile Ulaşım Ağında Verimli Yeşil Dalga Koridorlarının Belirlenmesi. Politeknik Dergisi ss. 1–1. https://doi.org/10.2339/politeknik.1074962

  43. Javed MA, Younis MS, Latif S, Qadir J, Baig A (2018) Community detection in networks: a multidisciplinary review. J Netw Comput Appl 108:87–111. https://doi.org/10.1016/j.jnca.2018.02.011

    Article  Google Scholar 

  44. Gates KM, Henry T, Steinley D, Fair DA (2016) A monte carlo evaluation of weighted community detection algorithms. Front Neuroinform 10:5435. https://doi.org/10.3389/fninf.2016.00045

    Article  Google Scholar 

  45. Hoffman M, Steinley D, Gates KM, Prinstein MJ, Brusco MJ (2018) Detecting Clusters/communities in social networks. Multivariate Behav Res 53(1):57–73

    Article  Google Scholar 

  46. Newman ME (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133. https://doi.org/10.1103/PhysRevE.69.066133

    Article  Google Scholar 

  47. Jokar E, Mosleh M (2019) Community detection in social networks based on improved label propagation algorithm and balanced link density. Phys Lett A 383(8):718–727. https://doi.org/10.1016/j.physleta.2018.11.033

    Article  MathSciNet  Google Scholar 

  48. Xing Y, Meng F, Zhou Y, Zhu M, Shi M, Sun G (2014) A node influence based label propagation algorithm for community detection in networks. Sci World J. https://doi.org/10.1155/2014/627581

    Article  Google Scholar 

  49. Cordasco G, Gargano L (2010) Community detection via semi-synchronous label propagation algorithms. IEEE International Workshop on: Business Applications of Social Network Analysis (BASNA) pp. 1–8. https://doi.org/10.1109/BASNA.2010.5730298

  50. Christensen AP, Garrido LE, Golino H (2020) Comparing community detection algorithms in psychological data: a Monte Carlo simulation. PsyArXiv. https://doi.org/10.31234/osf.io/hz89e

  51. Newman MEJ (2006) Finding community structure using the eigenvectors of matrices. Phys Rev E 74:036104. https://doi.org/10.1103/PhysRevE.74.036104

    Article  MathSciNet  Google Scholar 

  52. Aktunc R, Toroslu IH, Ozer M and Davulcu H (2015) A dynamic modularity based community detection algorithm for large-scale networks: DSLM. (ASONAM ‘15) New York USA 1177–1183. https://doi.org/10.1145/2808797.2808822

  53. Optimal Cluster. https://igraph.org/r/doc/cluster_optimal.html. Accessed: 29.07.2022

  54. Danon L, Duch J, Díaz-Guilera A, Arenas A (2005) Comparing community structure identification. J Stat Mech 2005(9):P09008. https://doi.org/10.1088/1742-5468/2005/09/P09008

    Article  Google Scholar 

  55. Botta F, del Genio C (2016) Finding network communities using modularity density. J Stat Mech: Theory Exp. https://doi.org/10.1088/1742-5468/2016/12/123402

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Software Engineering, Inonu University, 44210, Battalgazi, Malatya, Turkey

    Furkan Öztemiz & Ali Karcı

Authors
  1. Furkan Öztemiz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ali Karcı
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Furkan Öztemiz.

Ethics declarations

Conflict of Interest

The authors declare that they have no conflict of interest. Researches are not related to human participants and/or animals.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Öztemiz, F., Karcı, A. KO: Modularity optimization in community detection. Neural Comput & Applic 35, 11073–11087 (2023). https://doi.org/10.1007/s00521-023-08284-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-023-08284-8

Keywords

Search

Navigation