eigenvector_centrality does not converge for 'periodic' graphs

[ghost]

The way eigenvector_centrality is implemented, it cannot work for some 'periodic' graphs because of the way power iteration works. (By periodicity, I mean the same definition than a periodicity of a Markov Chain cf https://en.wikipedia.org/wiki/Markov_chain paragraph 4.2).

For example, it will not work for nx.path_graph(n) where n is an odd number. For example, the eigenvector in the main loop the the graph nx.path_graph(3) oscillates between these two values:

['0 0.333', '1 0.333', '2 0.333']
['0 0.408', '1 0.816', '2 0.408']
['0 0.577', '1 0.577', '2 0.577']
['0 0.408', '1 0.816', '2 0.408']
['0 0.577', '1 0.577', '2 0.577']
['0 0.408', '1 0.816', '2 0.408']
['0 0.577', '1 0.577', '2 0.577']
etc...

This convergence issue is linked to the power iteration method and to the fact that the graph is periodic. One easy way to solve this issue is to make the graph aperiodic by adding to the adjacency matrix a non-null diagonal when doing the power iteration method.

For example, we could insert in line https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality/eigenvector.py#L119 the following (outside of the second loop):

x[n] += xlast[n]

This cheap trick works in my case.

[hagberg]

You are right. The power method the way we have implemented it won't converge for adjacency matrices with a pair of extremal eigenvalues with opposite signs. The odd-node path graphs have that property. Maybe the solution is to use power iteration on A^2? @dschult?

[ghost]

As I said, doing the power iteration on A + delta_I where I is the identity matrix works well. It does not change the eigenvector to add delta_I to A. I'm using it on my own code and so far it seems to behave nicely.

[hagberg]

Yes, that is the "shifted power method". I think it won't work in general for this case unless you know what shift to use.

[dschult]

As you know, the power iteration method will not work for general networks/matrices. In cases where degenerate eigenvalues are dominant, convergence is not guaranteed. In the example here (odd order path graphs) a negative eigenvalue has the same magnitude as the largest positive eigenvalue.

Using A^2 creates a 2-D space of eigenvectors with largest eigenvalues: any linear combination of the dominant eigenvectors of A. Not all of them are eigenvectors of A however. Only the original eigenvectors of A work. All the non-trivial linear combinations of them are eigenvectors of A^2 but not of A. For example, if A_v1 = v1 and A_v2 = -v2, then A^2_(v1+v2) = (v1+v2). So (v1+v2) is an eigenvector of A^2. But A_(v1+v2) = v1 - v2. I cannot find this written up anywhere, but it is true: while eigenvectors of A must be eigenvectors of A^2, eigenvectors of A^2 do not need to be eigenvectors of A.

Luckily, Perron-Frobenius comes to the rescue (as it often seems to). So long as G is strongly connected (connected for an undirected network) the adjacency matrix is non-negative and irreducible. Thus the dominant eigenvalues include a positive real value r with one dimensional eigenspace represented by a non-negative eigenvector. Also, all other dominant eigenvalues are evenly spread about the circle in the complex plane centered at zero with radius r. So the entire spectrum of A lies on or in that circle, and the eigenvalue we care about is on the positive real axis.

If we shift the spectrum to the right by considering the matrix (A+I), we obtain a single dominant eigenvalue r+1 with the same eigenvector that corresponds to the eigenvalue r of A. So, to find the eigenvector centrality using the power method we should multiply by A+I. (Adding other multiples of the identity to A will also work, but A+I is cheap to implement and sufficient for strongly connected networks.)
I can't find this written anywhere, so maybe it should be. If anyone has seen this please let me know.

This change expands the usefulness of our simple power iteration method from strongly connected networks with non-degenerate adj matrices to all strongly connected networks. I'll put together a PR to implement it. Thanks @Tantto for suggesting it and @hagberg for nugding me into what turned out to be a productive rabbit hole. :}

[hagberg]

Great. It seems that as long as we shift the eigenvalues to the right (A + alpha I, where alpha>0) this should be safe and will compute the eigenvalue/eigenvector pair we want.

[jfinkels]

FYI this discussion also appears in issue #261.