Re: [igraph] interpretation of hub/auth scores

[Tamás Nepusz]

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
> > address@hidden (mailto:address@hidden)
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>