Re: [igraph] interpretation of hub/auth scores

[Matthew Galati]

Yes. I have even reading up on this topic. I think the hub/auth scores assume a 
unique dominant eigenvalue - which is not true on this case (and many others I 
have seen). I am trying to see if anything can be done. I think that, by adding 
epsilon to all matrix coefficients, this will ensure that the eigenvalue is 
unique. This idea does lead to sensible results in the cases I have looked at. 
It forces the matrix to be positive, which implies a unique dominant 
eigenvalue. Unfortunately, this makes A fully dense - so, I am hoping there is 
a better way. 

Sent from my iPhone

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