Yes - the eigenvalues are close when adding epsilon, but you do now have a strictly dominant one. And, the resulting eigenvectors seem to make sense in the hub/auth context. I didn't find anything about this in the literature - except for the assumption that a unique dominant eigenvalue exists - which, obviously is not true in many cases. Making the matrix a 'positive matrix' forces this to be true. I am no linear algebra expert - so I might be doing some hand-waving here.
On Tue, Dec 3, 2013 at 9:29 AM, Gábor Csárdi <[email protected]> wrote: > In your experiments aren't the new eigenvalues close to the old double > eigenvalue? I would think that the spectrum is a continuous function > of epsilon, and probably the new eigenvalue is close the old double > one. Maybe the eigenvectors are close, too. > > To me it would probably make more sense to report that the results are > ill-defined, and just return them. > > We can also try searching for literature about this, or ask Jon > Kleinberg what he thinks. > > G. > > On Tue, Dec 3, 2013 at 9:20 AM, Matthew Galati <[email protected]> > wrote: > > 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 > > > > _______________________________________________ > 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
