Given a weighted graph, where the nodes add and subtract from each other. Is there convergence?

Question

Informally: Assume you have a set of weighted nodes (each node has a value between 0 and 1). Further, the nodes may influence each other by either adding to connected nodes or subtracting from them. Is there a convergent distribution of values?

Formally: Assume a graph $G =\langle N, w, R_+, R_-\rangle$, where

• $N$ is a set of nodes,
• the weighting $w$ is a function from $N$ to $[0,1]$
• the support relationship $R_+$ is a binary relation on $N$
• the attack relationship $R_-$ is a binary relation on $N$

Let the damping factor $d$ be such that $0 < d \leq 1$.

Let $f^i$ ($i \in \mathbb{N} $) be a function from N to $\mathbb{R}$ such that for any $v\in N$,

• if $i = 0$, then $f^i(v) = w(v)$,
• otherwise,
  $$ f^i(v) = w(v) + d \ (\sum_{x \in \{y | y R_+ v \} } f^{i-1}(x) - \sum_{x \in \{y | y R_- v \} } f^{i-1}(x) ) $$

Does $f^i$ converge?

Answer 1

If we interpret $f$ as vector indexed by $N$ and $R$'s as matrices representing the characteristic function of the relation, i.e., that have $1$ in appropriate row and column if and only if $u\ R\ v$, then we can set $R = R_+ - R_-$ and observe that

\begin{align} f^i &= w + d(R_+ f^{i-1} - R_- f^{i-1}) \\ &= w+d(R_+-R_-)f^{i-1} \\ &= w+dRf^{i-1} \\ &= w+dR(w+dRf^{i-2}) \\ &= w+dR(w+dR(w+dR(w+dRf^{i-3}))) \\ &\hspace{6pt}\vdots \\ &= \sum_{k=0}^i (dR)^kw = \left(\sum_{k=0}^i (dR)^k\right)w \end{align}

The matrix power series converge iff $\rho(dR) < 1$ (see convergent matrix and spectral radius), in particular it does when $\|dR\|<1$. In such case $I-(dR)$ is invertible and $\sum_{k=0}^{\infty} (dR)^k = (I-dR)^{-1}$.

To give you some concrete examples, for $d = 1$ we can use $$N = \{1,2\}, w(1) = 1, w(2) = 1, R_+=N^2, R_- = \varnothing$$ and then $f$ grows infinitely, by $1$ every turn.

You can also create a cycle: $$N = \{1,2\}, w(1) = 1, w(2) = 0, R_+ = \{1 \to 2, 2\to 1\}, R_- = \{1 \to 1, 2\to 2\},$$ where $f^i(x)$ flips between $w(x)$ and $1-w(x)$. You can also adjust that example so that $R_-$ is non-reflexive and perhaps also include a cost for attacking/supporting.

For $d = \frac{1}{2}$ you can take $$N = \{1,2,3,4,5\}, w(n) = 1, R_+ = N^2, R_- = \varnothing$$ so $f^i(n) = 1 + \frac{1}{2}(5\cdot f^{i-1}(n)-0)$ which is again unbounded.

I hope this helps $\ddot\smile$

Answer 2

In terminology of the first answer, the infinite sum $\sum_{k=0}^{\infty} (dR)^k$ can be generalised to $\sum_{k=0}^{\infty} c_k R^k$, where $c_k$ are suitable coefficients, i.e. those of a Taylor series. Then it should be possible to obtain convergence for all matrices $R$.

More specifically, consider $\sum_{k=0}^{\infty} \frac{1}{k!} R^k$ (which formally is the Maclaurin series for the exponential function). This converges, because $\frac{\rho(R)^k}{k!}$ converges to zero.