A review: Multi-Objective Algorithm for Community Detection in Complex Social Networks
DOI:
https://doi.org/10.21928/uhdjst.v9n1y2025.pp44-54Keywords:
Meta-heuristic, Multi-Objective Algorithm, Community Detection, Complex Networks, Optimization and ObjectiveAbstract
Recently, research on multi-objective optimization algorithms for community detection in complex networks has grown considerably. Community detection based on multi-objective algorithms (MOAs) in complex social networks is a fundamental scheduler, and it supports knowing the dynamics of a society, finding influential groups, and improving information dissemination. The traditional methodologies often cannot cope with the features that real-world network usually present, related to optimizing various and sometimes conflicting objectives. This paper provides an overview of some recent works on MOAs for community detection in complex social networks. This paper will explore the balance of the reached objectives, such as modularity, community size, and edge density. Which are analyzed by 15 different approaches in order to choose from works published during the period 2019–2024. These strengths and limitations of various MOAs are reviewed with a comparative analysis to provide insights into both the effectiveness and computational efficiency of these methods. The present trends and future research are discussed that underline the need for the development of solutions to be more adaptive and scalable in coping with the gradually increasing complexity of social networks.
References
S. E. De Leon-Aldaco, H. Calleja and J. Aguayo Alquicira. “Metaheuristic optimization methods applied to power converters: A review”. IEEE Transactions on Power Electronics, vol. 30, no. 12, pp. 6791-6803, 2015.
A. M. Nassef, M. A. Abdelkareem, H. M. Maghrabie and A. Baroutaji. “Review of metaheuristic optimization algorithms for power systems problems”. Sustainability, vol. 15, no. 12, p. 9434, 2023.
K. Diao, X. Sun, G. Bramerdorfer, Y. Cai, G. Lei and L. Chen. “Design optimization of switched reluctance machines for performance and reliability enhancements: A review”. Renewable and Sustainable Energy Reviews, vol. 168, p. 112785, 2022.
R. H. Stewart, T. S. Palmer and B. DuPont. “A survey of multi-objective optimization methods and their applications for nuclear scientists and engineers”. Progress in Nuclear Energy, vol. 138, p. 103830, 2021.
S. Chand and M. Wagner. “Evolutionary many-objective optimization: A quick-start guide”. Surveys in Operations Research and Management Science, vol. 20, no. 2, pp. 35-42, 2015.
K. Deng. “An efficient multi-objective community detection algorithm in complex networks”. Tehnicki vjesnik - Technical Gazette, vol. 22, no. 2, pp. 319-328, 2015.
P. Bedi and C. Sharma. “Community detection in social networks”. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 6, no. 3, pp. 115-135, 2016.
B. S. Khan and M. A. Niazi. “Network community detection: A review and visual survey”. arXiv preprint arXiv:1708.00977, 2017.
A. Clauset, M. E. J. Newman and C. Moore. “Finding community structure in very large networks”. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, vol. 70, no. 6, pp. 1550-2376, 2004.
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, 2008.
A. L. Barabási. “Scale-free networks: A decade and beyond”. Science, vol. 325, no. 5939, pp. 412-413, 2009.
S. Fortunato. “Community detection in graphs”. Physics Reports, vol. 486, no. 3-5, pp. 75-174, 2010.
M. E. J. Newman. “Communities, modules and large-scale structure in networks”. Nature Physics, vol. 8, no. 1, pp. 25-31, 2012.
I. A. Doush, W. A. B. Alrashdan, M. A. Al-Betar and M. A. Awadallah. “Community detection in complex networks using multi-objective bat algorithm”. International Journal of Mathematical Modelling and Numerical Optimisation, vol. 10, no. 2, pp. 123-140, 2020.
Z. Beheshti and S. M. H. Shamsuddin. “A review of population-based meta-heuristic algorithms”. International Journal of Advances in Soft Computing and Its Applications, vol. 5, no. 1, pp. 1-35, 2013.
R. K. Congram, C. N. Potts and S. L. van de Velde. “An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem”. INFORMS Journal on Computing, vol. 14, no. 1, pp. 52-67, 2002.
F. Glover and C. McMillan. “The general employee scheduling problem. An integration of MS and AI”. Computers and Operations Research, vol. 13, no. 5, pp. 563-573, 1986.
A. H. Hosseinian and V. Baradaran. “A multi-objective multi-agent optimization algorithm for the community detection problem”. Journal of Information Systems and Telecommunication, vol. 6, no. 1, pp. 169-179, 2019.
M. M. Abdulrahman, A. D. Abood and B. A. Attea. “An Enhanced Multi-Objective Evolutionary Algorithm with Decomposition for Signed Community Detection Problem”. In: Presented at the 2020 2nd Annual International Conference on Information and Sciences (AICIS). Fallujah, Iraq, 2020.
Z. Liu, Y. Ma and X. Wang. “A compression-based multi-objective evolutionary algorithm for community detection in social networks”. IEEE Access, vol. 8, pp. 62137-62150, 2020.
T. Shaik, V. Ravi and K. Deb. “Evolutionary multi-objective optimization algorithm for community detection in complex social networks”. SN Computer Science, vol. 2, pp. 1-25, 2021.
Y. Su, K. Zhou, X. Zhang, R. Cheng and C. Zheng. “A parallel multi-objective evolutionary algorithm for community detection in large-scale complex networks”. Information Sciences, vol. 576, pp. 374-392, 2021.
M. E. A. Alkhalec Tharwat, M. F. M. Fudzee, S. Kasim, A. A. Ramli and M. K. Ali. “Multi-objective NSGA-II based community detection using dynamical evolution social network”. International Journal of Electrical and Computer Engineering, vol. 11, no. 5, pp. 4502-4512, 2021.
S. Pérez-Peló, J. Sánchez-Oro, A. Gonzalez-Pardo and A. Duarte. “A fast variable neighborhood search approach for multi-objective community detection”. Applied Soft Computing, vol. 112, p. 107838, 2021.
A. D. Abbood, A. A. Bara’a, A. A. Hasan and R. K. Everson. “A Multi- Objective Evolutionary Algorithm with Neighbour Nodecentrality for Community Detection in Complex Networks”. Researchsquare, Durham, NC, 2022.
S. Yang, Q. Li, W. Wei and Y. Zhang. “A multi-objective evolutionary algorithm based on mixed encoding for community detection”. Multimedia Tools and Applications, vol. 82, no. 9, pp. 14107- 14122, 2023.
W. Zhu, H. Li and W. Wei. “A two-stage multi-objective evolutionary algorithm for community detection in complex networks”. Mathematics, vol. 11, no. 12, p. 2702, 2023.
L. Zhang, H. Yang, S. Yang and X. Zhang. “A macro-micro population-based co-evolutionary multi-objective algorithm for community detection in complex networks [research frontier]”. IEEE Computational Intelligence Magazine, vol. 18, no. 3, pp. 69-86, 2023.
C. Li. “Multi-objective optimization overlapping community detection algorithm based on subgraph structure”. Frontiers in Computing and Intelligent Systems, vol. 3, no. 3, pp. 110-112, 2023.
L. Yu, X. Guo, D. Zhou and J. Zhang. “A multi-objective pigeon-inspired optimization algorithm for community detection in complex networks”. Mathematics, vol. 12, no. 10, p. 1486, 2024.
L. Cai, J. Zhou and D. Wang. “Two-stage multi-objective evolutionary algorithm for overlapping community discovery”. PeerJ Computer Science, vol. 10, p. e2185, 2024.
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.
J. Yang and J. Leskovec. “Defining and Evaluating Network Communities based on Ground-truth”. In: MDS ‘12: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pp. 1-8, 2012.
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, 1977.
D. Lusseau. “The emergent properties of a dolphin social network”. Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, no. Suppl_2, pp. S186-S188, 2003.
M. E. J. Newman. “Modularity and community structure in networks”. Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577-8582, 2006.
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, 2002.
K. D. Bollacker, S. Lawrence and C. L. Giles. “CiteSeer: An Autonomous Web Agent for Automatic Retrieval and Identification of Interesting Publications”. In: Proceedings of 2nd International ACM Conference on Autonomous Agents, ACM Press, pp. 116-123, 1998.
J. Leskovec, J. Kleinberg and C. Faloutsos. “Graph evolution: Densification and shrinking diameters”. ACM transactions on Knowledge Discovery from Data, vol. 1, no. 1, p. 2-es, 2007.
J. Leskovec and A. Krevl. 2014. “SNAP Datasets: Large Network Dataset Collection”. Available from: https://snap.stanford.edu/data [Last accessed on 2024 Jul 15].
J. Leskovec, K. J. Lang, A. Dasgupta and M. W. Mahoney. “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters”. Internet Mathematics, vol. 6, no. 1, pp. 29-123, 2009.
M. E. J. Newman. “Fast algorithm for detecting community structure in networks”. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, vol. 69, no. 6, p. 066133, 2004.
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, pp. P09008-P09008, 2005.
J. C. Devi and E. Poovammal. “An analysis of overlapping community detection algorithms in social networks”. Procedia Computer Science, vol. 89, pp. 349-358, 2016.
P. B. Jadhav and V. B. Burra. “Deep learning in social networks for overlappering community detection”. International Journal on Recent and Innovation Trends in Computing and Communication, vol. 10, no. 12, pp. 35-43, 2022.
Z. Liu, Y. Dong, X. Zhao and B. Zhang. “A dynamic social network data publishing algorithm based on differential privacy”. Journal of Information Security, vol. 8, no. 4, pp. 328-338, 2017.
J. MacQueen. “Some Methods for Classification and Analysis of Multivariate Observations”. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press, Berkeley, 1967.
C. M. Fiduccia and R. M. Mattheyses. “A Linear-time Heuristic for Improving Network Partitions”. In: Papers on Twenty-five years of Electronic Design Automation, pp. 241-247, 1988.
J. Shi and J. Malik. “Normalized cuts and image segmentation”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, 2000.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner and G. Monfardini. “The graph neural network model”. IEEE Transactions on Neural Networks and Learning Systems, vol. 20, no. 1, pp. 61-80, 2009.
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, p. P10008, 2008.
B. W. Kernighan and S. Lin. “An efficient heuristic procedure for partitioning graphs”. The Bell System Technical Journal, vol. 49, no. 2, pp. 291-307, 1970.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Mariwan Wahid Ahmed, Hama Ali
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
