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 00:39:34 +0100

```Hi Matthew,

So, the whole story is as follows. igraph uses ARPACK to find the dominant
eigenvalue of the A*A’ and A’*A matrices (where A is the adjacency matrix) and
the corresponding eigenvectors in order to obtain the hub and authority scores.
This works fine in most cases - however, in your case, igraph fails because the
dominant eigenvalue (4 in your case) has two corresponding eigenvectors, one of
which is the one you see and the other is the one you would expect intuitively.
For what it’s worth, here are the two eigenvectors (normalized conveniently):

v1 = [1 0 0 0 0 0 0]
v2 = [0 2 1 0 1 0 0]

It is easy to confirm that both are valid eigenvectors, and it is also easy to
confirm that both satisfy the HITS equations. Suppose you start out from v1 as
the hub scores. The authority score of each vertex is then the sum of the hub
scores of its predecessors, so we get:

w1 = [0 1 1 0 1 1 0]

since nodes 2, 3, 5 and 6 are successors of node 1 and node 1 is the only node
with a nonzero hub score. Now, let us calculate the hub scores again from the
authority scores we have obtained above. In order to do that, we have to take
the sum of the authority scores of the successors for each node. The result is:

v1’ = [4 0 0 0 0 0 0]

This is indeed 4 times v1, so v1 is an eigenvector of A*A’ with a corresponding
eigenvalue of 4. In other words, igraph is not “wrong”, it is just that your
graph has a structure for which the hub and authority scores are not
well-defined.

--
T.

On Monday, 2 December 2013 at 23:15, Tamás Nepusz wrote:

> Hi Matthew,
>
> Yes, that’s odd indeed. Let me double-check our code; I suspect an ARPACK
> convergence problem here but I’m not sure (and I don’t know why there’s no
> warning if ARPACK indeed fails to converge).
>
> --
> T.
>
>
> On Monday, 2 December 2013 at 21:30, Matthew Galati wrote:
>
> > I am considering this small directed graph.
> >
> > The results score node 1 as the dominate hub and the rest of the nodes with
> > value 0 (i.e., no' hubness'). This seems odd to me. For example, node 2,
> > has outlinks to 3 different nodes (1,4, and 7). So, I would expect it to
> > have some relative level of hubness.
> >
> > > g <- graph.empty()
> > > g <- g+vertices(1,2,3,4,5,6,7)
> > > g <- g+edge("1","2")
> > > g <- g+edge("1","3")
> > > g <- g+edge("1","5")
> > > g <- g+edge("1","6")
> > > g <- g+edge("2","1")
> > > g <- g+edge("2","4")
> > > g <- g+edge("3","1")
> > > g <- g+edge("5","1")
> > > g <- g+edge("2","7")
> > > E(g)
> >
> >
> >
> > Edge sequence:
> >
> > [1] 1 -> 2
> > [2] 1 -> 3
> > [3] 1 -> 5
> > [4] 1 -> 6
> > [5] 2 -> 1
> > [6] 2 -> 4
> > [7] 3 -> 1
> > [8] 5 -> 1
> > [9] 2 -> 7
> >
> > > hub.score(g,scale=FALSE)\$vector
> >
> >
> > 1 2 3 4 5 6 7
> > 0.5733822 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000
> >
> >
> > _______________________________________________
> > igraph-help mailing list