Commute time distance

The commute time distance is the second of the four hypergraph metrics. It comes from the same random walk as resistance distance, but measures something subtly different — and that difference matters.

Definition

Let $h(u, v)$ be the expected first-passage time of the harmonic random walk from $u$ to $v$ — the expected number of steps to first reach $v$ starting from $u$. The commute time distance is the symmetric round trip:

It lives at ProofAtlas/Metric/CommuteTime/CommuteTime.lean:36.

Intuition: random-walk efficiency

If you stand at $u$ and let the random walk run, $h(u, v)$ is how long you expect to wait before bumping into $v$. The commute time is your wait if you also have to come back. It's a natural notion of "how reachable is $v$ from $u$" that takes into account every path, weighted by its likelihood.

A short commute time means there are many likely short routes from $u$ to $v$ and back. A long commute time means $v$ is a needle in a haystack from $u$'s vantage point — the walk is likely to get lost visiting other vertices first.

Relationship to resistance

For a finite connected reversible Markov chain with conductance $C = (C_{u, v})$, total weight $T = \sum_{u, v} C_{u, v}$, and effective resistance $R_{\mathrm{eff}}(L_C; u, v)$ of the associated Laplacian $L_C = D - C$:

This is the Chandra–Raghavan–Ruzzo–Smolensky / Doyle–Snell identity. Up to the global factor $T$, commute time is just resistance.

For the harmonic random walk this identity is formalised in ProofAtlas/Markov/CommuteTime.lean. So the question "why have both?" is sharper than it looks: the multiplicative factor $T$ depends on the total conductance budget of the hypergraph, which depends on $|V|$ and the colour weights $\alpha$.

Where the two diverge — degree contamination

The single difference between resistance and commute time is the $T$ factor. $T$ scales like $|V|$ — total conductance grows with the graph size — so commute times scale quadratically with $|V|$ while resistances stay $O(1)$ for "geometrically close" pairs.

This is sometimes called the degree contamination of commute time: on a large random graph, almost every pair has commute time $\approx 2|V|$, drowning out the geometric information that resistance preserves. In small-world / scale-free regimes this is severe.

For ProofAtlas's use case — small connected components, $|V|$ in the dozens — the contamination is negligible and the two distances agree up to a global scale. The choice between them is then mathematical convenience: commute time is more natural for "how often does the random walk visit $v$?", resistance for "how strongly is $v$ wired into the network?".

Quality status

commuteTimeDist_isHypergraphMetric is certified as of the most recent commit — all four metric axioms come from the proven commuteTimeDist_self, _symm, _triangle, and hittingTime_nonneg lemmas in Metric/CommuteTime/{CommuteTime,HittingTime}.lean. The sensitivity witnesses use the same hypothesis pattern as resistance.

The compute-layer Float implementation is still TODO — it would require porting the hitting-time matrix inversion (currently noncomputable) to the Pipeline/ layer. Once that lands, an #atlas.commute A B command can be wired up to mirror #atlas.resistance.

Try it

#atlas.commute is currently not implemented as a command. Until the Float compute path lands, the closest thing is verifying the quality certificate:

→ #atlas.status commuteTimeDist should report ✓ certified.

For the metric-agnostic theorems that apply to commute time (and every other registered metric) see Hyperbolicity.

References

[BDF26] §5.2 — commute time on hypergraphs.
[CRRS96] Chandra, Raghavan, Ruzzo, Smolensky, The electrical resistance of a graph captures its commute and cover times, Computational Complexity 6, 1996.