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

[Yong Zou]

Hi Tamas,

I downloaded the C_library directly from your homepage. Afterwards,
from the installation documentary:
$ ./configure
$ make
$ make install

By the way, I can't see the content of the webpage you referred to.

Best,
Y.

On Thu, Jun 11, 2009 at 2:08 PM, Tamas Nepusz<address@hidden> wrote:
> 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
>> >
>