> 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.
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
