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

[Tamas Nepusz]

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

pgpufjFeiZQdF.pgp
Description: PGP signature