¿Cuáles son las condiciones para que la matriz de adyacencia de un gráfico no tenga un valor propio negativo con magnitud> = 1?

Question

Digamos que tengo un grafo (dirigido) $G$ con una matriz de adyacencia $A$.
Por el bien de la pregunta, asumamos que está normalizado por columnas (los pesos de las aristas están normalizados de manera que la suma de los pesos de las aristas de salida por nodo es igual a 1).
Me gustaría calcular la centralidad de los valores propios de sus nodos usando el método de la potencia, pero sé que en algunos casos puede que no converja (lo cual, si entiendo correctamente, ocurre si y solo si tiene un valor propio de -1).

Mi pregunta es: En general, ¿cuáles son las condiciones en el grafo para evitar este caso?
Específicamente, si uso la centralidad de page-rank (con factor de amortiguación < 1), ¿puedo estar seguro de evitar este caso (¿Para cualquier elección de vector de personalización?)

[Editado: Parece que puedo ser aún más específico: Si hay una arista con peso distinto de cero de cada nodo a cada nodo, ¿puedo estar seguro de no tener un valor propio de -1?]

Answer 1

Aquí está lo que tengo hasta ahora:

En un grafo bipartito, cada eigenvalor $\lambda$ tiene un eigenvalor correspondiente $-\lambda$ (ver por ejemplo esta respuesta en math.stackexchange, aunque no dice si solo un grafo bipartito tiene esta característica).
Entonces, para una matriz de adyacencia cuyas columnas suman a $1$ (que tiene un eigenvalor de $1$, que corresponde al eigenvector que estamos buscando en centralidad de eigenvalor), si el grafo en cuestión es bipartito, la matriz de adyacencia tendrá un eigenvalor de $-1$.

Si la matriz de adyacencia ha sido modificada para reflejar un 'vector de personalización' como en la centralidad de pagerank, es decir, cada columna ha sido multiplicada por el factor de amortiguación $d$ y se le ha sumado $1-d$ veces al vector de personalización, entonces siempre y cuando no haya elementos cero en el vector de personalización, podemos garantizar que el grafo modificado no es bipartito, y (si entendí correctamente) - no tendrá un eigenvalor de $-1$.

Por lo tanto, si podemos imponer que no haya elementos no cero en el vector de personalización, es una condición suficiente para que el método de la potencia converja al calcular la centralidad del eigenvalor.