Re: [igraph] interpretation of hub/auth scores

[Matthew Galati]

Unfortunately there’s no easy way to detect whether the multiplicity of an eigenvalue is >1 due to numerical inaccuracies. In the case of your graph, it happened to be easy because the multiple eigenvalue was integer, but this is not true in the general case and it is hard to decide whether two eigenvalues are the same (but look different due to inaccuracies) or they are indeed different (but very close to each other).

I would just assume (heuristically) that if the first two eigenvalues are within epsilon (some tolerance, like e-8), then it has multiplicity>1 and you need to do something else. Heuristically, that seems to work for what I have tried.

 

The other thing is that as soon as you have an eigenvalue with multiplicity >1, then the eigenvectors corresponding to this eigenvalue define a subspace within which *any* vector that is a linear combination of the eigenvector basis will also be an eigenvector. Suppose that you have an eigenvalue x and two corresponding eigenvectors: v1 and v2. By definition, it follows that A*v1 = x*v1 and A*v2 = x*v2. But then it also follows that any vector v3 = a*v1 + b*v2 is also an eigenvector since A*v3 = A*(a*v1 + b*v2) = a*A*v1 + b*A*v2 = a*x*v1 + b*x*v2 = x*(a*v1 + b*v2) = x*v3. Therefore, as soon as you have an eigenvalue with multiplicity > 1, you have an *infinite* number of solutions; in other words, an infinite number of possible hub scores. Actually, I noticed that yesterday when I was testing your graph: I temporarily modified igraph’s code to use a random starting vector in the iteration that searches for the eigenvector (instead of the degree vector of the graph), and I noticed that the results were not consistent between runs - this was because the algorithm converged to a different eigenvector in the eigenspace spanned by the two bases.

Yes - understood. So, if we have multiplicity>1, we really need to do something else or the results won't make much sense.

> Making the matrix a 'positive matrix' forces this to be true. I am no linear algebra expert - so I might be doing some hand-waving here.

Actually, it is enough for the matrix to be a “primitive matrix”, which means that there exists some integer k for which A^k (A to the power of k) contains positive numbers only. Since the intersection of row i and column j in A^k simply counts the number of shortest paths from i to j, it basically means that your graph has to be strongly connected; in other words, you must be able to get from any point to any other point in a finite number of steps. This would ensure the uniqueness of the hub scores.

Yes - but you will hardly ever have a strongly connected graph. This was is not. 

The point of hub/auth is to produce a ranking - so adding some small constant should fix the multiplicity, give a valid ranking, and hopefully not cause any other numeric issues. It would need some experimentation to test this.