图上随机游走的‘distance’定义是什么？与游走长度有何区别？

Great question—this is a super common point of confusion, especially when diving into cluster significance research where random walk metrics pop up a lot. Let’s break this down clearly, and make sure we separate it from the simpler "random walk length" you’re contrasting it with.

First: The Core Distinction #

Let’s start with the basics to avoid mix-ups:

• Random walk length is just a parameter of the random walk process: it refers to the number of steps the walker takes (e.g., a 5-step random walk). It’s a discrete count, used to define how far the walker can move from its starting node.
• Random walk distance is a metric that quantifies the structural relationship between two nodes using the behavior of random walks. It’s a non-negative real number, not just a step count, and it captures how "connected" or "similar" two nodes are across the entire graph (not just via the shortest path).

Common Definitions of Random Walk Distance (Used in Cluster Significance) #

In the context of cluster statistical significance, these are the most widely used variants:

• Commute Time Distance
  This is one of the most foundational random walk distances. It’s defined as the sum of the expected time for a random walker starting at node u to first reach node v, plus the expected time to go back from v to u:

  C(u, v) = E[T_uv] + E[T_vu]
  

  where T_uv is the first passage time from u to v. Intuitively, if two nodes are in the same dense cluster, their commute time will be much smaller than nodes across clusters—since there are far more paths a walker can take between them. This makes it perfect for measuring cluster compactness.

• Similarity-Derived Random Walk Distance
  Often, researchers first define a random walk similarity between nodes, then convert it to a distance. For example:

  • Use the probability that a k-step random walk starting at u ends at v (P^k(u, v)).
  • Convert this to a distance using something like d(u, v) = -log(P^k(u, v)) (so higher probability = smaller distance) or by measuring the L2/cosine distance between the nodes’ k-step walk probability vectors.
    In cluster significance tests, this distance helps show that nodes within a real cluster have significantly higher mutual reachability (smaller distance) than nodes in a randomly assigned group.

• Symmetrized Hitting Time Distance
  The raw hitting time (E[T_uv], the expected time to first reach v from u) is asymmetric (walking from u to v might take longer than v to u), so it’s often symmetrized to make a valid distance metric. Common versions include taking the average of E[T_uv] and E[T_vu], or using the commute time (which is already symmetric, as we saw earlier).

Why This Matters for Cluster Statistical Significance #

In papers and blog posts about cluster significance, random walk distances are used to:

1. Quantify how "tight" a cluster is (nodes inside should have much smaller random walk distances than nodes outside).
2. Compare the observed cluster’s distance distribution to distributions from randomly generated clusters. If the real cluster’s average internal distance is significantly smaller than random groups, that’s evidence the cluster isn’t just a fluke—it has statistical significance.

内容的提问来源于stack exchange，提问作者user3813057