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 <[email protected]> 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 <[email protected]> > 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 <[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 > > _______________________________________________ > 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
