Evolution of weights on a connected finite graph

In 1982, Ricci flow was first introduced by Hamilton [14] to deform a metric on a Riemannian manifold $(M,g)$ according to the differential equation involving a one-parameter family of metrics $g(t)$ on a time interval, namely

where ${\rm Ric}(g(t))$ is the Ricci curvature of the metric $g(t)$. Generally speaking, Ricci flow smooths the metric, but it may lead to singularities. It was used in a genius way by Perelman [26] for solving the Poincaré conjecture. Moreover, it was used by Brendle and Schoen [4] for solving the differentiable sphere theorem.

Also, Ricci flow can be applied to discrete geometry, which includes complex networks and weighted finite graphs. To be more specific, we assume that $G=(V,E,\bf{w})$ is a connected weighted finite graph. Here $V=\{z_{1},z_{2},\cdots,z_{n}\}$ denotes the vertex set, $E=\{e_{1},e_{2},\cdots,e_{m}\}$ represents the edge set and $\mathbf{w}=(w_{e_{1}},w_{e_{2}},\cdots,w_{e_{m}})$ stands for the weights on edges. In 2009, Ollivier [24] suggested a Ricci flow

where, for each $e\in E$, $\kappa_{e}^{\alpha}$ is its Ollivier’s Ricci curvature, and $\alpha\in[0,1]$ is a parameter. Ni et al [23] found that discrete Ricci flow can be applied to detect community structures in networks, similar to classical Ricci flow on manifolds.

Community detection is an important research area in network analysis, aiming to identify clusters or groups of nodes that are more densely connected internally than with the rest of the network. This concept is crucial in various fields, including sociology [28, 31], biology [12, 3], and computer science[29]. Lots of algorithms [32, 11, 21, 18, 5, 25, 12] have been developed to detect and separate communities. Most of these algorithms focus on identifying dense clusters in a graph, using randomized approaches like label propagation or random walks, optimizing centrality measures such as betweenness centrality, or considering measures like modularity. Ricci curvature, introduced by Forman [10], Ollivier [24] and Lin-Lu-Yau [19], acknowledged as an essential tool in graph theory, facilitates deeper insights into network structures and provides an innovative approach to community detection. In 2019, based on (1.1) and a surgery process, Ni et al [23] established a very effective method of community detection. In 2021, Bai et al [1] studied a star coupling Ricci curvature based on Olloivier’s Ricci curvature. In 2022, this community detection method was extended by Lai et al [16] to a normalized Ricci flow based on [19, 1]. Experiments in [16] had shown that their methods were still effective. Very recently, the authors in the current paper [20] proposed a modified Ricci flow and a quasi-normalized Ricci flow for arbitrary weighted graphs. Notably, the results on global existence and uniqueness of solutions in [20] do not rely on the exit condition suggested by Bai et al. [2].

Although literatures [23] and [16] have shown great success in their applications, they lack theoretical support. In order to make up for this shortcoming, recently, concerning Lin-Lu-Yau’s Ricci curvature $\kappa_{e}$, Bai et al [2] obtained the existence and uniqueness of global solutions to the Ricci flow

and the normalized Ricci flow

under an exit condition: if $w_{e}>\rho_{e}=\inf_{\gamma}\sum_{\tau\in\gamma}w_{\tau}$, then the edge $e$ is deleted, where $e=xy\in E$ and $\gamma$ is a path connecting $x$ and $y$. Notice that in all of the above mentioned articles, the authors ask for surgery while extending solutions.

In [20], we find that if $w_{e}$ is replaced by $\rho_{e}$ on the right hand sides of (1.2) and analog of (1.3), namely

and

then both (1.4) and (1.5) have unique global solutions $w_{e}(t)$ for each $e\in E$ and all $t\in[0,+\infty)$. In this setting, we removed the exit condition in [2], and did not require surgery in the process of flowing. Meanwhile, experiments show that (1.4) and (1.5) have the same impressive performance as (1.2) and (1.3), and have better modularity.

Currently, there is no existence result for solution to Ollivier’s Ricci flow (1.1). To ensure the global existence of the solution, we can modify the equation (1.1) by replacing the term $\kappa_{e}^{\alpha}w_{e}$ with $\kappa_{e}^{\alpha}\rho_{e}$. Then we prove the existence and uniqueness of global solutions to the modified Ricci flow. In fact, we shall consider a more general evolution of weights on a connected weighted finite graph $(V,E,\bf{w})$, which reads as

where $e=xy\in E$ and $W(\mu(x,\cdot),\mu(y,\cdot))$ denotes the Wasserstein distance between two probability measures $\mu(x,\cdot)$ and $\mu(y,\cdot)$. One can easily see that if $\mu(x,z)=\mu_{x}^{\alpha}(z)$ is an $\alpha$-lazy one-step random walk, then (1.6) reduces to $w_{e}^{\prime}=-\kappa_{e}^{\alpha}\rho_{e}$. Through a large number of experiments, we conclude that (1.6) is effective in community detection. We look at how key factors, like $\alpha$ and the number of iterations, affect the results. After being tested on real data and compared with existing methods, our approach demonstrates strong performance, especially in measuring modularity.

Before ending this introduction, we mention another interesting curvature flow, the Bakry-Émery curvature flow, studied by Cushing et al. Interested readers are referred to [7, 8] for details. The remaining part of this paper is organized as follows: In Section 2, we state our main results for the evolution of weights; In Section 3, we prove the Lipschitz property of the Wasserstein distance; The proof of Theorems 2.1 and 2.2 will be given in Section 4; In Section 5, We construct several examples of converging flow; Experiments will be done in Section 6.

Let $G=(V,E,\mathbf{w})$ be a connected weighted graph, $V=\{z_{1},z_{2},\cdots,z_{n}\}$ denotes the set of all vertices, $E=\{e_{1},e_{2},\cdots,e_{m}\}$ denotes the set of all edges, and $\mathbf{w}=(w_{e_{1}},w_{e_{2}},\cdots,w_{e_{m}})$ denotes the vector of weights on edges. Clearly, each function $f:G\rightarrow\mathbb{R}$ corresponds to a vector $(f(z_{1}),f(z_{2}),\cdots,f(z_{n}))$ in $\mathbb{R}^{n}$. Nevertheless, when the weights $\mathbf{w}$ change, $f$ can be regarded as a vector-valued function, namely

Here and in the sequel, $\mathbb{R}^{m}_{+}=\{\mathbf{y}=(y_{1},y_{2},\cdots,y_{m})\in\mathbb{R}^{m}:y_{i}>0,i=1,2,\cdots,m\}$. A function $f:G\rightarrow\mathbb{R}$ is said to be locally Lipschitz in $\mathbb{R}^{m}_{+}$ with respect to $\mathbf{w}$, if for any fixed domain $\Omega\subset\subset\mathbb{R}^{m}_{+}$, there exists a constant $C$ depending only on $\Omega$ such that for any vertex $u$,

where $\widetilde{f}$ represents the function obtained by replacing $\mathbf{w}$ with $\widetilde{\mathbf{w}}$ in the expression of $f$.

Throughout this paper, we use the the distance between two vertices $x$ and $z$ defined by

where the infimum is taken over all paths $\gamma$ connecting $x$ and $z$. Obviously, the function $f=d(x,\cdot)$ is considered not only as a vector $(d(x,z_{1}),d(x,z_{2}),\cdots,d(x,z_{n}))$, but also a vector-valued function ${\bf{w}}\mapsto(d(x,z_{1}),d(x,z_{2}),\cdots,d(x,z_{n}))$, in particular, each $d(x,z_{j})$ is a function of $\mathbf{w}$. Given $\mathbf{w}$ and $\widetilde{\mathbf{w}}$ in $\mathbb{R}^{m}_{+}$. Let $d$ and $\widetilde{d}$ be two distance functions determined by $\mathbf{w}$ and $\widetilde{\mathbf{w}}$ respectively. Then, by ([20], Lemma 2.1), for any two fixed vertices $x$ and $z$,

Thus the distance function $d$ is Lipschitz in $\mathbf{w}$.

We are now defining a set of functions

Note that for any fixed $x\in V$, each $\mu(x,\cdot)$ is a probability measure. In practical problems, probability measures involving the weights $\mathbf{w}$ are more meaningful. For example, given any number $\alpha\in[0,1]$, the $\alpha$-lazy one-step random walk reads as

Obviously $\mu(x,\cdot)=\mu_{x}^{\alpha}(\cdot)$ belongs to $\mathscr{M}$. Denote the one-step neighbor of $x$ by $N_{x}=\{y:y\sim x\}$, and the two-step neighbor of $x$ by $N_{2,x}=\{z\not=x:z\sim y\,\,{\rm for\,\,some}\,\,y\in N_{x}\}$. Similarly, an $\alpha$-lazy two-step random walk is represented by

One can easily check that $\mu(x,\cdot)=\mu_{2,x}^{\alpha}(\cdot)\in\mathscr{M}$ for all $x\in V$ and all $\alpha\in[0,1]$. Clearly, $\mu_{x}^{\alpha}$ and $\mu_{2,x}^{\alpha}$ are also two functions of $\mathbf{w}$, and both of them are locally Lipschitz in $\mathbb{R}^{m}_{+}$ with respect to $\mathbf{w}$.

Let $\mu_{1}$ and $\mu_{2}$ be two probability measures. A coupling between $\mu_{1}$ and $\mu_{2}$ is defined as a map $A:V\times V\rightarrow[0,1]$ satisfying for all $x,y\in V$,

While the Wasserstein distance between $\mu_{1}$ and $\mu_{2}$ reads

where the infimum is taken over all couplings between $\mu_{1}$ and $\mu_{2}$.

Assuming that $\mu\in\mathscr{M}$, we consider an evolution of weights $\mathbf{w}=(w_{e_{1}},w_{e_{2}},\cdots,w_{e_{m}})$ according to

Our first result reads as follows.

Analogous to [20], we consider a quasi-normalized flow

As we mentioned above, $\alpha$-lazy random walks $\mu_{x}^{\alpha}(y)$ and $\mu_{2,x}^{\alpha}(y)$ are locally Lipschitz in $\mathbf{w}_{0}\in\mathbb{R}^{m}_{+}$. As a consequence, both $\mu(x,y)=\mu_{x}^{\alpha}(y)$ and $\nu(x,y)=\mu_{2,x}^{\alpha}(y)$ are appropriate candidates for $\mu(\cdot,\cdot)$ satisfying the assumptions in Theorems 2.1 and 2.2. Both the proofs of Theorems 2.1 and 2.2 are based on the following lines: Consider the differential system

where ${\bf{f}}(\mathbf{w}(t))=({f}_{1}(\mathbf{w}(t)),{f}_{2}(\mathbf{w}(t)),\cdots,{f}_{m}(\mathbf{w}(t)))$ represents the right hand side of the system (2.7) or (2.8). We first prove the local Lipschitz continuity of $\mathbf{w}$. Together with the ODE theory ([30], Chapter 6), this implies the local existence and uniqueness of solutions. Next, we prove there exists a constant $C$ such that

This leads to long time existence of solutions. More details are left to Section 4.

Addressing the convergence of solutions to systems (2.7) or (2.8) poses a significant challenge, and we do not know how to obtain general convergence results except for a few special cases involving particular graphs (see Section 5 below). Even so, the global existence of solution is sufficient for practical applications, such as in community detection problems, which will be discussed in Section 6.

In this section, we prove a key lemma to be used later. Using the same notations as in Section 2. we have the following:

In this section, we prove Theorems 2.1 and 2.2 by using the ODE theory.

Proof of Theorem 2.1. We divide the proof into two parts.

Part 1. Short time existence.

Set $w_{i}=w_{e_{i}}$, $i=1,2,\cdots,m$. Given any vector ${\bf{w}}_{0}=(w_{0,1},w_{0,2},\cdots,w_{0,m})\in\mathbb{R}^{m}_{+}$. In fact, the evolution of weights (2.7) is the ordinary differential system

where ${\bf w}=(w_{1},w_{2},\cdots,w_{m})\in\mathbb{R}^{m}_{+}$ and ${\mathbf{f}}=(f_{1},f_{2},\cdots,f_{m})$ is a map represented by

where $f_{i}(\mathbf{w})=W(\mu(x_{i},\cdot),\mu(y_{i},\cdot))-d(x_{i},y_{i})$ and $e_{i}=x_{i}y_{i}$, $i=1,2,\cdots,m$. From Lemma 3.1 and ([20], Lemma 2.1), we know that all $f_{i}(\mathbf{w})$, $i=1,2,\cdots,m$, are locally Lipschitz in $\mathbb{R}^{m}_{+}$, and so is ${\bf f}({\bf w})$. By the ODE theory ([30], Chapter 6), there exists a constant $T>0$ such that the ordinary differential system (4.1) has a unique solution ${\bf{w}}(t)$ on $[0,T]$.

Part 2. Long time existence.

According to the conclusion of the first part, we may define

If $T^{\ast}<+\infty$, then (4.1) has a unique solution ${\bf w}(t)$ on the time interval $[0,T^{\ast})$; moreover, according to the ODE theory ([30], Chapter 6), we have either

or

where $\phi(t)=\min\{w_{1}(t),w_{2}(t),\cdots,w_{m}(t)\}$ and $\Phi(t)=\max\{w_{1}(t),w_{2}(t),\cdots,w_{m}(t)\}$.

Let $e=xy\in E$ be fixed. Since

this together with (4.1) implies

Thus we have

Noting also that each coupling $A$ between $\mu(x,\cdot)$ and $\mu(y,\cdot)$ satisfies $A(u,v)\in[0,1]$ and $\sum_{u,v\in V}A(u,v)=1$, and that $d(u,v)\leq\sum_{\tau\in E}w_{\tau}$ for all vertices $u,v$, we obtain

where, in the first equality, $B$ is taken from all couplings between probability measures $\mu(x,\cdot)$ and $\mu(y,\cdot)$. In view of (4.1), it follows that

Then integration by parts gives

Combining (4.5) and (4.7), we have

for all $t\in[0,T^{\ast})$, which contradicts (4.2) and (4.3). Therefore $T^{\ast}=+\infty$, and thus (4.1) has a unique solution $\mathbf{w}(t)$ on $[0,+\infty)$. $\hfill\Box$

Proof of Theorem 2.2.

Given ${\bf{w}}=(w_{e_{1}},w_{e_{2}},\cdots,w_{e_{m}})\in\mathbb{R}^{m}_{+}$. Let ${\bf{g}}:\mathbb{R}^{m}_{+}\rightarrow\mathbb{R}^{m}$ be a vector-valued function written as ${\bf{g}}({\bf{w}})=(g_{1}({\bf{w}}),g_{2}({\bf{w}}),\cdots,g_{m}({\bf{w}}))$, where

and $e_{i}=x_{i}y_{i}$. From Lemma 3.1 and ([20], Lemma 2.1), we conclude that ${\bf{g}}$ is locally Lipschitz in $\mathbb{R}^{m}_{+}$, namely if $\Omega\subset\mathbb{R}^{m}_{+}$ satisfies $\overline{\Omega}\subset\mathbb{R}^{m}_{+}$, then there exists a constant $C$ depending only on $\Omega$ such that

Hence, according to the ODE theory ([30], Chapter 6), there exists some $T>0$ such that the flow (2.8) has a unique solution ${\bf{w}}(t)$ on $[0,T]$. Let

If $T^{\ast}<+\infty$, then (2.8) has a unique solution ${\bf w}(t)=(w_{e_{1}}(t),w_{e_{2}}(t),\cdots,w_{e_{m}}(t))$ for all $t\in[0,T^{\ast})$. However, the ODE theory ([30], Chapter 6) implies either

or

In view of (4.4) and (4.6), we obtain for each $i$,

This together with (2.8) gives for each $i$,

and