Improving Modularity Regularization Techniques for Estimating Structures in Complex Network

Authors

DOI:

https://doi.org/10.30526/38.3.3728

Keywords:

Community detection, likelihood function, model selection, Bayesian Information Criterion, Stochastic Block Models.

Abstract

Complex systems in the real world have networks differ significantly from random graphs and have non-trivial structures. In fact, they have a community structure that needs to be recognized and recovered. The stochastic block models (SBMs) are popular models for community detection in networks, where nodes are divided into groups based on their connectivity patterns. Maximum likelihood estimation is a common method for estimating the parameters of SBMs. In this paper, a model selection for stochastic block models is presented based on the optimization of the log-likelihood function to find the best number of communities K detected by the regularized convex modularity maximization method. This work deals with many assumptions on K because it is necessary to study the behavior of the network and the best optimum K is assumed to select the best partition over the AIC, BIC metric. The proposed model selection method is presented in an algorithm that is implemented for both real and synthetic networks. This method enables the detection of networks with small communities that are more likely to provide a better fit to the observed data.

Author Biographies

  • Samaa F. Ibraheem , Department of Mathematics, College of Applied Science, University of Technology, Baghdad, Iraq.

    Department of Mathematics, College of Applied Science, University of Technology, Baghdad, Iraq.

  • Basad Al-Sarray, Department of Computer Science, College of Science, University of Baghdad, Baghdad, Iraq

    Department of Computer Science, College of Science, University of Baghdad, Baghdad, Iraq

References

1. Karrer B., Newman M.E.J. Stochastic blockmodels and community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys 2011;83(1):1–11.https://doi.org/10.1103/PhysRevE.83.016107

2. Abdul-Emeer S.S. An evolutionary bi-clustering algorithm for community detection in social networks. Iraqi J Sci 2016;57(3):2111–2120.

3. Mohammed S.K., Taha M.M., Taha E.M., Mohammad M.N.A. Cluster analysis of biochemical markers as predictor of COVID-19 severity. Baghdad Sci J 2022;19(6):1423–1429. https://doi.org/10.21123/BSJ.2022.7454

4. Li X., Chen Y., Xu J. Convex relaxation methods for community detection. Stat Sci 2021;36(1):2–15. https://doi.org/10.1214/19-STS715

5. Holland P.W., Laskey K.B., Leinhardt S. Stochastic blockmodels: first steps. Soc Networks 1983;5(2):109–137. https://doi.org/10.1016/0378-8733(83)90021-7.

6. Alsaleem N.Y.A., Alsaleem M.Y.A., Zakar N.A. Network performance analysis based on network simulator NS-2. Ibn Al-Haitham J Pure Appl Sci 2018;31:222–229.

7. Hassan F., Behadili S.F. Modeling social networks using data mining approaches—Review. Iraqi J Sci 2022;63(3):1313–1338. https://doi.org/10.24996/ijs.2022.63.3.35

8. Wang Y.X.R., Bickel P.J. Likelihood-based model selection for stochastic block models. Ann Stat 2017;45(2):500–528. https://doi.org/10.1214/16-AOS1457

9. Al-obedy J.A.N. Posterior estimates for the parameter of the Poisson distribution by using two different loss functions. Ibn Al-Haitham J Pure Appl Sci 2022;35(1):60–72. https://doi.org/10.30526/35.1.2800

10. Abbe E. Community detection and stochastic block models: recent developments. J Mach Learn Res 2017;18(177):1–86.

11. Von Luxburg U. A tutorial on spectral clustering. Stat Comput 2007;17(4):395–416. https://doi.org/10.1007/s11222-007-9033-z

12. Dabbs B., Junker B. Comparison of cross-validation methods for stochastic block models. arXiv Methodol 2016. http://arxiv.org/abs/1605.03000

13. Newman M.E.J. Networks: an introduction. Oxford Univ Press 2018. ISBN: 9780198805090.

14. Nishii R. Maximum likelihood principle and model selection when the true model is unspecified. J Multivar Anal 1988;27(2):392–403. https://doi.org/10.1016/0047-259X(88)90137-6

15. Ponveni P., Visumathi J. A review on community detection algorithms and evaluation measures in social networks. 2021 7th Int Conf Adv Comput Commun Syst 2021:1892–1899. https://doi.org/10.1109/ICACCS51430.2021.9441868

16. Yaqoob A.F., Al-Sarray B. Community detection under stochastic block model likelihood optimization via tabu search – Fuzzy C-mean method for social network data. Iraqi J Sci 2020;61(10):2695–2704. https://doi.org/10.24996/ijs.2020.61.10.27

17. Funke T., Becker T. Stochastic block models: a comparison of variants and inference methods. PLoS One 2019;14(4):e0215296. https://doi.org/10.1371/journal.pone.0215296

18. Abbe E., Sandon C. Community detection in general stochastic block models: fundamental limits and efficient algorithms for recovery. Proc Annu IEEE Symp Found Comput Sci 2015;2015:670–688. https://doi.org/10.1109/FOCS.2015.47

19. Daudin J., Picard F., Robin S. A mixture model for random graphs. Stat Comput 2008;18(2):173–183.

20. Ibraheem S.F., Al-Sarray B. A heuristic technique for community detection in complex networks. AIP Conf Proc 2024;3097:080012. https://doi.org/10.1063/5.0209446

21. Chen Y., Li X., Xu J. Convexified modularity maximization for degree-corrected stochastic block models. Ann Stat 2018;46(4):573–1602. https://doi.org/10.1214/17-AOS1595

22. Newman M.E.J. Fast algorithm for detecting community structure in networks. Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Top 2004;69(6):5. https://doi.org/10.1103/PhysRevE.69.066133

23. Danon L., Díaz-Guilera A., Arenas A. The effect of size heterogeneity on community identification in complex networks. J Stat Mech Theory Exp 2006;2006(11):P11010. https://doi.org/10.1088/1742-5468/2006/11/P11010

24. Cai T.T., Li X. Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann Stat 2015;43(3):1027–1059. https://doi.org/10.1214/14-AOS1290

25. Zhou Z., Amini A.A. Analysis of spectral clustering algorithms for community detection: the general bipartite setting. J Mach Learn Res 2019;20:1–45.

26. Yan B., Sarkar P., Cheng X. Provable estimation of the number of blocks in block models. Int Conf Artif Intell Stat AISTATS 2018;84:1185–1194.

27. Jin D., Zhao Z., Zhang Y., Zheng V.W., Yu S., Li Y. A survey of community detection approaches: from statistical modeling to deep learning. IEEE Trans Knowl Data Eng 2023;35(2):1149–1170. https://doi.org/10.1109/TKDE.2021.3104155

28. Christensen A.P., Garrido L.E., Guerra-Peña K., Golino H. Comparing community detection algorithms in psychological data: a Monte Carlo simulation. 2020:1–25.

29. Ren R., Shao J., Bishop A.N., Zheng W.X. Modeling and detecting communities in node attributed networks. IEEE Trans Knowl Data Eng 2022. http://arxiv.org/abs/2101.03280

30. Ghasemian A. Limits of model selection, link prediction, and community detection. PhD Thesis, University of Colorado at Boulder; 2019.

Downloads

Published

20-Jul-2025

Issue

Section

Mathematics

How to Cite

[1]
Ibraheem , S.F. and Al-Sarray, B. 2025. Improving Modularity Regularization Techniques for Estimating Structures in Complex Network. Ibn AL-Haitham Journal For Pure and Applied Sciences. 38, 3 (Jul. 2025), 325–335. DOI:https://doi.org/10.30526/38.3.3728.