CS Paper Radar

Ollivier's Ricci Curvature on Complex-weighted Graphs

Yu Tian, Eleanor Wiesler, Melanie Weber

cs.SI math.MGphysics.soc-ph ·submitted 2026-08-10 18:43 UTC · v1

Abstract

Understanding the geometry of complex networks is critical for effective modeling and analysis across domains. While discrete notions of Ricci curvature have emerged as powerful tools for characterizing both local and global network structure, existing formulations are largely confined to undirected networks with real-valued weights. This limits the use of curvature-based analysis of directional and complex-weighted relations that arise naturally in many applications, from social and biological systems to quantum and signal-processing networks. In this work, we introduce a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case. We establish fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that relate curvature to cycle structure in local neighborhoods. We further develop computational methods for curvature estimation and demonstrate their utility in community detection on directed networks.

Comment
32 pages, 11 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Community Detection using the Edge Laplacian Dynamics vis-a-vis Ricci Flow

cs.SI math.DS ·2026-09-30 ·Pratibha Bhandari, Soumyendu Raha
similarity 0.74
Abstract

It has been found that utilizing the geometric properties of the graph dynamics can bring out crucial information of the data that a statistical analysis will not. The properties of Ricci flow bring out hidden dynamics of the data in the same way as decomposition of smooth manifolds. In this paper we explore an alternative to Ricci flow, where we find that we can bring out similar properties like it using a simpler and well defined Edge Laplacian to practice community detection in graphs. Moreover, the results obtained by the present approach show that a flow driven by the Edge Laplacian yields results similar to those of the Ricci flow. In contrast, computing the Forman-Ricci curvature requires looping over the adjacent edges, while computing Olivier-Ricci curvature involves the computation of Wasserstein distance and probability distribution associated with the graph nodes, making the Edge Laplacian approach computationally more efficient.

0.11

Curvature-Guided Sparsification for Graphs with Community Structure

cs.SI ·2026-10-28 ·Avin Kolahdooz, Jose Jairo Garcia, Sarah Percival
theory similarity 0.68
Abstract · 25 pages, 8 figures

Graph sparsification in large-scale networks often requires balancing structural accuracy and computational efficiency. Curvature-based methods, particularly Ollivier-Ricci curvature (ORC), have shown strong performance in identifying inter-community bridges, but their computational cost limits scalability. In this work, we propose a two-stage curvature-guided pipeline for graph sparsification with the goal of preserving community structure. We first use the Lower Ricci Curvature, a combinatorial lower bound of the ORC, to perform efficient edge filtering, substantially reducing graph size before applying the computationally intensive optimal-transport-based ORC curvature and Ricci flow. Results from empirical studies on synthetic and real-world datasets demonstrate that the combined LRC-ORC pipeline can achieve community-recovery accuracy comparable to ORC-only sparsification in terms of Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI), while reducing runtime on most evaluated benchmarks. Our findings suggest that integrating combinatorial and geometric curvature notions provides a computationally efficient and structurally principled framework for graph sparsification in complex networks.

0.20

A comparative exploration of Steinerberger curvature and resistance curvature in model and real-world complex networks

cs.SI ·2026-11-17 ·Madhumita Mondal, Priyank Vasu, Areejit Samal, Jürgen Jost
similarity 0.67
Abstract · 40 pages, 5 main figures, 3 supplementary figures, 1 main table, 17 supplementary tables

Discrete curvature extends the concept of curvature from continuous spaces to discrete structures such as graphs and networks. It provides a mathematical framework for characterising local and global network geometry, that offers insights into structural properties such as connectivity and clustering. In this study, we investigate Steinerberger curvature (SBC) and resistance curvature (RC) and examine their relationships with established graph curvature measures, namely Forman-Ricci, Augmented Forman-Ricci, and Ollivier-Ricci curvatures, a notion of scalar sectional curvature, as well as conventional vertex-based measures. A systematic comparative analysis is conducted across various synthetic network models and real-world networks, focusing on curvature distributions, correlations with structural measures, and the identification of structurally important vertices through network disintegration experiments based on global efficiency. Our results show that SBC generally exhibits weaker correlations with other measures. On the other hand, RC is strongly positively correlated with established discrete Ricci curvature measures, whereas it is predominantly negatively correlated with conventional vertex-based measures like degree and centrality-based measures. Furthermore, RC achieves a reduction in communication efficiency comparable to or faster than established Ricci curvature measures. These findings suggest that SBC captures structural characteristics that are largely distinct from those reflected by other measures, while RC exhibits distinct structural associations and shows significant potential for identifying vertices critical to network connectivity.

0.32

Geometric Flow enhanced Graph Coarsening

cs.AI ·2026-09-14 ·Chaoqun Fei, Guoxuan Li, Tinglve Zhou, Chuanqing Wang, Yangyang Li
similarity 0.63
Abstract

Recently, researchers have proposed a graph pooling operation, akin to the pooling process in conventional convolutional neural networks (CNN), aimed at reducing the computation cost of Graph convolutional neural networks (GCNNs). While most GCNN-based methods treat graph pooling as a node clustering problem and propose learning a cluster assignment matrix, existing clustering-based pooling methods tend to focus solely on the rough topology information of graphs, neglecting the exploitation of higher-order mutual connections among neighbors. In terms of message passing on graph, the ease of information passing on edges reflects the closeness between neighboring nodes, which significantly relies on the interconnectivity among neighbors. In this study, we address this gap by considering such local connection information and introducing a novel graph pooling method named RicciPool. We introduce discrete graph curvature, particularly Ollivier-Ricci curvature, as a measure of higher-order connectivity around an edge. Subsequently, we construct an Ollivier-Ricci flow formula to reweigh edge weights, leveraging the crucial information provided by Ricci curvature, particularly vital for extracting clusters in graphs. Building upon this foundation, we utilize the spectral clustering technique to learn a new cluster assignment matrix. Experimental results on multiple bioinformatics protein datasets and social networks underscore the effectiveness of our proposed method.

0.38

Behavior of Nonlinear Opinion Dynamics over Large Networks

eess.SY ·2026-09-12 ·Yu Xing, Anastasia Bizyaeva, Karl H. Johansson
hot direction similarity 0.62
Abstract

Opinion dynamics have been studied for decades across disciplines, with much of the theoretical literature focusing on behaviors such as consensus, polarization, and clustering. Although classic models can exhibit more complex opinion patterns in simulations, quantifying such distributions is not fully understood. To address this question, in this paper, we study the behavior of nonlinear opinion dynamics over large-scale networks using graphons, which capture the underlying network structure. In the model, agents update their opinions according to a nonlinear rule that includes saturation effects in interactions. The network is represented by random graphs generated from a graphon, and a corresponding nonlinear dynamical model is introduced over the graphon. We show that the graphon dynamics approximate the finite-dimensional system, when the network size is large. Leveraging spectral approximation results for random graphs, we further show that the equilibria of the nonlinear model can also be approximated by those of the continuum limit. This result enables a quantitative characterization of the opinion distribution based on the underlying graphon structure. The theoretical results are illustrated by numerical simulation.

0.26

A Novel Approach for the SDIR Epidemic Model on Online Social Networks

cs.SI cs.NImath.OC ·2026-09-27 ·Nguyen Hong Phuc, Duong Khanh Ly, Hoang Phi Dung
theory similarity 0.59
Abstract · Welcome comments

Information diffusion can be controlled by restricting or removing links (edges) in online social networks, as well as in real-world networks. To identify the most influential links to remove while minimizing diffusion, previous studies have proposed upper bounds for spreading processes in SIR and SIS models, using supermodularity and weighted matrices to identify critical links in contact networks. However, in some cases, existing upper bounds are not sufficiently tight to accurately capture the effect of important edges, as in the SDIR model of [14] (Khanh-Cho-Dung, Proceedings of 40th ICOIN, 2026). We therefore propose a tighter upper bound for controlling diffusion in the SDIR model by directly analyzing the dynamics of the two state vectors D and I in a $2N$-dimensional space. This approach yields an improved spectral-radius convergence condition and outperforms the previous method. Simulations on the synthetic Erdos-Renyi network and the real-world Haslemere dataset using a Greedy edge-deletion algorithm demonstrate its effectiveness for influence minimization on social networks.

0.18

Discretization-free exact recovery in geometric community detection

cs.SI math.PR ·2026-08-23 ·Maarten Hoeneveld, Moritz Otto, Raphaël Sala
theory similarity 0.59
Abstract · 30 pages, 2 figures

Geometric community detection seeks to recover latent communities in networks where connectivity depends jointly on community structure and continuous spatial geometry. Existing exact-recovery approaches typically discretize the underlying space, which can impose restrictive structural assumptions on the connectivity functions. We develop a polynomial-time, discretization-free algorithm for exact recovery in the Geometric Hidden Community Model (GHCM), operating directly on the continuous geometry. Our method succeeds even when connectivity functions coincide on a nontrivial portion of their visibility range and when two communities can be distinguished only through their connectivity to a third community. We prove exact recovery under these weaker conditions and provide experiments showing that the algorithm succeeds beyond the theoretically guaranteed regime.

0.23

Spectral Braids: A Topological Descriptor for Dynamic Directed Networks

cs.SI cs.LG ·2026-10-27 ·Mehmet Emin Aktas, Esra Akbas
published similarity 0.58
Abstract · 15 pages, 5 figures, 2 tables. Accepted at the 2026 IEEE International Conference on Big Data (IEEE BigData 2026)

Eigenvalues are a workhorse of graph machine learning: spectral clustering, spectral graph neural networks, and graph kernels all summarize a network by the eigenvalues of a matrix. These eigenvalues are almost always treated as a static list of numbers. When a graph changes, however, its eigenvalues move, and when the matrix is not symmetric, they move in the complex plane, where they can wind around each other. The pattern of this winding is a braid, a classical object from topology. We propose spectral braids, a methodology for dynamic directed networks: each snapshot is aggregated into a community-level transition matrix, its complex eigenvalues are tracked over time, and the braid they trace is read off as a word. The word is then mapped to a matrix by the Burau representation, which gives a fixed-size feature vector for any classifier. The braid has a concrete meaning: each eigenvalue describes how a group of communities behaves, and each crossing records one group overtaking another. We evaluate the method on dynamic network classification, using synthetic networks of online communities whose labels describe how the network evolved between the same starting and ending states. Our experimental results show that the proposed features reach 97.1% accuracy on four classes, against 44.5% for the best feature set that does not track eigenvalues, and that the Burau features also separate networks containing the same events in a different order, which simple counts of crossings cannot do. To the best of our knowledge, this is the first study that defines braids and braid monodromy on graph data and uses them as features for learning on dynamic networks.

0.36