Dynamic network curvature analysis

Dynamic network curvature analysis was conducted by simulating diffusion over the weighted network and measuring geometric changes^18,21. First, the graph Laplacian L was determined as

where I is the identity matrix, CN is the shifted correlation matrix of edges in the network and K is the weighted degree or row-sum of CN.

The graph Laplacian represents the divergence of weighted differences in a discrete graph and served as a crucial tool to efficiently simulate diffusion at multiple pseudotime/scale parameters τ. A diffusion distribution matrix D was computed using the matrix exponential of L:

Each row of D indicates a probability distribution corresponding to one diffusion process with an initial Dirac delta δi concentrated at a single vertex i then diffused over pseudotime τ to arrive at a diffused distribution. We applied this step for 101 values of τ ranging in the form log₁₀(τ) ∈ [− 2,2].

In each diffused graph, Ollivier-Ricci curvature (ORC) κ was computed for each edge in the graph by first computing the Wasserstein distance W1 between two probability distributions:

as the minimum total cost for all couplings γ that satisfy marginals pi and pj, which signify probability distributions of vertex weights initially concentrated at vertex i and j respectively diffused for the same pseudotime τ, with transport cost d specified by the shortest path length between each vertex. The Wasserstein distance (W1) thus indicates optimal transport distance as a measure of closeness between the two diffused distributions. Then, ORC subsequently transforms this value by the following formula:

where dij is the direct distance between the two vertices defined above. Curvature κ can indicate positive convergence (clique-like) or negative divergence (tree-like) among diffused probability distributions in the graph, revealing the geometric structure of the graph (i.e. clusters, branching).

After measuring all edge curvature values over the diffusion evolution, we determined a threshold τcrit as the first pseudotime/scale when the upper 99^th percentile of all edges exceeded κ≥ 0.75. For each edge, we determine κcrit to be the value of κ at τcrit. We additionally define κ¯crit as the integral κ¯crit=∫0critκ, to represent a smoothed estimate of curvature during diffusion up to τcrit.