Re: [igraph] interpretation of hub/auth scores

[Matthew Galati]

Yes. I imagine this might cause numeric instability. But, this is better than getting results that make no sense conceptually. I suggest only doing that if you find that the leading eigenvalue is non-unique (as a backup plan).

On Tue, Dec 3, 2013 at 7:09 AM, Gábor Csárdi <address@hidden> wrote:

A dense matrix is not necessarily a problem. All we need is that the
matrix-matrix product and matrix-vector product operations are easy,
which holds if your matrix is sparse + constant.

However, I don't think this would work in practice. Yes, in theory the
eigenvalue is positive and unique, but in practice, if epsilon is
small, then the top two eigenvalues will be close, causing numerical
instabilities.

(I must admit, I had no time to follow through Tamas's argument, so
fixme. Thanks.)

Gabor

On Tue, Dec 3, 2013 at 6:58 AM, Matthew Galati <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help