Kybernetika 61 no. 4, 509-536, 2025

New gravitational algorithms for the detection of overlapping and disjoint communities in weighted complex networks

Nermin Kartli, Pelin Çetin and Selin AyhanDOI: 10.14736/kyb-2025-4-0509

Abstract:

The excessive increase in the amount of data caused a rise in the number of vertices and edges in the graph models. This gave rise to the concept of complex networks. Complex networks are present in almost every area of life, in social networks, natural sciences, drug discovery, etc. Detection of overlapping or disjoint communities in complex networks is an important problem. In this study, we propose two new algorithms to detect overlapping and disjoint communities in weighted complex networks. We assume that the weights represent how close the vertices are to each other in some sense. First, we calculate the similarity of the vertices to each other using the universal gravitational law, then place similar vertices in overlapping communities. Then, for each vertex in multiple communities, we calculate the attraction force of each community where this vertex is located. We leave the vertex in the community that attracts the vertex more and delete it from the others. The results of experiments conducted on complex networks consisting of real and artificial data show the efficiency of the proposed algorithms.

Keywords:

weighted complex networks, community detection, overlapping community, disjoint community

Classification:

94C15

paper.pdf

References:

  1. R. Alguliyev, R. Aliguliyev and L. Sukhostat: Method for quantitative risk assessment of cyber-physical systems based on vulnerability analysis. Kybernetika 60 (2024), 6, 779-796.   DOI: 10.14736/kyb-2024-6-0779
  2. S. E. Amrahov, Y. Ar, B. Tugrul, B. E. Akay and N. Kartli: A new approach to Mergesort algorithm: Divide smart and conquer. Future Gener. Computer Systems 157 (2024), 330-343.   DOI:10.1016/j.future.2024.03.049
  3. S. E. Amrahov and B. Tugrul: A community detection algorithm on graph data. In: 2018 International Conference on Artificial Intelligence and Data Processing (IDAP) IEEE (2018), pp. 1-4.   DOI:10.1109/IDAP.2018.8620850
  4. Y. Ar: An initialization method for the latent vectors in probabilistic matrix factorization for sparse datasets. Evol. Intell. 13 (2020), 2, 269-281.   DOI:10.1007/s12065-019-00299-2
  5. M. Arasteh, S. Alizadeh and C. G. Lee: Gravity algorithm for the community detection of large-scale network. J. Ambient Intell. Human Comput. 14 (2023), 1217–-1228.   DOI:10.1007/s12652-021-03374-8
  6. R. K. Bera and S. K. Mondal: Analyzing a transportation problem with reliability under the shadowed environment. Oper. Res. Forum 6 (2025), article number 69.   DOI:10.1007/s43069-025-00469-2
  7. M. Bisht and S. Rawat: A novel interval-valued neutrosophic model to solve uncertain transportation problems. OPSEARCH (2025), 1-35.   DOI:10.1007/s12597-025-00948-4
  8. P. Cetin and Ö. Tanriöver: Priority rule for resource constrained project planning problem with predetermined work package durations. J. Faculty of Engineering and Architecture of Gazi University 35 (2020), 3, 1537-1549.   DOI:10.17341/gazimmfd.545873
  9. P. Cetin and S. E. Amrahov: A new network-based community detection algorithm for disjoint communities. Turkish J. Electr. Engrg. Comput. Sci. 30 (2022), 6, Article 13.   DOI:10.55730/1300-0632.3933
  10. P. Cetin and S. Emrah Amrahov: A new overlapping community detection algorithm based on similarity of neighbors in complex networks. Kybernetika 58 (2022), 2, 277-300.   DOI: 10.14736/kyb-2022-2-0277
  11. K. Chi, H. Qu and Z. Fu: A novel approach for overlapping community detection in social networks based on the attraction. J. Comput. Sci. 85 (2025), 102508.   DOI:10.1016/j.jocs.2024.102508
  12. S. Dhanasekar, J. J. Rani and M. Annamalai: Transportation problem for interval-valued trapezoidal intuitionistic fuzzy numbers. Int. J. Fuzzy Logic Intell. Systems 22 (2022), 2, 155-168.   DOI:10.5391/IJFIS.2022.22.2.155
  13. J. H. Chin and K. Ratnavelu: Community detection using constrained label propagation algorithm with nodes exemption. Computing \textit(104) (2022), 339–-358.   DOI:10.1007/s00607-021-00966-2
  14. A. Ghareeb, O. Nooruldeen, C. A. Arslan and J. K. Choi: Synergistic optimization of predictive models for water quality analysis in treatment plants using machine learning and evolutionary algorithms. Evolut. Intell. 18 (2025), 2, 1-24.   DOI:10.1007/s12065-025-01022-0
  15. S. Goswami and A. K. Das: Determining maximum cliques for community detection in weighted sparse networks. Knowl. Inf. Syst. 64 (2022), 289–-324.   DOI:10.1007/s10115-021-01631-y
  16. H. Hajibabaei, V. Seydi and A. Koochari: Community detection in weighted networks using probabilistic generative model. J. Intell. Inf. Syst. 60 (2023), 119–-136.   DOI:10.1007/s10844-022-00740-6
  17. E. Hazrati Nejad, S. Yigit-Sert and S. Emrah Amrahov: An effective global path planning algorithm with teaching-learning-based optimization. Kybernetika 60 (2024), 3, 293-316.   DOI: 10.14736/kyb-2024-3-0293
  18. Z. He, W. Chen, X. Wei and Y. Liu: Mining statistically significant communities from weighted networks. IEEE Trans. Knowledge Data Engrg. 35 (2022), 6, 6073-6084.   DOI: 10.1109/TKDE.2022.3176816
  19. N. Kartli: Hybrid algorithms for fixed charge transportation problem. Kybernetika 61 (2025), 2, 141-167.   DOI: 10.14736/kyb-2025-2-0141
  20. N. Kartli, E. Bostanci and M. S. Guzel: A new algorithm for optimal solution of fixed charge transportation problem. Kybernetika 59 (2023), 1, 45-63.   DOI: 10.14736/kyb-2023-1-0045
  21. N. Kartli, E. Bostanci and M. S. Guzel: Heuristic algorithm for an optimal solution of fully fuzzy transportation problem. Computing 106 (2024), 10, 3195-3227.   DOI:10.1007/s00607-024-01319-5
  22. A. Khastan, B. H. Jimenez and A. B. Moreno: On the new solution to interval linear fractional programming problems. Evolut. Intell. 17 (2024), 5, 4001-4005.   DOI:10.1007/s12065-024-00968-x
  23. F. R. Khawaja, Z. Zhang and A. Ullah: Common-neighbor based overlapping community detection in complex networks. Soc. Netw. Anal. Min. 15 (2025), Article number 61.   DOI:10.1007/s13278-025-01480-5
  24. A. Kumar, P. Kumar and R. Dohare: Revisiting neighbourhood proximity based algorithm for overlapping community detection in weighted networks. Soc. Netw. Anal. Min. 14 (2024), 105.   DOI:10.1007/s13278-024-01257-2
  25. P. Kumar: A depth-first search approach to detect the community structure of weighted networks using the neighbourhood proximity measure. Int. J. Data Sci. Anal. (2024).   DOI:10.1007/s41060-024-00631-9
  26. A. Lancichinetti, S. Fortunato and J. Kertész: Detecting the overlapping and hierarchical community structure in complex networks. {New J. Physics \textbf{11} (2009), 3, 033015.   DOI:10.1088/1367-2630/11/3/033015
  27. S. Li, L. Jiang, X. Wu, W. Han, D. Zhao and Z. Wang: A weighted network community detection algorithm based on deep learning. Appl. Math. Comput. 401 (2021), 126012.   DOI:10.1016/j.amc.2021.126012
  28. W. Li, J. Wang and J. Cai:     CrossRef
  29. H. Liu, Z. Li and N. Wang: Overlapping community detection algorithm based on similarity of node relationship. Soft Comput 27 (2023), 19, 13689–-13700.   10.1007/s00500-023-08067-2
  30. Z. Lu and Z. A. Dong: Gravitation-based hierarchical community detection algorithm for structuring supply chain network. Int. J. Comput. Intel. Syst. 16 (2023), 110.   DOI:10.1007/s44196-023-00290-x
  31. J. Ma, L. Zhou and J. Zuo: Adaptive community detection based on node dissimilarity. Int. J. Modern Physics C 2550066.   DOI:10.1142/S0129183125500664
  32. A. McDaid, D. Greene and N. Hurley: Normalized mutual information to evaluate overlapping community finding algorithms. arXiv preprint arXiv:1110.2515 (2011).   DOI:10.48550/arXiv.1110.2515
  33. S. N. Mohammed and S. Gunduc: TPM: Transition Probability Matrix-Graph Structural Feature based Embedding. Kybernetika 59 (2023), 2, 234-253.   DOI: 10.14736/kyb-2023-2-0234
  34. G. Murray, G. Carenini and R. Ng: Using the Omega Index for evaluating abstractive community detection. In: Proc. Workshop on Evaluation Metrics and System Comparison for Automatic Summarization}, Association for Computational Linguistics, 2012. pp. 10-18.   CrossRef
  35. K. Nallusamy and K. S. Easwarakumar: PERMDEC: community deception in weighted networks using permanence. Computing 106 (2024), 353–-370.   DOI:10.1007/s00607-023-01223-4
  36. E. Nasibov, M. Demir and A. Vahaplar: A fuzzy logic apparel size decision methodology for online marketing. Int. J. Clothing Sci. Technol. 31 (2019), 2, 299-315.   DOI:10.1108/IJCST-06-2018-0077
  37. M. E. J. Newman: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 74 (2006), 3, 036104.   https://doi.org/10.1103/PhysRevE.74.036104
  38. B. Ozhan and B. Tugrul: Analysis of Turkish cuisine flavors network. Int. J. Food Sci. Technol. 59 (2024), 2, 908-915.   DOI:10.1111/ijfs.16849
  39. S. Pandey and A. Gupta: Lazy merge sort: An improvement over merge sort. In: 2024 International Conference on Electrical Electronics and Computing Technologies (ICEECT), Greater Noida 2024, pp. 1-6.   DOI:10.1109/ICEECT61758.2024.10738877
  40. H S. Pattanayak, H. K. Verma and A. L. Sangal: Gravitational community detection by predicting diameter. Discrete Math. Algorithms Appl. 14 (2022), 4, 2150145.   DOI:10.1142/S1793830921501457
  41. P. Prokop, P. Drazdilova and J. Platos: Overlapping community detection in weighted networks via hierarchical clustering. Plos one 19 (2024, 10, e0312596.   DOI:10.1371/journal.pone.0312596
  42. G. Rossetti, L. Pappalardo and S. Rinzivillo: A novel approach to evaluate community detection algorithms on ground truth. In: Complex Networks VII (2016), 133-144.   CrossRef
  43. S. Sandhiya and A. Dhanapal: Solving neutrosophic multi-dimensional fixed charge transportation problem. Contempor. Math. 5 (2024), 3, 3601-3624.   DOI:10.37256/cm.5320244927
  44. L. Samandari Masooleh, J. E. Arbogast, W. D. Seider, U. Oktem and M. Soroush: An efficient algorithm for community detection in complex weighted networks. AIChE J. 67 (2021), 7, e17205.   DOI:10.1002/aic.17205
  45. M. Shen and Z. Ma: A novel node gravitation-based label propagation algorithm for community detection. Int. J. Modern Physics C 30 (2019), 6, 1950049.   DOI: 10.1142/S0129183119500499
  46. J. Sheng, C. Liu, L. Chen, B. Wang and J. Zhang: Research on community detection in complex networks based on internode attraction. Entropy 22 (2020), 12, 1383.   DOI:10.3390/e22121383
  47. Shivani, D. Chauhan and D. Rani: A feasibility restoration particle swarm optimizer with chaotic maps for two-stage fixed-charge transportation problems. Swarm Evolution. Comput. 91 (2024), 101776.   DOI:10.1016/j.swevo.2024.101776.
  48. M. Subramaniam, T. Tripathi and O. Chandraumakantham: Cluster Sort: A Novel Hybrid Approach to Efficient In-Place Sorting Using Data Clustering. IEEE Access 13 (2025), 74359-74374.   DOI:10.1109/ACCESS.2025.3564380
  49. C. K. Suja, C. V. Harinarayanan and A. Arivalagan: Novel objective-based coot puzzle optimisation for overlapping community expansion in complex networks. Int. J. Network. Virtual Organis. 31 (2024), 4, 281-305.   DOI:10.1504/IJNVO.2024.144079
  50. Y. Wang, J. Chen, J. Bai, X. Lin, S. Liang and Y. Zhang: Spatial-SLPA: uncovering overlapping communities in geospatial networks via the spatially constrained speaker-listener label propagation algorithm. In: International Conference on Smart Transportation and City Engineering (STCE 2024), SPIE, 13575 (2025), pp. 1247-1259).   DOI:10.1117/12.3061956
  51. X. Wu, D. Teng, H. Zhang, J. Hu, Y. Quan, Q. Miao and P. G. Sun: Graph reconstruction and attraction method for community detection. Appl. Intell. 55 (2025), 5, 1-17.   DOI:10.1007/s10489-024-05858-4
  52. C. Yang, M. Li and Y. Wang: Overlapping community detection algorithm based on the law of universal gravitation. In: MATEC Web of Conferences 22 (2015), 01056 EDP Sciences.   DOI:10.1051/matecconf/20152201056
  53. H. B. Yıldırım, K. Kullu and S. E. Amrahov: A graph model and a three-stage algorithm to aid the physically disabled with navigation. Univers. Access Inform. Soc. 23 (2024), 2, 901-911.   DOI: 10.1007/s10209-023-00981-4
  54. Y. Y. Yu, C. Y. Xu and K. F. Cao: An effective community detection method based on one-dimensional “attraction” in network science. Int. J. Modern Physics C 31 (2020), 5, 2050071.   DOI:10.1142/S0129183120500710
  55. K. R. Žalik and B. Žalik: Node attraction-facilitated evolution algorithm for community detection in networks. Soft Comput. 23 (2019), 6135–-6143.   DOI:10.1007/s00500-018-3267-x
  56. H. Zhou, B. Xi, Y. Zhang, J. Li and F. Zhang: A graph clustering algorithm using attraction-force similarity for community detection. IEEE Access 7 (2019), 13683-13692.   DOI: 10.1109/ACCESS.2018.2889312
  57. Dolphins network dataset available at (accessed June 2025):     github.com/csdashes/GraphStreamCommunityDetection/blob/master/data/dolphins.gml
  58. W. W. Zachary: Karate club network. Available via NetworkX documentation https://networkx.org/documentation/stable/reference/generated/networkx.generators. social.karate_club_graph.html,   accessed June 2025.
  59. Political books network dataset available at (accessed June 2025):     https://public.websites.umich.edu/$\sim$mejn/netdata/
  60. Facebook social network dataset available at (accessed June 2025):     http://snap.stanford.edu/data/
  61. Netscience co-authorship network dataset available at (accessed June 2025):     https://public.websites.umich.edu/$\sim$mejn/netdata/