Random walk on a multigraph
ID: random-walk-on-a-multigraph
For a loopless undirected multigraph, let be the number of parallel graph edges between distinct graph vertices . Assume . Choosing an incident edge uniformly gives the transition probabilitiesThe measure is reversible since . It becomes a stationary distribution only when the total vertex degree is finite. On a finite graph this holds; on an infinite locally finite graph, a reversible measure need not be a normalizable probability measure. Self-loops need a stated incidence-counting convention and are excluded from the formula here.
For example, two parallel edges from to and one edge from to give degrees , stationary probabilities , and . Collapsing the parallel edges to a single unweighted edge would change the random walk.
New to topics? Read the docs here!