Re: [igraph] betweenness centrality -- negative and floating values?

[Tamas Nepusz]

Hi Yong,

Did you compile igraph from source? If not, what operating system are
you using and how did you install igraph (i.e., via a package manager or
by downloading it directly from our homepage)? If you compiled igraph
from source, here are the changes you have to make (red lines are the
ones that were removed, the green ones were added):

http://bazaar.launchpad.net/~igraph/igraph/0.5-main/revision/151a

-- 
Tamas
0
On Thu, Jun 11, 2009 at 02:00:50PM +0200, Yong Zou wrote:
> Thanks a lot Tamas,
> 
> Can you please send me the updated source code? Probably I also need
> to know how to work with your source code and the one of igraph i
> already have.
> 
> Many thanks,
> Yong
> 
> On Thu, Jun 11, 2009 at 1:34 PM, Tamas Nepusz<address@hidden> wrote:
> > Hi Yong,
> >
> > I can confirm that it's a "simple" overflow problem that occurs when
> > igraph counts the number of geodesics from a given vertex to another
> > one. Is your graph special in some way (i.e., does it follow a regular
> > grid structure for instance)?
> >
> > The bug can easily be worked around by changing the storage type of the
> > nrgeo variable in centrality.c to unsigned long long int instead of a
> > simple long int. This results in a minimum betweenness of zero and a
> > maximum betweenness of 2461107.447955 for me, but I guess a better
> > solution is needed, as even the limits of a long long int are too
> > restrictive when you consider a regular 2D lattice of size k*k (since
> > the number of geodesics from the top left to the bottom right corner is
> > (2k!) / (k! k!)). If k is large enough, this can overflow easily.
> >
> > Anyway, I guess the above quick fix should work for you. Are you able to
> > modify the source code or shall I give you the updated source code? You
> > have to replace "long int" by "unsigned long long int" in 6 places in
> > total, three in igraph_betweenness_estimate and three in
> > igraph_edge_betweenness_estimate (this might not be necessary, but
> > better safe than sorry).
> >
> > --
> > Tamas
> >
> > On Thu, Jun 11, 2009 at 10:03:38AM +0200, Yong Zou wrote:
> >> Good morning Tamas,
> >>
> >> I wouldn't think it is because of the platforms or gcc. It is because
> >> of whether it is 32bits or 64 bits.
> >>
> >> We have made the following test: (For the network I sent to you.)
> >> -- previously: 32 bits machine, openSuSE 10.3,
> >> Maximum betweenness is   376506206757352.750000, vertex 5411
> >> Minimum betweenness is   -55004389285247.281250, vertex 125
> >>
> >> -- now, the results on 64 bits system:
> >> Maximum betweenness is   3616914.907793, vertex 1785
> >> Minimum betweenness is   -25946.467790, vertex 4156
> >>
> >> The maximum BC from the new test sounds reasonable.
> >>
> >> The problem remains:
> >> Negative BC values.
> >>
> >> Best,
> >> Yong
> >>
> >> On Thu, Jun 11, 2009 at 1:52 AM, Tamas Nepusz<address@hidden> wrote:
> >> > Hi Yong,
> >> >
> >> > I tested your graph and it looks like the issue is platform-dependent; 
> >> > e.g.,
> >> > it doesn't happen in openSuSE 11.1 (gcc 4.3.2, igraph 0.5.2), but I can
> >> > reproduce it with OS X (gcc 4.0.1, igraph 0.5.2 and igraph 0.6). I 
> >> > suspect
> >> > some kind of an internal overflow problem, but it takes more time to 
> >> > track
> >> > down the bug than I expected. I filed a bug report on Launchpad; if you 
> >> > want
> >> > to get notified when there's some progress, subscribe to the bug report
> >> > here:
> >> >
> >> > https://bugs.launchpad.net/igraph/+bug/385747
> >> >
> >> > --
> >> > Tamas
> >

pgpuVeT7xCFwp.pgp
Description: PGP signature