An Iterated Heuristic Community Detection Algorithm for Social Networks Based on Centrality and Similarity Measures
Received: 4 March 2025 | Revised: 29 April 2025 | Accepted: 8 May 2025 | Online: 21 May 2025
Corresponding author: Ali Chenaoui
Abstract
Community detection is a crucial analytical approach to comprehend the structure and functionality of intricate networks, which are frequently conceptualized as graphical representations. This problem is extremely difficult and has not yet been satisfactorily solved. It is believed that neighbors may strongly surround a community's central or leader node, and that the centers of two communities may be far apart. Furthermore, it is postulated that the similarity between nodes within the same community is greater than that observed between nodes belonging to different communities. Thus, it is evident that local and global structural information is important in community detection. This paper presents an iterative heuristic algorithm for community detection in social networks using centrality and similarity measures called HCCS, which consists of four main steps: parameter initialization, leader nodes' selection, communities' formation, and post-processing. The main contributions are as follows: first, both local and global information about the network is considered, and then a heuristic formula for measuring the similarity between two nodes is redefined. The leader nodes are identified based on two criteria: degree and distance. During the community formation phase, the degree of similarity between the nodes is quantified using the heuristic formula. The nodes are then assigned to the same community once they reach maximum similarity. The postprocessing phase entails the integration of two communities when the modularity increment is positive, reaching its maximum when the two communities are merged. Experiments on real networks demonstrate the effectiveness of the proposed approach.
Keywords:
community detection, social network, centrality, similarity measures, heuristic, modularityDownloads
References
J. Scott, Social Network Analysis: A Handbook, 2nd ed. SAGE Publications Ltd, 2000.
M. Girvan and M. E. J. Newman, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, Jun. 2002. DOI: https://doi.org/10.1073/pnas.122653799
M. E. J. Newman, "Modularity and community structure in networks," Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577–8582, Jun. 2006. DOI: https://doi.org/10.1073/pnas.0601602103
V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, Jul. 2008, Art. no. P10008. DOI: https://doi.org/10.1088/1742-5468/2008/10/P10008
A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," Physical Review E, vol. 70, no. 6, Dec. 2004, Art. no. 066111. DOI: https://doi.org/10.1103/PhysRevE.70.066111
B. Zarei and M. R. Meybodi, "Detecting community structure in complex networks using genetic algorithm based on object migrating automata," Computational Intelligence, vol. 36, no. 2, pp. 824–860, 2020. DOI: https://doi.org/10.1111/coin.12273
S. Fortunato and M. Barthélemy, "Resolution limit in community detection," Proceedings of the National Academy of Sciences, vol. 104, no. 1, pp. 36–41, Jan. 2007. DOI: https://doi.org/10.1073/pnas.0605965104
M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical Review E, vol. 74, no. 3, Sep. 2006, Art. no. 036104. DOI: https://doi.org/10.1103/PhysRevE.74.036104
U. N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Physical Review E, vol. 76, no. 3, Sep. 2007, Art. no. 036106. DOI: https://doi.org/10.1103/PhysRevE.76.036106
B. Zarei, M. R. Meybodi, and B. Masoumi, "Detecting community structure in signed and unsigned social networks by using weighted label propagation," Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 30, no. 10, Oct. 2020, Art. no. 103118. DOI: https://doi.org/10.1063/1.5144139
P. Pons and M. Latapy, "Computing Communities in Large Networks Using Random Walks," in Computer and Information Sciences - ISCIS 2005, 2005, pp. 284–293. DOI: https://doi.org/10.1007/11569596_31
M. Rosvall and C. T. Bergstrom, "Maps of random walks on complex networks reveal community structure," Proceedings of the National Academy of Sciences, vol. 105, no. 4, pp. 1118–1123, Jan. 2008. DOI: https://doi.org/10.1073/pnas.0706851105
A. Grover and J. Leskovec, "node2vec: Scalable Feature Learning for Networks," in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, May 2016, pp. 855–864. DOI: https://doi.org/10.1145/2939672.2939754
T. N. Kipf and M. Welling, "Semi-Supervised Classification with Graph Convolutional Networks." arXiv, Feb. 22, 2017.
B. Zarei, M. R. Meybodi, and B. Masoumi, "A New Evolutionary Model Based on Cellular Learning Automata and Chaos Theory," New Generation Computing, vol. 40, no. 1, pp. 285–310, Apr. 2022. DOI: https://doi.org/10.1007/s00354-022-00159-1
G. Palla, I. Derényi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature, vol. 435, no. 7043, pp. 814–818, Jun. 2005. DOI: https://doi.org/10.1038/nature03607
P. Goyal, S. R. Chhetri, and A. Canedo, "dyngraph2vec: Capturing network dynamics using dynamic graph representation learning," Knowledge-Based Systems, vol. 187, Jan. 2020, Art. no. 104816. DOI: https://doi.org/10.1016/j.knosys.2019.06.024
B. Zarei, B. Arasteh, M. Asadi, V. Majidnezhad, S. T. Afshord, and A. Bouyer, "Multiplex Community Detection in Social Networks Using a Chaos-Based Hybrid Evolutionary Approach," Complexity, vol. 2024, no. 1, 2024, Art. no. 1016086. DOI: https://doi.org/10.1155/2024/1016086
B. Zarei, M. R. Meybodi, and B. Masoumi, "Chaotic memetic algorithm and its application for detecting community structure in complex networks," Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 30, no. 1, Jan. 2020, Art. no. 013125. DOI: https://doi.org/10.1063/1.5120094
G. R. Abdi, A. H. Refahi Sheikhani, S. Kordrostami, B. Zarei, and M. Falah Rad, "Identifying communities in complex networks using learning-based genetic algorithm," Ain Shams Engineering Journal, vol. 15, no. 12, Dec. 2024, Art. no. 103031. DOI: https://doi.org/10.1016/j.asej.2024.103031
S. Su, J. Guan, B. Chen, and X. Huang, "Nonnegative Matrix Factorization Based on Node Centrality for Community Detection," ACM Transactions on Knowledge Discovery Data, vol. 17, no. 6, Oct. 2023, Art. no. 84. DOI: https://doi.org/10.1145/3578520
C. Feng, J. Ye, J. Hu, and H. L. Yuan, "Community Detection by Node Betweenness and Similarity in Complex Network," Complexity, vol. 2021, no. 1, 2021, Art. no. 9986895. DOI: https://doi.org/10.1155/2021/9986895
X. You, Y. Ma, and Z. Liu, "A three-stage algorithm on community detection in social networks," Knowledge-Based Systems, vol. 187, Jan. 2020, Art. no. 104822. DOI: https://doi.org/10.1016/j.knosys.2019.06.030
J. Lei, W. X. Juan, and Z. Yong, "The independence of the centrality for community detection," International Journal of Modern Physics C, vol. 29, no. 07, Jul. 2018, Art. no. 1850060. DOI: https://doi.org/10.1142/S0129183118500602
S. Ahajjam and H. Badir, "Community Detection in Social Networks," in Principles of Social Networking: The New Horizon and Emerging Challenges, A. Biswas, R. Patgiri, and B. Biswas, Eds. Springer, 2022, pp. 91–107. DOI: https://doi.org/10.1007/978-981-16-3398-0_5
J. Sheykhzadeh, B. Zarei, and F. Soleimanian Gharehchopogh, "Community Detection in Social Networks Using a Local Approach Based on Node Ranking," IEEE Access, vol. 12, pp. 92892–92905, 2024. DOI: https://doi.org/10.1109/ACCESS.2024.3420109
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. American Elsevier Publishing Company, 1976. DOI: https://doi.org/10.1007/978-1-349-03521-2
K. Mouley and M. A. Tahraoui, "Locating the Source of Information in Social Networks using Critical Nodes," Engineering, Technology & Applied Science Research, vol. 15, no. 1, pp. 19136–19142, Feb. 2025. DOI: https://doi.org/10.48084/etasr.9283
J. Scott, Social Networks: Critical Concepts in Sociology. Taylor & Francis, 2002.
A. Bavelas, "Communication patterns in task-oriented groups," Journal of the Acoustical Society of America, vol. 22, pp. 725–730, 1950. DOI: https://doi.org/10.1121/1.1906679
L. C. Freeman, "A Set of Measures of Centrality Based on Betweenness," Sociometry, vol. 40, no. 1, pp. 35–41, 1977. DOI: https://doi.org/10.2307/3033543
P. Bonacich, "Power and Centrality: A Family of Measures," American Journal of Sociology, vol. 92, no. 5, pp. 1170–1182, Mar. 1987. DOI: https://doi.org/10.1086/228631
P. Jaccard, "Étude comparative de la distribution florale dans une portion des Alpes et du Jura," Bulletin de la Societe Vaudoise des Sciences Naturelles, vol. 37, no. 142, pp. 547–579, 1901.
G. Salton, Introduction to Modern Information Retrieval. McGraw-Hill, 1983. DOI: https://doi.org/10.1145/182.358466
M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physical Review E, vol. 69, no. 2, Feb. 2004, Art. no. 026113. DOI: https://doi.org/10.1103/PhysRevE.69.026113
L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas, "Comparing community structure identification," Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 09, Jun. 2005, Art. no. P09008. DOI: https://doi.org/10.1088/1742-5468/2005/09/P09008
D. Lusseau, "The emergent properties of a dolphin social network," Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, pp. S186–S188, Nov. 2003. DOI: https://doi.org/10.1098/rsbl.2003.0057
W. W. Zachary, "An Information Flow Model for Conflict and Fission in Small Groups," Journal of Anthropological Research, vol. 33, no. 4, pp. 452–473, Dec. 1977. DOI: https://doi.org/10.1086/jar.33.4.3629752
L. A. Adamic and N. Glance, "The political blogosphere and the 2004 U.S. election: divided they blog," in Proceedings of the 3rd international workshop on Link discovery, May 2005, pp. 36–43. DOI: https://doi.org/10.1145/1134271.1134277
P. M. Gleiser and L. Danon, "Community structure in jazz," Advances in Complex Systems, vol. 06, no. 04, pp. 565–573, Dec. 2003. DOI: https://doi.org/10.1142/S0219525903001067
D. E. Knuth, The Stanford GraphBase: a platform for combinatorial computing, First paperback printing. ACM Press, 2009.
D. J. Watts and S. H. Strogatz, "Collective dynamics of ‘small-world’ networks," Nature, vol. 393, no. 6684, pp. 440–442, Jun. 1998. DOI: https://doi.org/10.1038/30918
R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas, "Self-similar community structure in a network of human interactions," Physical Review E, vol. 68, no. 6, Dec. 2003, Art. no. 065103. DOI: https://doi.org/10.1103/PhysRevE.68.065103
Downloads
How to Cite
License
Copyright (c) 2025 Ali Chenaoui, Mohammed Amin Tahraoui
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
