Re: [igraph] interpretation of hub/auth scores

[Matthew Galati]

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 <address@hidden> 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 <address@hidden> 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 <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
>
>
>
> _______________________________________________
> 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