Re: [igraph] interpretation of hub/auth scores

[Tamás Nepusz]

> Yes - the eigenvalues are close when adding epsilon, but you do now have a 
> strictly dominant one.

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).

That’s one thing.

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 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.

T.