Dado un grafo ponderado, donde los nodos sumar y restar uno del otro. Hay convergencia?

Question

De manera informal: Suponga que tiene un conjunto de la ponderación de los nodos (cada nodo tiene un valor entre 0 y 1). Además, los nodos pueden influir en cada uno de los otros mediante la adición de nodos conectados o restar de ellos. Hay un convergentes distribución de los valores?

Formalmente: Asumir un gráfico de $G =\langle N, w, R_+, R_-\rangle$, donde

• $N$ es un conjunto de nodos,
• la ponderación $w$ es una función de $N$ $[0,1]$
• la relación de apoyo $R_+$ es una relación binaria en a $N$
• el ataque relación $R_-$ es una relación binaria en a $N$

Deje que el factor de amortiguamiento $d$ ser tal que $0 < d \leq 1$.

Vamos $f^i$ ($i \in \mathbb{N} $) ser una función de N a $\mathbb{R}$ tal que para cualquier $v\in N$,

• si $i = 0$,$f^i(v) = w(v)$,
• de lo contrario,
  $$ 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) ) $$

Qué $f^i$ convergen?

Answer 1

Si interpretamos $f$ como vector indexado por $N$ $R$'s, así como las matrices que representan la función característica de la relación, es decir, que han $1$ en fila y la columna si y sólo si $u\ R\ v$, entonces podemos establecer $R = R_+ - R_-$ y observar que

\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}

La matriz de potencia de la serie converge iff $\rho(dR) < 1$ (ver convergente de la matriz y espectral de radio), en particular cuando se $\|dR\|<1$. En tal caso, $I-(dR)$ es invertible y $\sum_{k=0}^{\infty} (dR)^k = (I-dR)^{-1}$.

Para dar algunos ejemplos concretos, para $d = 1$ podemos utilizar $$N = \{1,2\}, w(1) = 1, w(2) = 1, R_+=N^2, R_- = \varnothing$$ y, a continuación, $f$ crece infinitamente, por $1$ cada turno.

También puede crear un ciclo: $$N = \{1,2\}, w(1) = 1, w(2) = 0, R_+ = \{1 \to 2, 2\to 1\}, R_- = \{1 \to 1, 2\to 2\},$$ donde $f^i(x)$ invierte entre el$w(x)$$1-w(x)$. También puede ajustar el ejemplo de lo que $R_-$ es no-reflexiva y quizás también incluyen un costo de ataque/apoyo.

Para $d = \frac{1}{2}$ usted puede tomar $$N = \{1,2,3,4,5\}, w(n) = 1, R_+ = N^2, R_- = \varnothing$$ por lo $f^i(n) = 1 + \frac{1}{2}(5\cdot f^{i-1}(n)-0)$ cual, nuevamente, es ilimitado.

Espero que esto ayude a $\ddot\smile$

Answer 2

En la terminología de la primera respuesta, la infinita suma $\sum_{k=0}^{\infty} (dR)^k$ puede ser generalizado a $\sum_{k=0}^{\infty} c_k R^k$ donde $c_k$ son adecuados coeficientes, es decir, de una serie de Taylor. A continuación, debería ser posible obtener la convergencia de todas las matrices $R$.

Más específicamente, considere la posibilidad de $\sum_{k=0}^{\infty} \frac{1}{k!} R^k$ (que formalmente es la serie de Maclaurin para la función exponencial). Esto converge, porque $\frac{\rho(R)^k}{k!}$ converge a cero.