La centralidad del vector propio como caso límite de la centralidad de Katz

Question

La centralidad del vector propio como caso límite de la centralidad de Katz

limites
red
Matemáticas
Teoría de grafos
álgebra lineal
valores propios-vectores propios

jmbejara

En Redes de Newman (2ª ed.), la centralidad del vector propio (a veces llamada centralidad de Bonacich) se define como el vector $x$ que resuelve

A X = k X,

$A x = \kappa x,$ dónde

κ

$\kappa$ es el valor propio principal (mayor, más positivo) de la matriz de adyacencia

A

$A$ . La centralidad de Katz se define como el vector

y

$y$ que resuelve

y = α A y + 1,

$y = \alpha A y + \bf 1,$ dónde

0 \leq α < κ^{- 1}

$0 \leq \alpha < \kappa^{-1}$ y

1

$\bf 1$ es un vector conforme de unos. Eso es,

y = (I - α A)^{- 1} 1

$y = ({\bf I} - \alpha A)^{-1} {\bf 1}$ .

Pregunta: En el libro (p.164), se dice que en el límite como $\alpha \nearrow \kappa^{-1}$ , la centralidad de Katz converge a la centralidad del vector propio. ¿Cómo puedo probar esto?

Pensamientos hasta ahora:

Entiendo que, cuando exista, $y = ({\bf I} - \alpha A)^{-1} {\bf 1} = {\bf 1} + \alpha A {\bf 1} + \alpha^2 A^2 {\bf 1} + ...$ . Esta suma diverge cuando $\alpha = \kappa$ . En ese punto, $\det({\bf I} - \alpha A) = 0$ . Esto significa que $\det(\alpha^{-1}{\bf I} - A) = 0$ , que es la ecuación característica cuyas raíces $\alpha^{-1}$ son los valores propios de $A$ . Esto significa que $({\bf I} - \alpha A)^{-1} {\bf 1}$ está bien definido para $\alpha \in [0, \kappa^{-1})$ . No estoy seguro de cómo incorporar esto en la prueba final.
El libro menciona que la centralidad de un nodo solo tiene sentido en relación con la centralidad de otros nodos. Entonces, tal vez debería asumir que la centralidad del vector propio, por ejemplo, debería definirse como $\mathcal C^{e} = \frac{x}{\|x\|}$ y la centralidad de Katz como $\mathcal C^{k} = \frac{y}{\|y\|}$ .

Editar:

He publicado mi intento de solución a continuación. Todavía me gustaría verificar algunos aspectos de la misma.

eranreches

¿La red es dirigida o no?

jmbejara

@eranreches Tanto el vector propio como la centralidad de Katz se definen para redes dirigidas y no dirigidas. Entonces, sería mejor asumir que la red está dirigida.

Respuestas (2)

La centralidad del vector propio como caso límite de la centralidad de Katz

@eranreches Tanto el vector propio como la centralidad de Katz se definen para redes dirigidas y no dirigidas. Entonces, sería mejor asumir que la red está dirigida.

JG · Answer 1

Supongamos que la red no está dirigida, es simétrica y, además, que el gráfico es irreducible (equivalente a conexo), por lo que se cumple la forma estricta del teorema de Perron-Frobenius. Escribir $A$ en la descomposición espectral de modo que

A = \sum_{i = 1}^{norte} λ_{i} v_{i} v_{i}^{T},

$A=\sum_{i=1}^n \lambda_i v_iv_i^T,$ donde el

v_{i}

$v_i$ son los vectores propios (y forman una base ortonormal) y

κ_{1} = λ_{1} > λ_{2} \geq \dots \geq λ_{n} > - κ

$\kappa_1=\lambda_1>\lambda_2\geq \ldots\geq \lambda_n>-\kappa$ son los valores propios. Por el teorema de Perron-Frobenius,

v_{1} > 0

$v_1>0$ por componentes. Esto es

x

$x$ en su notación. Se deduce del límite de von Neumann que usó para

α < κ^{- 1}

$\alpha<\kappa^{-1}$ ,

(I - α A)^{- 1} = \frac{1}{1 - α k} X X^{T} + \sum_{i = 2}^{norte} \frac{1}{1 - α λ_{i}} v_{i} v_{i}^{T} .

$(I-\alpha A)^{-1}=\frac{1}{1-\alpha\kappa}xx^T +\sum_{i=2}^n \frac{1}{1-\alpha \lambda_i}v_iv_i^{T}.$

ahora calculamos

\begin{aligned} (I - α A)^{- 1} 1 = \frac{1}{1 - α k} X (X^{T} 1) + \sum_{i = 2}^{norte} \frac{1}{1 - α λ_{i}} v_{i} (v_{i}^{T} 1) . \end{aligned}

$\begin{align} (I-\alpha A)^{-1}\mathbf{1}=\frac{1}{1-\alpha\kappa}x(x^T\mathbf{1}) +\sum_{i=2}^n \frac{1}{1-\alpha \lambda_i}v_i(v_i^{T}\mathbf{1}). \end{align}$

La clasificación de centralidad de vectores propios solo se preocupa por los valores relativos de los componentes, por lo que podemos multiplicar con seguridad por el escalar $1-\alpha \kappa$ . Esto da

(1 - α k) (I - α A)^{- 1} 1 = X (X^{T} 1) + \sum_{i = 2}^{norte} \frac{1 - α k}{1 - α λ_{i}} v_{i} (v_{i}^{T} 1) .

$(1-\alpha \kappa)(I-\alpha A)^{-1}\mathbf{1}=x(x^T\mathbf{1})+ \sum_{i=2}^n \frac{1-\alpha \kappa}{1-\alpha \lambda_i}v_i(v_i^{T}\mathbf{1}).$ Como

α \to κ^{- 1}

$\alpha\to \kappa^{-1}$ , los términos de la suma desaparecen cuando los denominadores están acotados de

0

$0$ por la estricta desigualdad en Perron-Frobenius, y esto converge a

x (x^{T} 1)

$x(x^T\mathbf{1})$ .

x^{T} 1

$x^T\mathbf{1}$ es solo un escalar positivo del teorema de Perron-Frobenius, por lo que el vector límite es

x

$x$ hasta un factor escalar.

+1: aunque me interesa principalmente el caso de los gráficos dirigidos, esta es una prueba realmente excelente para este caso. ¡Gracias!
@jmbejara Gracias! En el caso dirigido, suponiendo una fuerte conectividad, por lo que Perron-Frobenius aún se mantiene, creo que todavía se puede hacer esto usando el SVD. $x$ es un vector propio correspondiente a $\kappa$ , así también de $I-\alpha A$ , entonces $I-\alpha A=(1-\alpha \kappa) xx^T+\sum_{i=2}^n (1-\alpha \sigma_i)u_{i,\alpha}v_{i,\alpha}^T$ , dónde $u_{i,\alpha}$ y $v_{i,\alpha}$ son los vectores singulares izquierdo/derecho. Entonces $(I-\alpha A)^{-1}=(1-\alpha \kappa)^{-1} xx^T+\sum_{i=2}^n (1-\alpha \kappa)^{-1}v_{i,\alpha}u_{i,\alpha}^T$ , y la misma derivación debería funcionar, creo. Puede que me esté perdiendo algo obvio.
¡Fresco! ¿Necesitamos alguna condición para decir que $u_{1,\alpha} = v_{1,\alpha} = x$ ? No estoy seguro de qué condiciones podríamos necesitar agregar (si las hay) para decir que si $\kappa$ es un valor propio de $A$ , entonces $\kappa$ es un valor singular de $A$ . Nosotros ya tenemos $\kappa > 0$ .
Ah, ya veo. ¿Quizás la forma normal de Jordan es el camino correcto? Intuitivamente, escribir $A=P^{-1}\Lambda P$ dónde $\Lambda$ consta de bloques Jordan donde el bloque Jordan para $\kappa$ es sencillo entonces $I-\alpha A=P^{-1}(I-\alpha \Lambda)P$ . $(I-\alpha \Lambda)^{-1}$ está en forma de Jordan (más complicada), pero las diagonales se invierten y las diagonales fuera de otros bloques de Jordan no son tan malas, así que multiplicando por $1-\alpha \kappa$ debe eliminar todos los términos en el límite de los bloques Jordan, excepto dejar un $1$ en la diagonal superior. Creo que la matriz de rango uno resultante es $xx^T$ , pero no estoy seguro.

jmbejara · Answer 2

Considere la definición de centralidad de vector propio dada arriba donde $\mathcal C^e = \frac{x}{\|x\|}$ y la definición de centralidad de Katz, donde $\mathcal C^k(\alpha) = \frac{({\bf I} - \alpha A)^{-1} {\bf 1}}{\|({\bf I} - \alpha A)^{-1} {\bf 1}\|}$ . Cuando $\alpha < \kappa^{-1}$ , recuerda que podemos escribir $y = ({\bf I} - \alpha A)^{-1} {\bf 1} = {\bf 1} + \alpha A {\bf 1} + \alpha^2 A^2 {\bf 1} + ...$ .

Definir $a_n(\alpha) = {\bf 1} + \alpha A {\bf 1} + \alpha^2 A {\bf 1}\, + ... + \, \alpha^n A^n {\bf 1}$ , dejar $a_0 = {\bf 1}$ . Definir $b_n(\alpha) = \|a_n(\alpha)\|$ .

Dadas estas definiciones, nos gustaría calcular el límite

\underset{α ↗ k^{- 1}}{límite} C^{k} (α) = \underset{α ↗ k^{- 1}}{límite} \underset{norte \to \infty}{límite} \frac{a_{norte} (α)}{b_{norte} (α)},

$\lim_{\alpha \nearrow \kappa^{-1}} \mathcal C^k(\alpha) = \lim_{\alpha \nearrow \kappa^{-1}} \lim_{n\rightarrow\infty} \frac{a_n(\alpha)}{b_n (\alpha)},$ dónde

κ

$\kappa$ es el valor propio principal de

A

$A$ .

Tenga en cuenta que $\lim_{n \rightarrow \infty} a_n/b_n$ se define para todos los valores $\alpha \in [0, \kappa^{-1})$ . También, $a_n$ y $b_n$ son finitos para $n < \infty$ . Por lo tanto, podemos cambiar el orden de los límites de modo que

\underset{α ↗ k^{- 1}}{límite} C^{k} (α) = \underset{norte \to \infty}{límite} \underset{α ↗ k^{- 1}}{límite} \frac{a_{norte} (α)}{b_{norte} (α)} = \underset{norte \to \infty}{límite} \frac{a_{norte} (k^{- 1})}{b_{norte} (k^{- 1})}

$\lim_{\alpha \nearrow \kappa^{-1}} \mathcal C^k(\alpha) = \lim_{n\rightarrow\infty} \lim_{\alpha \nearrow \kappa^{-1}} \frac{a_n(\alpha)}{b_n(\alpha)} = \lim_{n\rightarrow\infty} \frac{a_n(\kappa^{-1})}{b_n(\kappa^{-1})}$

Definir

X_{norte + 1} = \frac{A^{norte + 1} X_{0}}{‖ A^{norte + 1} X_{0} ‖},

$x_{n+1} = \frac{A^{n+1} x_0}{\|A^{n+1} x_0\|},$ con

x_{0} = 1

$x_0 = {\bf 1}$ . Asumiendo las condiciones necesarias para el algoritmo de iteración de potencia ,

x_{n + 1} \to x

$x_{n+1} \rightarrow x$ , dónde

x

$x$ es un vector propio asociado con el valor propio principal de

A

$A$ .

Desde $\det \left({\bf I} - \frac{1}{\kappa} A\right) = 0$ , lo sabemos $a_n$ y $b_n$ divergir cuando $\alpha = \kappa^{-1}$ . Asumir que $A$ no es negativo (los pesos de los bordes de la red no son negativos). Entonces $b_n$ también es estrictamente monótona. Esto nos permite usar el teorema de Stolz-Cesàro :

\underset{norte \to \infty}{límite} \frac{a_{norte}}{b_{norte}} = \underset{norte \to \infty}{límite} \frac{a_{norte + 1} - a_{norte}}{b_{norte + 1} - b_{norte}} .

$\lim_{n\rightarrow\infty} \frac{a_n}{b_n} = \lim_{n\rightarrow\infty} \frac{a_{n+1}-a_n}{b_{n+1}-b_n}.$ Calculador,

\frac{a_{norte + 1} - a_{norte}}{b_{norte + 1} - b_{norte}} = \frac{α^{norte + 1} A^{norte + 1} 1}{‖ a_{norte + 1} ‖ - ‖ a_{norte} ‖} = \frac{k^{- norte - 1} ‖ A^{norte + 1} 1 ‖ X_{norte + 1}}{‖ a_{norte + 1} ‖ - ‖ a_{norte} ‖} \geq \frac{k^{- norte - 1} ‖ A^{norte + 1} 1 ‖ X_{norte + 1}}{‖ k^{- norte - 1} A^{norte + 1} 1 ‖} = X_{norte + 1},

$\frac{a_{n+1}-a_n}{b_{n+1}-b_n} = \frac{\alpha^{n+1} A^{n+1} {\bf 1}}{\|a_{n+1}\| - \|a_n\|} = \frac{\kappa^{-n-1} \|A^{n+1} {\bf 1}\| \, x_{n+1} }{\|a_{n+1}\| - \|a_n\|} \geq \frac{\kappa^{-n-1} \|A^{n+1} {\bf 1}\| \, x_{n+1} }{\|\kappa^{-n-1} A^{n+1} {\bf 1}\|} = x_{n+1},$ donde la desigualdad se sigue de la desigualdad del triángulo inverso. Desde

‖ a_{n} (κ^{- 1}) ‖

$\|a_n(\kappa^{-1})\|$ diverge y es monótonamente creciente, la desigualdad se cumple con la igualdad en el límite. De este modo,

\underset{α ↗ k^{- 1}}{límite} C^{k} (α) = \underset{norte \to \infty}{límite} \frac{a_{norte} (k^{- 1})}{b_{norte} (k^{- 1})} = \underset{norte \to \infty}{límite} X_{norte} = X = C^{mi} .

$\lim_{\alpha \nearrow \kappa^{-1}} \mathcal C^k(\alpha) = \lim_{n\rightarrow\infty} \frac{a_n(\kappa^{-1})}{b_n(\kappa^{-1})} = \lim_{n\rightarrow\infty} x_n = x = \mathcal C^e.$

Notas:

Probablemente debería tener un poco más de cuidado al cambiar el orden de los límites.
Debo aclarar las condiciones necesarias para la iteración de potencia. (Véase Perron-Frobenius.)

La centralidad del vector propio como caso límite de la centralidad de Katz

jmbejara

eranreches

jmbejara

Respuestas (2)

JG

jmbejara

JG

jmbejara

JG

jmbejara

Parámetro para la centralidad de Katz de un gráfico

¿Cuál es el significado de los valores propios más grande/más pequeño?

¿Cuál es la multiplicidad del mayor valor propio de un gráfico?

¿Cuáles son los vectores propios de esta matriz y si estos son los vectores propios, por qué no son ortogonales?

¿Todo espacio propio de la potencia exterior ⋀kA⋀kA\bigwedge^k A corresponde a un subespacio invariante?

Problema relacionado con el espacio propio y el rango de alguna matriz

Si un valor propio de una matriz de enteros se encuentra en el círculo unitario, ¿debe ser una raíz de la unidad?

¿Los vectores propios incluyen vectores complejos?

Isometría sin valores propios

Encuentre todos los valores propios de la matriz AAA sin calcular su c. polinomio