[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] interpretation of hub/auth scores
From: |
Matthew Galati |
Subject: |
Re: [igraph] interpretation of hub/auth scores |
Date: |
Tue, 3 Dec 2013 06:58:08 -0500 |
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] interpretation of hub/auth scores, Matthew Galati, 2013/12/02
- Re: [igraph] interpretation of hub/auth scores, Tamás Nepusz, 2013/12/02
- Re: [igraph] interpretation of hub/auth scores, Tamás Nepusz, 2013/12/02
- Re: [igraph] interpretation of hub/auth scores,
Matthew Galati <=
- Re: [igraph] interpretation of hub/auth scores, Gábor Csárdi, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Matthew Galati, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Gábor Csárdi, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Matthew Galati, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Tamás Nepusz, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Gábor Csárdi, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Matthew Galati, 2013/12/03
- Re: [igraph] interpretation of hub/auth scores, Matthew Galati, 2013/12/03