4

Say I have a (directed) graph $G$ with an adjacency matrix $A$.
For the sake of the question, let's assume it's normalized column-wise (edge weights are normalized so the sum of out-edge weights per node is equal to 1).
I'd like to calculate the eigenvalue centrality of its nodes using the power method, but I know that it might not converge in some cases (which, if I understand correctly, occurs if and only if it has an eigenvalue of -1).

My question is: Generally, what are the conditions on the graph to avoid this case?
Specifically, if I use page-rank centrality (with damping factor < 1), can I be certain to avoid this case (For every choice of personalization vector?)

[Edited: It appears I can be even more specific: If there is an edge with non-zero weight from each node to each node, can I be sure not have an eigenvalue of -1?]

Itamar Mushkin
  • 672
  • 3
  • 19
  • P.S. I know it looks like I'm asking two questions here, but I'd accept an answer to either of the two; I'll manage going from the general case to my specific case. – Itamar Mushkin Jul 26 '20 at 06:33

1 Answers1

0

Here's what I've got so far:

In a bi-partite graph, every eigenvalue $\lambda$ has a corresponding eigenvalue $-\lambda$ (see for example this answer in math.stackexchange, though it doesn't say if only a bi-partite graph has this attribute).
So, for an adjacency matrix whose columns sum to $1$ (which has an eigenvalue of $1$, which corresponds to the eigenvector we're looking for in eigenvalue centrality), if the graph in discussion is bipartite, the adjacency matrix will have an eigenvalue of $-1$.

If the adjacency matrix has been modified to reflect a 'personalization vector' as in pagerank centrality, i.e. every column has been multiplied by the damping factor $d$ and added $1-d$ times the personalization vector, then as long as there's no zero elements in the personalization vector, we can be guaranteed the the modified graph is not bi-partite, and (if I followed correctly) - will not have a $-1$ eigenvalue.

So, if we can impose that there are no non-zero elements in the personalization vector, it is a sufficient condition so that the power method will converge when calculating the eigenvalue centrality.

Itamar Mushkin
  • 672
  • 3
  • 19