An edge-weighted graph assigns a numerical weight to each graph edge. The meaning depends on the model: a weight can be a length, a cost, or an electrical conductance. Arbitrary weights do not automatically define transition probabilities.
For the random walk convention used here, take a locally finite undirected graph with symmetric nonnegative electrical conductances , and optional nonnegative killing weights . AssumeThe Markov chain moves from to with probability and goes to a cemetery state with probability . These probabilities sum to one. With no killing, detailed balance holds with respect to the measure ; normalization gives a stationary distribution when its total mass is finite.
For example, electrical conductances and on the two edges incident to an graph vertex give outgoing probabilities and . Treating the same weights as electrical resistances would require reciprocal electrical conductances and reverse these preferences. The distinction is essential in the electrical network interpretation.
New to topics? Read the docs here!