igraph-help
[Top][All Lists]

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

 From: Tamas Nepusz Subject: Re: [igraph] betweenness centrality -- negative and floating values? Date: Wed, 10 Jun 2009 11:50:20 +0100 User-agent: Mutt/1.5.17 (2007-11-01)

Hi Yong,

I'm 99.9% convinced that such large values cannot be right. Even the
maximal betweenness centrality in a line graph of 10000 nodes is only
24995000 (i.e., 4999*5000). Can you send me the source code and the
graph you are working with (or any other graph that produces erroneously
high betweenness values)?

--
Tamas

On Wed, Jun 10, 2009 at 12:43:19PM +0200, Yong Zou wrote:
> Hi Tamas,
>
> the betweenness centrality?
> 58743768046350440071168.000000 for a network of 10000 nodes.
>
> Thank you very much.
> Yong
>
> On Thu, May 28, 2009 at 1:38 PM, Yong Zou<address@hidden> wrote:
> > Thanks Tamas,
> >
> > Now it is clear for those floating values. But what about the very big
> > or even negative values, then?
> >
> > Best,
> > Yong
> >
> > On Thu, May 28, 2009 at 1:33 PM, Tamas Nepusz <address@hidden> wrote:
> >>> Ok, I can understand the floating values for the BC then because of
> >>> this weight of 1/k. It also means that the more shortest paths between
> >>> A and B, the less weight will be counted.
> >>>
> >>> However from the original definition for BC,
> >>> http://en.wikipedia.org/wiki/Centrality, this sounds to be different
> >>> for me.
> >>
> >> No, it isn't. The formula on that Wikipedia page has the number of shortest
> >> paths between s and t in the denumerator, so if there is more than a single
> >> shortest path between s and t, the vertices participating in those paths
> >> will receive a contribution of 1/k due to this path, where k is
> >> \sigma_{s,t}
> >> - the number of shortest paths between s and t.
> >>
> >>> I'm quite confused by this now. The values should be
> >>> normalized to the interval [0 1]?
> >>
> >> It can be normalized if you wish, but igraph doesn't do that by default. As
> >> it says on the Wikipedia page you mentioned, "This may be normalised by
> >> dividing through the number of pairs of vertices not including v, which is
> >> (n - 1)(n - 2) / 2.". So if you want to get values between 0 and 1, divide
> >> the betweenness centrality values by (n-1)(n-2)/2.
> >>
> >> --
> >> Tamas
> >>
> >> _______________________________________________
> >> igraph-help mailing list
> >> http://lists.nongnu.org/mailman/listinfo/igraph-help
> >>
> >
>
>
> _______________________________________________
> igraph-help mailing list