Weighted graph Created 2026-09-24 Updated 2026-11-05
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.
For two configurations , the weighted Hamming distance for the noisy voter model is , where is the stationary distribution of the copying walk. On a connected undirected graph, . Positive weights make this a metric, with values between zero and one.
Couple two chains using the same uniformly selected vertex, refresh decision, fresh bit and copied neighbor. If the refresh probability is , stationarity gives . Copying redistributes disagreements without increasing their stationary-weighted total in expectation; refreshes remove them. The factor belongs to the single-vertex update convention, not a simultaneous update of every vertex.[ref]