On the relation between graph Ricci curvature and community structure

Sathya Rengaswami; Theodora Bourni; Vasileios Maroulas; Sathya Rengaswami; Theodora Bourni; Vasileios Maroulas

doi:10.3934/mine.2025008

Mathematics in Engineering

2025, Volume 7, Issue 2: 178-193. doi: 10.3934/mine.2025008

Previous Article Next Article

Research article

On the relation between graph Ricci curvature and community structure

Department of Mathematics, University of Tennessee, Knoxville TN 37916, USA

Received: 20 June 2024 Revised: 22 January 2025 Accepted: 07 April 2025 Published: 16 April 2025

The connection between curvature and topology is a very well-studied theme in the subject of differential geometry. By suitably defining curvature on networks, the study of this theme has been extended into the domain of network analysis as well. In particular, this has led to curvature-based community detection algorithms. In this paper, we reveal the relation between community structure of a network and the curvature of its edges. In particular, we give apriori bounds on the curvature of intercommunity edges of a graph.
- discrete curvature,
- Ollivier Ricci curvature,
- graph curvature,
- optimal transport,
- community structure,
- community detection
Citation: Sathya Rengaswami, Theodora Bourni, Vasileios Maroulas. On the relation between graph Ricci curvature and community structure[J]. Mathematics in Engineering, 2025, 7(2): 178-193. doi: 10.3934/mine.2025008

Related Papers:

Abstract

The connection between curvature and topology is a very well-studied theme in the subject of differential geometry. By suitably defining curvature on networks, the study of this theme has been extended into the domain of network analysis as well. In particular, this has led to curvature-based community detection algorithms. In this paper, we reveal the relation between community structure of a network and the curvature of its edges. In particular, we give apriori bounds on the curvature of intercommunity edges of a graph.

References

[1]	F. Bauer, J. Jost, S. Liu, Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, arXiv, 2013. https://doi.org/10.48550/arXiv.1105.3803
[2]	D. Cushing, S. Kamtue, J. Koolen, S. Liu, F. Münch, N. Peyerimhoff, Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature, Adv. Math., 369 (2020), 107188. https://doi.org/10.1016/j.aim.2020.107188 doi: 10.1016/j.aim.2020.107188
[3]	D. Cushing, S. Kamtue, R. Kangaslampi, S. Liu, N. Peyerimhoff, Curvatures, graph products and Ricci flatness, J. Graph Theory, 96 (2021), 522–553. https://doi.org/10.1002/jgt.22630 doi: 10.1002/jgt.22630
[4]	K. Devriendt, R. Lambiotte, Discrete curvature on graphs from the effective resistance, J. Phys.: Complex., 3 (2022), 025008. https://doi.org10.1088/2632-072X/ac730d doi: 10.1088/2632-072X/ac730d
[5]	R. Dunn, F. Dudbridge, C. M. Sanderson, The use of edge-betweenness clustering to investigate biological function in protein interaction networks, BMC Bioinf., 6 (2005), 39 https://doi.org/10.1186/1471-2105-6-39 doi: 10.1186/1471-2105-6-39
[6]	P. Elumalai, Y. Yadav, N. Williams, E. Saucan, J. Jürgen, A. Samal, Graph Ricci curvatures reveal atypical functional connectivity in autism spectrum disorder, Sci. Rep., 12 (2022), 8295. https://doi.org/10.1038/s41598-022-12171-y doi: 10.1038/s41598-022-12171-y
[7]	L. Fesser, S. S. de Haro Iváñez, K. Devriendt, M. Weber, R. Lambiotte, Augmentations of Forman's Ricci curvature and their applications in community detection, J. Phys.: Complex., 5 (2023), 035010. https://doi.org/10.1088/2632-072X/ad64a3 doi: 10.1088/2632-072X/ad64a3
[8]	Forman, Bochner's method for cell complexes and combinatorial Ricci curvature, Discrete Comput. Geom., 29 (2003), 323–374. https://doi.org/10.1007/s00454-002-0743-x doi: 10.1007/s00454-002-0743-x
[9]	S. Fortunato, Community detection in graphs, Phys. Rep., 486 (2010), 75–174. https://doi.org/10.1016/j.physrep.2009.11.002 doi: 10.1016/j.physrep.2009.11.002
[10]	S. Fortunato, D. Hric, Community detection in networks: a user guide, Phys. Rep., 659 (2016), 1–44. https://doi.org/10.1016/j.physrep.2016.09.002 doi: 10.1016/j.physrep.2016.09.002
[11]	A. Gosztolai, A. Arnaudon, Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature, Nat. Commun., 12 (2021), 4561. https://doi.org/10.1038/s41467-021-24884-1 doi: 10.1038/s41467-021-24884-1
[12]	R. Guimera, S. Mossa, A. Turtschi, L. A. N. Amaral, The worldwide air transportation network: anomalous centrality, community structure, and cities' global roles, Proc. Natl. Acad. Sci. U.S.A., 102 (2005), 7794–7799. https://doi.org/10.1073/pnas.0407994102 doi: 10.1073/pnas.0407994102
[13]	V. Grout, S. Cunningham, A constrained version of a clustering algorithm for switch placement and interconnection in large networks, 19th ISCA International Conference on Computer Applications in Industry and Engineering, 2006,252–257.
[14]	P. Krishna, N. H. Vaidya, M. Chatterjee, D. K. Pradhan, A cluster-based approach for routing in dynamic networks, ACM SIGCOMM Comput. Commun. Rev., 27 (1997), 49–64. https://doi.org/10.1145/263876.263885 doi: 10.1145/263876.263885
[15]	J. M. Lee, Introduction to Riemannian manifolds, 2 Eds., Springer, 2018. https://doi.org/10.1007/978-3-319-91755-9
[16]	Y. Lin, L. Lu, S. T. Yau, Ricci curvature of graphs, Tohoku Math. J., Second Series, 63 (2011), 605–627. https://doi.org/10.2748/tmj/1325886283 doi: 10.2748/tmj/1325886283
[17]	F. Münch, R. K. Wojciechowski, Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds, Adv. Math., 356 (2019), 106759. https://doi.org/10.1016/j.aim.2019.106759 doi: 10.1016/j.aim.2019.106759
[18]	C. C. Ni, Y. Y. Lin, F. Luo, J. Gao, Community detection on networks with Ricci flow, Sci. Rep., 9 (2019), 9984. https://doi.org/10.1038/s41598-019-46380-9 doi: 10.1038/s41598-019-46380-9
[19]	M. E. O'Kelly, A clustering approach to the planar hub location problem, Ann. Oper. Res., 40 (1992), 339–353. https://doi.org/10.1007/BF02060486 doi: 10.1007/BF02060486
[20]	Y. Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal., 256 (2009), 810–864. https://doi.org/10.1016/j.jfa.2008.11.001 doi: 10.1016/j.jfa.2008.11.001
[21]	O. Queen, G. A. McCarver, S. Thatigotla, B. P. Abolins, C. L. Brown, V. Maroulas, et al., Polymer graph neural networks for multitask property learning, npj Comput. Mater., 9 (2023), 90. https://doi.org/10.1038/s41524-023-01034-3 doi: 10.1038/s41524-023-01034-3
[22]	A. W. Rives, T. Galitski, Modular organization of cellular networks, Proc. Natl. Acad. Sci. U.S.A., 100 (2003), 1128–1133. https://doi.org/10.1073/pnas.0237338100 doi: 10.1073/pnas.0237338100
[23]	J. Sia, W. Zhang, E. Jonckheere, D. Cook, P. Bogdan, Inferring functional communities from partially observed biological networks exploiting geometric topology and side information, Sci. Rep., 12 (2022), 10883. https://doi.org/10.1038/s41598-022-14631-x doi: 10.1038/s41598-022-14631-x
[24]	J. Sia, E. Jonckheere, P. Bogdan, Ollivier-Ricci curvature-based method to community detection in complex networks, Sci. Rep., 9 (2019), 9800. https://doi.org/10.1038/s41598-019-46079-x doi: 10.1038/s41598-019-46079-x
[25]	V. Spirin, L. A. Mirny, Protein complexes and functional modules in molecular networks, Proc. Natl. Acad. Sci. U.S.A., 100 (2003), 12123–12128. https://doi.org/10.1073/pnas.2032324100 doi: 10.1073/pnas.2032324100
[26]	S. Tan, J. Sia, P. Bogdan, R. Ivanov, Analyzing neural network robustness using graph curvature, 2024 International Conference on Assured Autonomy (ICAA), Nashville, TN, USA, 2024,110–113. https://doi.org/10.1109/ICAA64256.2024.00026
[27]	Y. Tian, Z. Lubberts, M. Weber, Mixed-membership community detection via line graph curvature, Proceedings of the 1st NeurIPS Workshop on Symmetry and Geometry in Neural Representations, 2023,219–233.
[28]	J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, M. M. Bronstein, Understanding over-squashing and bottlenecks on graphs via curvature, arXiv, 2021. https://doi.org/10.48550/arXiv.2111.14522
[29]	Y. Tian, Z. Lubberts, M. Weber, Curvature-based clustering on graphs, arXiv, 2023. https://doi.org/10.48550/arXiv.2307.10155
[30]	M. Weber, E. Saucan, J. Jürgen, Characterizing complex networks with Forman-Ricci curvature and associated geometric flows, J. Complex Netw., 5 (2017), 527–550. https://doi.org/10.1093/comnet/cnw030 doi: 10.1093/comnet/cnw030
[31]	J. Wee, K. Xia, Forman persistent Ricci curvature (FPRC)-based machine learning models for protein–ligand binding affinity prediction, Brief. Bioinform., 22 (2021), bbab136. https://doi.org/10.1093/bib/bbab136 doi: 10.1093/bib/bbab136
[32]	J. Wee, K. Xia, Ollivier persistent Ricci curvature-based machine learning for the protein–ligand binding affinity prediction, J. Chem. Inf. Model., 61 (2021), 1617–1626. https://doi.org/10.1021/acs.jcim.0c01415 doi: 10.1021/acs.jcim.0c01415
[33]	M. R. Znaidi, J. Sia, S. Ronquist, I. Rajapakse, E. Jonckheere, P. Bogdan, A unified approach of detecting phase transition in time-varying complex networks, Sci. Rep., 13 (2023), 17948. https://doi.org/10.1038/s41598-023-44791-3 doi: 10.1038/s41598-023-44791-3

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)