Re: [igraph] interpretation of hub/auth scores

[Gábor Csárdi]

Agreed. This said, adding a small (not epsilon, but rather 0.1 or
something like that) constant to the graph still makes sense, the same
way as it does for PageRank on graphs that are not strongly connected.
But then this would be a parameter, like for PR.

It is the small epsilon, added only if double eigenvalues are
detected, that I am against.

Gabor

On Tue, Dec 3, 2013 at 2:43 PM, Tamás Nepusz <address@hidden> wrote:
>> 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.
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help