
From:  Matthew Galati 
Subject:  Re: [igraph] interpretation of hub/auth scores 
Date:  Tue, 3 Dec 2013 15:25:57 0500 
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).
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.
> Making the matrix a 'positive matrix' forces this to be true. I am no linear algebra expert  so I might be doing some handwaving 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.
[Prev in Thread]  Current Thread  [Next in Thread] 