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.
Articles by others on the same topic
There are currently no matching articles.