igraph-help
[Top][All Lists]

## Re: [igraph] interpretation of hub/auth scores

 From: Tamás Nepusz Subject: Re: [igraph] interpretation of hub/auth scores Date: Tue, 3 Dec 2013 20:43:52 +0100

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

```

reply via email to