Community Detection on Networks with Ricci Flow

Chien-Chun Ni; Yu-Yao Lin; Feng Luo; Jie Gao

Source-linked AI summary

Community Detection on Networks with Ricci Flow

Chien-Chun Ni, Yu-Yao Lin, Feng Luo, Jie Gao

arXiv:1907.03993v1Jul 9, 2019cs.SIphysics.soc-ph

TL;DR

Community detection is important for networks whose nodes form densely connected functional groups, but existing approaches mainly rely on statistical or graph-theoretic methods. The paper instead treats networks as geometric objects and applies curvature-based discrete Ricci flow, which stretches inter-community edges and shrinks intra-community edges. Experiments and theory show effective community detection, including nearly perfect clustering when structure exists and competitive performance on real networks.

Problem
Community detection seeks to identify densely connected functional groups in real-world networks, while prevailing approaches mainly use statistical or graph-theoretic methods.
Method
The paper models networks as geometric objects and uses discrete Ricci flow to evolve edge weights according to Ollivier-Ricci curvature before thresholding stretched edges to separate communities.
Results
The method provides nearly perfect clustering when community structures exist, is competitive with prior algorithms on real networks, and is theoretically guaranteed for G(a,b) when a > b ≥2.
Takeaways & Limitations
Discrete curvature and Ricci flow are effective geometric tools for detecting community structures in complex networks.
Takeaways & Limitations
The number of flow iterations and the surgery threshold depend on the individual network.

Abstract

from arXiv · show

Many complex networks in the real world have community structures -- groups of well-connected nodes with important functional roles. It has been well recognized that the identification of communities bears numerous practical applications. While existing approaches mainly apply statistical or graph theoretical/combinatorial methods for community detection, in this paper, we present a novel geometric approach which enables us to borrow powerful classical geometric methods and properties. By considering networks as geometric objects and communities in a network as a geometric decomposition, we apply curvature and discrete Ricci flow, which have been used to decompose smooth manifolds with astonishing successes in mathematics, to break down communities in networks. We tested our method on networks with ground-truth community structures, and experimentally confirmed the effectiveness of this geometric approach.

1 Introduction

The paper reframes community detection as a geometric decomposition problem and introduces discrete Ricci flow to identify communities by evolving network edge weights. Experiments on benchmark and real networks report strong or competitive clustering performance.

Real-world networks often contain densely connected communities whose identification supports analysis of functional processes such as disease, information, and behavior contagion.
Existing community-detection methods primarily use randomized procedures, centrality, or statistical objectives such as modularity to find dense clusters.
The paper models community structure as a geometric phenomenon, transferring the manifold-decomposition intuition of Ricci flow to networks.The proposed analogy treats connected-sum components of manifolds as network communities.
Discrete Ricci flow stretches negatively curved, typically inter-community edges and shrinks positively curved, typically intra-community edges, enabling threshold-based network surgery.The method can perform multiple rounds of flow and edge removal for hierarchical community structures.
Illustrations show the method separating two or three communities in the Karate club graph and detecting hand-labeled friend circles in a Facebook ego network.The Karate example uses thresholds after Ricci-flow iterations, while the Facebook example reports 792 friends, 14,025 edges, and 24 friend circles.
On benchmark networks, the method provides nearly perfect clustering when community structure exists and is competitive with prior algorithms on real networks with ground-truth communities.Similar performance trends were observed using modularity and other clustering-accuracy metrics.

2 Classical theory of Ricci curvature, Optimal transport and the Ricci flow

The classical framework treats curvature as a measure of geometric bending and Ricci flow as a curvature-driven metric evolution. Optimal transport extends curvature to metric-measure spaces, motivating its discrete use on networks.

Curvature quantitatively measures how space bends, with positive, zero, and negative curvature corresponding to geometrically distinct manifold and graph structures.Examples include spheres, planes, hyperboloids, complete graphs, grids, and trees.
Optimal transport formulates the movement of probability mass between spaces, and the Wasserstein distance measures minimum transportation cost when the cost is metric distance.
Ollivier’s construction defines Ricci curvature on metric-measure spaces through the Wasserstein distance between probability measures associated with points.For nearby points on a manifold, the Wasserstein distance relates to curvature and geodesic distance.
Hamilton’s Ricci flow evolves a manifold metric through a nonlinear equation analogous to heat diffusion, smoothing curvature irregularities over time.Positive-curvature regions tend to shrink, while negative-curvature regions tend to expand and spread.
Perelman’s Ricci flow with surgery captures geometric decomposition of 3-manifolds by analyzing singularity formation and removing singular regions.
The network analogue assumes that networks discretize higher-dimensional manifolds and that communities correspond to geometric components, while iteration counts and surgery thresholds depend on each network.

3 Theory and Algorithms on Discrete Ollivier Ricci Flow

The algorithm defines network curvature through optimal transport and evolves edge weights with discrete Ricci flow. Iterative stretching, shrinking, and thresholding separate intra-community from inter-community edges.

Discrete Ricci curvature: Ollivier Ricci curvature relates an edge’s curvature to the optimal transportation cost between probability measures on its endpoint neighborhoods.The Wasserstein distance is the minimum weighted travel cost over valid transport plans, using shortest-path distances.
Discrete Ricci curvature: Different-community edges tend to have negative curvature because endpoint neighborhoods share fewer common neighbors, making transport cost exceed edge length.Within-community nodes tend to share neighbors or have shortcuts, producing the contrasting curvature pattern.
Mass distribution: The node mass distribution uses α for the probability of remaining at the node and exponentially distance-discounted neighbor weights controlled by p.When p = 0, the distribution is uniform over neighbors; larger p more strongly discounts distant neighbors.
Discrete Ricci flow: At each iteration, all edge weights are updated simultaneously according to their current Ricci curvature and shortest-path distances.The flow is an evolving process whose curvature and distance values are recomputed on the graph induced by the current weights.
Community separation: After usually 10 to 15 iterations, thresholding removes large-weight edges, separating communities through network surgery.The flow expands negatively curved edges and shrinks positively curved edges, condensing intra-community connections and stretching inter-community ones.

4 Results

The method is evaluated theoretically and experimentally on synthetic and real-world networks with ground-truth communities. Results show strong accuracy on model networks and competitive performance across several real datasets.

4.1 Theoretical Results: For G(a,b) graphs with a > b ≥2, Ricci flow detects communities because intra-community edge weights shrink asymptotically faster than inter-community weights.The result is established for Ollivier-Ricci flow with α = 0 and p = 0.
4.2.1 Model Networks and Real World Datasets: The evaluation uses SBM, LFR, GNet, and six real-world networks with ground-truth community labels.The real-world datasets include Email-EU-core, Karate club, Football, Polbooks, Polblogs, and a Facebook ego-network.
4.2.1 Model Networks and Real World Datasets: ARI measures agreement with ground-truth communities, while modularity measures community strength without requiring ground-truth labels.Higher ARI indicates more accurate detected communities.
4.2.2 Experimental Results: Ricci flow shows nearly 100% SBM accuracy at pinter/pintra = 0.5 and nearly 0% at 0.55, reflecting a sharp transition as community structure disappears.The method is evaluated after 50 discrete Ricci-flow iterations.
4.2.3 Comparison with Other Methods: On LFR graphs, Ricci flow and Spinglass outperform other methods, with Ricci flow achieving nearly perfect accuracy across most µ values compared with Spinglass at 95%.Ricci flow is reported as more stable across the tested µ values.
4.2.3 Comparison with Other Methods: On real-world datasets, Ricci flow is competitive or better in Karate club, Football, Polbooks, and Polblogs, and both Ricci flow and Spinglass improve with higher average degree.Higher average degree implies greater edge density within communities.

5 Conclusion

The paper introduces geometric tools for analyzing community structures in complex networks by treating networks as geometric objects and using curvature-guided flow to decompose them.

The paper introduces geometric tools to investigate community structures on complex networks.It treats networks as geometric objects and applies curvature and curvature-guided flow to decompose them.

Supplementary Materials

The supplementary materials formulate community detection using graph connectivity, optimal transport, metric structure, and curvature-based network analysis.

Community detection seeks inter-community edges whose removal yields connected subgraphs with dense internal and sparse external connections.The formulation distinguishes intra-community from inter-community edges by their connectivity patterns.
The approach models a graph as a transportation network where inter-community edges are more heavily traveled than intra-community edges.Optimal transportation cost quantifies traffic through edges.
A weighted graph assigns non-negative edge weights, and path length is defined as the sum of weights along the path.These weights induce the metric used for subsequent transportation and curvature calculations.
On finite graphs, probability measures are functions on vertices, while edge weights induce distances through shortest paths.The induced metric is the minimum path length between vertices.
Optimal transportation minimizes the cost of moving mass between probability measures, and Kantorovich’s formulation guarantees an attained solution through transportation plans.The finite-graph version uses a transportation plan over vertex pairs.
Ricci curvature characterizes geometric structure, while Ollivier’s formulation connects curvature on metric spaces to optimal transportation.The paper applies this connection to networks equipped with edge weights and vertex probability measures.

A.3 Ollivier’s work on Ricci curvature for general metric spaces with measures

This section connects Ollivier Ricci curvature and discrete Ricci flow to optimal transport, weighted-graph geometry, and the classical Ricci-flow decomposition of manifolds.

Ollivier’s theorem relates classical Ricci curvature to Wasserstein distance between probability measures centered at nearby points.This relation motivates extending Ricci curvature to general metric spaces with measures.
Ollivier Ricci curvature on a metric space is defined along a shortest path using the Wasserstein distance between the associated measures.The transportation cost uses the metric distance as its cost function.
For weighted graphs, the method combines induced shortest-path distances with probability measures on vertices to define discrete Ricci curvature.The generalized measure incorporates edge weights through distance-dependent exponential weighting and normalization.
Discrete Ricci flow evolves edge-weighted graphs in discrete time, with edge weights changing according to Ollivier-Ricci curvature.For unweighted graphs, all initial edge weights are set to 1 before the flow begins.
The flow expands negatively curved subgraphs and contracts positively curved subgraphs, causing inter-community weights to diverge and intra-community weights to shrink.Removing sufficiently high-weight edges partitions the network and can expose hierarchical communities through continued flow.
The network method is motivated by classical Ricci flow, whose singularities and surgery helped decompose 3-manifolds into simpler components.The paper uses this geometric analogy to motivate community detection on networks.
Classical Ricci flow smooths curvature irregularities, and Perelman’s work used singularity formation and surgery in proving the geometrization conjecture.These results provide the geometric precedent for using flow and decomposition in the network setting.

D Evaluations

The evaluation section uses ARI and modularity to assess clustering accuracy, distinguishing metrics that require ground truth from those that do not.

Adjusted Rand Index measures agreement between detected and ground-truth partitions, with random agreement adjusted to a score of 0.An ARI of 1 indicates a perfect match between the two clusterings.
Modularity measures the excess fraction of within-community edges relative to a degree-preserving random baseline.It does not require ground-truth communities and is easy to compute on large networks, but has a resolution problem.
The modularity score is defined from the network’s adjacency matrix, node degrees, and community assignments.The formulation also represents inter-community and intra-community edge fractions.

D.1 Edge Weights under Ricci Flow Iterations

Ricci flow separates intra-community from inter-community edges through opposite weight dynamics, while edge Ricci curvatures converge during iteration.

Initially, all graph edges have weight 1 before Ricci flow iterations begin.
As iterations proceed, intra-community edge weights decrease toward 0, whereas inter-community edge weights increase.The experiment uses an LFR graph with 1000 nodes, μ = 0.4, 38 communities, and average degree 20.
Ricci curvature on all edges converges to a fixed value during the iteration process.
On the LFR graph, Ricci flow expands inter-community edge weights and drives edge Ricci curvatures toward 0.The graph has 1000 nodes, 9539 edges, and μ = 0.4.

D.2 Ricci Flow Parameters

The parameter study varies the probability measure used to compute Ricci curvature and finds that performance is generally good for less mixed graphs, with base e most stable for more mixed graphs.

Ricci curvature computation uses a probability distribution exponential in edge weight, with a selectable base and power p.
Across most base settings, community-detection results are good when the mixing parameter μ is below 0.6.The reported results average over 10 trials on LFR graphs with 1000 nodes and average degree 20.
For more mixed graphs with larger μ, choosing base e gives the most stable result.
The subsequent experiments use base = e and power = 2.

D.3 Approximated Optimal Transport Distance

The Sinkhorn distance approximates optimal transport in Ricci flow computations while substantially reducing computation time.

With regularity term 0.1, Sinkhorn distance performs equally well as optimal transport in the Ricci flow process.
4 times smaller time cost is reported for Sinkhorn distance than optimal transport on an LFR graph with 300 nodes.The comparison averages computation time over 5 iterations.

D.4 Ricci flow with Surgery

Ricci flow with periodic surgery improves community separation in complex or hierarchical graphs by removing high-weight edges during the flow. On an LFR graph with μ = 0.6, surgery raises ARI from 0.3 to 0.8.

D.4 Ricci flow with Surgery: Ricci flow generally performs well on graphs with distinct community structures without many parameter settings.
D.4 Ricci flow with Surgery: Complex graphs, especially hierarchical ones, may require multiple Ricci flow runs and surgery during the iterations.
D.4 Ricci flow with Surgery: Every 5 iterations, surgery removes the top 5% of edges ranked by weight.
D.4 Ricci flow with Surgery: For networks without ground-truth labels, modularity is proposed to determine the final edge-weight cutoff threshold.The suggested threshold is the point where the modularity curve first reaches a plateau or turning point.
D.4 Ricci flow with Surgery: The removed high-weight edges are mostly inter-community edges, and their removal further separates communities.
D.4 Ricci flow with Surgery: ARI increases from 0.3 to 0.8 when surgery is applied on an LFR graph with 1000 nodes and μ = 0.6.The comparison evaluates 50 Ricci flow iterations with surgery every 5 iterations.

E Proof of Theorem 4.1

The proof analyzes Ricci flow on a symmetric community network by reducing its metric to three edge lengths and studying their Wasserstein-distance updates. An eigenvalue analysis then establishes that inter-community edges expand while non-gateway edges contract exponentially.

Network structure: The graph has gateway and non-gateway nodes, yielding three edge types: inter-community, gateway-to-non-gateway, and non-gateway-to-non-gateway edges.Symmetry preserves these three edge classes throughout the Ricci-flow iterations.
Wasserstein distances: The Wasserstein distances D1, D2, and D3 are computed for the three edge types, with D1 ≥ D2 ≥ D3 when a > b ≥ 2 and d1 ≥ d2 ≥ d3.For non-gateway edges, identical neighboring measures give D3 = 1/a d3.
Ricci-flow recurrence: The edge-length vector follows a linear recurrence Wn+1 = AWn with W0 = [1,1,1]^t, so Ricci-flow behavior reduces to the asymptotics of matrix powers.The three entries of Wn represent the three edge lengths after n iterations.
Eigenvalue analysis: For a > b ≥ 2, the update matrix has three real eigenvalues with λ2 = 1/a and λ3 < 0, while the dominant eigenvector has form [1,k,0]^t with 0 < k < 1.The dominant eigenvalue λ1 controls the long-run growth because λ1 exceeds the magnitudes of the other eigenvalues.
Asymptotic behavior: The inter-community edge length grows at rate λ1^n, whereas gateway-to-non-gateway and non-gateway-to-non-gateway lengths grow more slowly; the latter shrinks exponentially because 1/a < 1.This separation produces the geometric decomposition underlying the theorem.