Walk-Independence Probabilities and WIP Centrality: a new heuristic for diffusion probabilities in networks

Calculating the true probability that a signal will be transmitted between any pair of nodes in a network is computationally hard. Diffusion centrality, which counts the expected number of times that a signal will be transmitted, is often used as a heuristic for this probability. But this formula can lead to distorted results when used in this way, because its summation of probabilities does not take account of the inclusion-exclusion principle. This paper provides a simple new formula for the probabilities of node-to-node diffusion in networks, which uses De Morgan's laws to account for the inclusion-exclusion principle. Like diffusion centrality, this formula is based on the assumption that the probabilities of a signal travelling along each walk in a network are independent. The probabilities it calculates are therefore called Walk-Independence Probabilities (WIP). These probabilities also provide two new centrality measures, WIP centrality and blocking centrality. Blocking centrality is a type of induced centrality which is calculated when some nodes block signals.