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

TY - JOUR

T1 - Walk-Independence Probabilities and WIP Centrality

T2 - A new heuristic for diffusion probabilities in networks

AU - King, Maia

PY - 2024/7

Y1 - 2024/7

N2 - 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 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.

AB - 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 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.

UR - http://www.scopus.com/inward/record.url?scp=85186609772&partnerID=8YFLogxK

U2 - 10.1016/j.socnet.2023.11.007

DO - 10.1016/j.socnet.2023.11.007

M3 - Article

SN - 1879-2111

VL - 78

SP - 173

EP - 183

JO - Social Networks

JF - Social Networks

ER -