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 <[email protected]> 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 >>> [email protected] (mailto:[email protected]) >>> https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > > _______________________________________________ > igraph-help mailing list > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
