Detection of communities by modularity matrix

Document Type : Full Length Article

Authors

1 Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan, I. R. Iran

2 Faculty of Computer, Network and Communication , Imam Hossein Comprehensive University, Tehran, I. R. Iran

Abstract

One of the most discussed topics in social networks is community detection. As these networks become more complex, spectral graph properties and graph-related structures are increasingly used for community detection. In this paper, we examine these properties of the modularity matrix, such as the eigenvalues of the modularity matrix structure of some specific graphs, modularity energy, and the Estrada modularity index. Additionally, we study the bounds for the energy and Estrada indices. Furthermore, considering the significant issue of estimating the number of communities in some community detection algorithms in networks, we focus on the modularity eigenvalues.

Graphical Abstract

Detection of communities by modularity matrix

Keywords

Main Subjects


[1] A. R. Ashrafi, G. H. Fath-Tabar, Bounds on the Estrada index of ISR (4, 6)-fullerenes, Appl. Math.
Lett. 24 (2011) 337–339. https://doi.org/10.1016/j.aml.2010.10.018
[2] R. Bhattacharya, N. K. Nagwani, S. Tripathi, A community detection model using node embedding approach and graph convolutional network with clustering technique, Decis. Anal. J. 9 (2023)
100362. https://doi.org/10.1016/j.dajour.2023.100362
[3] M. Bolla, Penalized versions of the Newman-Girvan modularity and their relation to normalized cuts and k-means clustering, Phys. Rev. E 84 (2011) 016108.
https://doi.org/10.1103/PhysRevE.84.016108
[4] M. Bolla, B. Bullins, S. Chaturapruek, S. Chen, K. Friedl, Spectral properties of modularity matrices, Linear Algebra Appl. 473 (2015) 359–376. https://doi.org/10.1016/j.laa.2014.10.039
[5] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New York, 2008. https://doi.org/10.1007/978-
1-84628-970-5
[6] S. P. Borgatti, M. G. Everett, J. C. Johnson, Analyzing Social Networks, SAGE Publications, London,
2022. https://doi.org/10.1080/0022250x.2015.1053371
[7] G. Budel, P. Van Mieghem, Detecting the number of clusters in a network, J. Complex Netw. 8
(2020) cnaa047. https://doi.org/10.1093/comnet/cnaa047
[8] F. Chung, Spectral Graph Theory, American Mathematical Society, Providence, 1997.
https://doi.org/10.1090/cbms/092
[9] D. Cvetkovic, S. Simi ´ c, Graph spectra in computer science, Linear Algebra Appl. 434 (2011) 1545– ´
1562. https://doi.org/10.1016/j.laa.2010.11.035
[10] A. K. Dey, Y. Tian, Y. R. Gel, Community detection in complex networks: From statistical foundations to data science applications, WIREs Comput. Stat. 14 (2022) e1566.
https://doi.org/10.1002/wics.1566
[11] E. Estrada, P. A. Knight, A First Course in Network Theory, Oxford University Press, Oxford, 2015.
https://doi.org/10.1007/s00362-017-0961-1
[12] D. Fasino, F. Tudisco, An algebraic analysis of the graph modularity, SIAM J. Matrix Anal. Appl.
35 (2014) 997–1018. https://doi.org/10.1137/130943455
[13] D. Fasino, F. Tudisco, Modularity bounds for clusters located by leading eigenvectors of the normalized modularity matrix, J. Math. Ineq. 11(2016) 701–714. https://doi.org/10.7153/jmi-11-56
[14] G. H. Fath-Tabar, A. R. Ashrafi, New upper bounds for Estrada index of bipartite graphs, Linear
Algebra Appl. 435 (2011) 2607–2611. https://doi.org/10.1016/j.laa.2011.01.034
[15] G. H. Fath-Tabar, A. R. Ashrafi, I. Gutman, Note on Laplacian energy of graphs, Bull. Acad. Serbe
Sci. Arts (Cl. Sci. Math. Natur.) 33 (2008) 1–10. http://eudml.org/doc/258685
[16] G. H. Fath-Tabar, A. R. Ashrafi, I. Gutman, Note on Estrada and L-Estrada indices of graphs, Bull.
Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.) 139 (2009) 1–16. http://eudml.org/doc/253352
[17] M. Fiedler, Algebraic connectivity of graphs, Czechoslov. Math. J. 23 (1973) 298–305.
https://doi.org/10.21136/CMJ.1973.101168
[18] I. Gutman, The energy of a graph, Ber. Math.-Statist. Sekt. Forsch. Graz 103 (1978) 1–22.
[19] I. Gutman, N. Trinajstic, Graph theory and molecular orbitals, in: A. Graovac (Ed.), Top- ´
ics in Molecular Organization and Engineering, Vol. 2, Springer, Dordrecht, 2005, pp. 49–93.
https://doi.org/10.1007/3-540-06399-4 5
[20] I. Gutman, X. Li, J. Zhang, Graph energy, in: M. Dehmer, F. Emmert-Streib (Eds.), Analysis
of Complex Networks: From Biology to Linguistics, Wiley-VCH, Weinheim, 2009, pp. 145–174.
https://doi.org/10.1002/9783527627981.ch7
[21] R. A. Horn, C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge,
2012. https://doi.org/10.1017/CBO9781139020411
[22] H. Jiang, C. Meyer, Relations between adjacency and modularity graph partitioning, in: H.
Kashima, T. Ide, W. Peng (Eds.), Advances in Knowledge Discovery and Data Mining, PAKDD
2023, Lecture Notes in Computer Science, vol. 13936, Springer, Cham, 2023, pp. 547–559.
https://doi.org/10.1007/978-3-031-33377-4 15
[23] D. Jin, B. Yang, C. Liu, D. He, J. Zhang, W. Zhang, A survey of community detection approaches:
From statistical modeling to deep learning, IEEE Trans. Knowl. Data Eng. 35 (2021) 1149–1170.
https://doi.org/10.1109/TKDE.2021.3104155
[24] D. Koutra, M. van Leeuwen, C. Plant, M. M. Gaber, E. Ntoutsi, A. Schubert, A. Zimek (Eds.),
Machine Learning and Knowledge Discovery in Databases: Research Track, ECML PKDD 2023,
Proceedings, Part V, Lecture Notes in Computer Science, vol. 14173, Springer, Cham, 2023.
https://doi.org/10.1007/978-3-031-43418-1
[25] J. Li, Z. Wang, K. Yu, J. Cao, Y. Wang, A comprehensive review of community detection in graphs,
Neurocomputing 576 (2024) 128169. https://doi.org/10.1016/j.neucom.2024.128169
[26] R. Nasiri, G. H. Fath-Tabar, A. Gholami, Z. Yarahmadi, Resolvent Estrada and signless Laplacian Estrada indices of graphs, MATCH Commun. Math. Comput. Chem. 77 (2017) 157–176.
https://match.pmf.kg.ac.rs/electronic versions/Match77/n1/match77n1 157-176.pdf
[27] M. E. J. Newman, Detecting community structure in networks, Eur. Phys. J. B 38 (2004) 321–330.
https://doi.org/10.1140/epjb/e2004-00124-y
[28] M. E. J. Newman, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004)
026113. https://doi.org/10.1103/PhysRevE.69.026113
[29] M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford, 2010.
https://doi.org/10.1093/acprof:oso/9780199206650.001.0001
[30] M. E. J. Newman, Community detection in networks: Modularity optimization and maximum
likelihood are equivalent, arXiv:1606.02319 (2016). https://doi.org/10.48550/arXiv.1606.02319
[31] M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West, R. Lambiotte, Different approaches
to community detection, in: P. Doreian, V. Batagelj, A. Ferligoj (Eds.), Advances in Network Clustering and Blockmodeling, John Wiley & Sons, Hoboken, 2019, pp. 105–119.
https://doi.org/10.1002/9781119483298.ch4
[32] L. Tang, H. Liu, Community Detection and Mining in Social Media, Springer, Cham, 2022.
https://doi.org/10.1007/978-3-031-01900-5
[33] P. Van Mieghem, Graph Spectra for Complex Networks, Cambridge University Press, Cambridge,
2023. https://doi.org/10.1017/CBO9780511921681

Volume 10, Issue 4
December 2025
Pages 359-374
  • Receive Date: 26 January 2025
  • Revise Date: 13 March 2025
  • Accept Date: 21 April 2025
  • First Publish Date: 28 November 2025
  • Publish Date: 01 December 2025