commute time concept

Definition	The expected number of steps a random walk on a graph needs to go from one node to another and back. Divided by the graph's volume it is the resistance, which a particular scaling of the spectral embedding makes equal to the squared Euclidean distance. Equation 0.20. Also resistance.
Example	On a path of three nodes the commute time between the ends is 8 steps, and dividing by the volume, 4, gives the resistance, 2.
Book	Data Mining as Observation, draft 0.2, commit `f3914f0`; entry id `commute-time`, kind concept.
Status	no ledger row names this entry. Corrections: none recorded.
Defining equation	Book equation 0.20.
Assumptions and scope	The expected number of steps a random walk needs to go from one node to another and back, the hitting time there plus the hitting time back, so it is symmetric and zero from a node to itself. The resistance is the commute time divided by the volume, and the squared Euclidean distance in the embedding of equation 0.20 equals the resistance, not the commute time itself. On a large neighbourhood graph of a shape of dimension three or more the resistance converges to one over each degree, uniformly over pairs, so it depends on two nodes only through their degrees and carries no geometry, which is why the magnitude of the spectral embedding is degree noise. The program’s first claim of a commute-metric form was self-refuted, NEG-1.
Prior art	none recorded
Evidence	`lean/DataMiningAsObservation/CommuteTime.lean`
Reviewed	semantic review 2026-09-06; generated 2026-09-10 from records at the commits on the provenance page.

Steps there and back for a random walk, whose scaling by the volume is the resistance.

Equation

Book equation 0.20.

\[\Psi_i=\left(\frac{u_k(i)}{\sqrt{\lambda_k\,d_i}}\right)_{k\ge2},\qquad \|\Psi_i-\Psi_j\|^{2}=R(i,j)=\frac{C(i,j)}{\operatorname{vol}(G)}.\]

Conditions

The expected number of steps a random walk needs to go from one node to another and back, the hitting time there plus the hitting time back, so it is symmetric and zero from a node to itself. The resistance is the commute time divided by the volume, and the squared Euclidean distance in the embedding of equation 0.20 equals the resistance, not the commute time itself.
On a large neighbourhood graph of a shape of dimension three or more the resistance converges to one over each degree, uniformly over pairs, so it depends on two nodes only through their degrees and carries no geometry, which is why the magnitude of the spectral embedding is degree noise. The program’s first claim of a commute-metric form was self-refuted, NEG-1.

Conditions are curated in entries.toml rather than read from a record.

Ledger

none

First stated

Chapter 0 section 0.10 of Data Mining as Observation, equation 0.20, with von Luxburg, Radl, and Hein, 2014, read in chapter 3 section 3.3 and the program’s collapse proof in the-angular-observer/theorem.md:110-146.

Measurements

Where the book states it	Numbers, as the book’s sources table records them	Source
chapter 3 section 3.3	resistance converges to 1 over d_i plus 1 over d_j, simplex argument, radius converges to 1 over root d_i	`the-angular-observer/theorem.md:110-146`

Failures and corrections

none

Invariance envelope

none declared

Machine checked

lean/DataMiningAsObservation/CommuteTime.lean, theorems commute_symm, commute_self, resistance_symm, commute_eq_resistance_mul, collapsed_congr, collapsed_const, at observation-data-mining f3914f0; what the check covers is stated in the book’s appendix C.

Used in

Data Mining as Observation chapters 0, 3.

spectral embedding; Laplacian; geodesic distance; degree; graph.

Status

Generated 2026-09-10 by encyclopedia/generate.py; book at observation-data-mining f3914f0; the commit of every record is listed in the encyclopedia’s provenance.

← commit hashconcentrated →