Newman, Message passing methods on complex networks
2022-11-12 → 2026-08-14
Giant component example#
Newman begins by letting $\mu_i$ be the probability that node $i$ does not belong to the giant connected component. If the corresponding events for its neighbors are treated as independent, then
$$\mu_i=\prod_{j\in\mathcal{N}_i}\mu_j.\tag{1}$$
But this is incorrect for two distinct reasons:
- Neighbor dependence: if two neighbors are connected by an edge, either both are in the giant component or neither is, so their probabilities $\mu_j$ are correlated.
- Backtracking through $i$: a neighbor $j$ may belong to the giant component only through its connection to $i$. In that case, $j$ cannot also be the route that establishes $i$’s membership. This motivates evaluating the message from $j$ after removing $i$ from the network.
Define $\mu_{i\leftarrow j}$ as the probability that $j$ is not in the giant component after $i$ is removed. Then $i$ is outside the giant component only if this holds for every neighbor:
$$\mu_i=\prod_{j\in\mathcal{N}_i}\mu_{i\leftarrow j}.\tag{2}$$
Each directed message is computed recursively from the other messages arriving at $j$, excluding the immediate return to $i$:
$$\mu_{i\leftarrow j}=\prod_{\substack{k\in\mathcal{N}_j\\k\ne i}}\mu_{j\leftarrow k}.\tag{3}$$
This is the message passing equation.
Across network problems, we can study such equations theoretically through their fixed points and stability, or iterate them numerically to compute node-level and global quantities.