|
From: | Matthew Walker |
Subject: | Re: [igraph] Eigenvector centrality |
Date: | Wed, 04 Nov 2009 09:20:59 -0500 |
User-agent: | Thunderbird 2.0.0.23 (X11/20090812) |
Hi Tamas, Gábor, Thank you both for your quick replies. I changed both instances of "options->start=1" to "options->start=0" inside igraph_eigenvector_centrality() and recompiled the library. The effect was indeed that iGraph now produces the correct answer (scaled). Thank you for that help. I would be very interested in how to deal with this in the future. I guess one option is to do the calculation twice, once with a degree-based starting-point and once with a random starting-point and to give a warning if the results are inconsistent. But I am sure you will find a far more efficient solution! Thanks again, Matthew Gábor Csárdi wrote: On Wed, Nov 4, 2009 at 10:58 AM, Tamas Nepusz <address@hidden> wrote:Hi Matthew,I am trying to understand eigenvector centrality, but I'm clearly doing something wrong!No, it seems you are doing everything right and the problem is within the eigenvector centrality calculation. The calculation calls ARPACK behind the scenes to do the hard job, and for some cases (like yours -- in fact, this is the only one we are aware of) it converges to the _second_ largest eigenvalue, not the first one. I tweaked the code yesterday a little bit, and it looks like if I set a random starting vector for ARPACK instead of the present solution (which uses the degree vector as the starting vector), the problem is solved. If you are willing to mess around with the igraph source code, this is the single line you have to change in igraph_eigenvector_undirected in centrality.c: options->start=0; /* random start vector */ Originally it was: options->start=1; /* no random start vector */ I will investigate the issue more in detail and try to come up with a permanent solution soon.The problem is, that if you start with a random vector, then the solver is very unstable for (very) sparse graphs. At least this was my experience, that is why I always call ARPACK with a non-random starting vector. Gabor-- Tamas[...] |
[Prev in Thread] | Current Thread | [Next in Thread] |