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

[Yong Zou]

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
>