Weighted graph

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 $c_{xy}=c_{yx}$, and optional nonnegative killing weights ${\kappa }_x$. AssumeThe Markov chain moves from $x$ to $y$ with probability $c_{xy}/{\mu }_x$ and goes to a cemetery state with probability ${\kappa }_x/{\mu }_x$. These probabilities sum to one. With no killing, detailed balance holds with respect to the measure $\mu$; normalization gives a stationary distribution when its total mass is finite.

For example, electrical conductances $1$ and $3$ on the two edges incident to an graph vertex give outgoing probabilities $1/4$ and $3/4$. 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.