headers
Rui Carvalho | 1 Sep 2008 13:05
Picon
Favicon

Betweenness centrality with parallel edges

Hi,

 

I remember asking some time ago whether graph-tool computed BC with parallel edges and Tiago pointing me to the BGL interface.

 

The answer is the BGL does take in account parallel edges in the computation of the number of shortest paths. However, the normalization factor in graph-tool becomes meaningless when networks have parallel edges as the star is no longer the benchmark network.

 

Tiago, would it be possible to include a flag in graph-tool so we can choose to compute normalized/non-normalized betweeness?

 

Many thanks,

Rui

 

_______________________________________________
graph-tool mailing list
graph-tool <at> forked.de
http://lists.forked.de/mailman/listinfo/graph-tool
Permalink | Reply | 3 comments |
headers
Tiago de Paula Peixoto | 2 Sep 2008 15:04
Picon
Gravatar

Re: Betweenness centrality with parallel edges

Hello Rui,

On 09/01/2008 01:05 PM, Rui Carvalho wrote:
> Tiago, would it be possible to include a flag in graph-tool so we can
> choose to compute normalized/non-normalized betweeness?

I don't object at all to this. I'm incredibly busy at the moment, but
I'll see around to implementing this as soon as I can.

Best regards,
Tiago

--

-- 
Tiago de Paula Peixoto <tiago <at> forked.de>


_______________________________________________
graph-tool mailing list
graph-tool <at> forked.de
http://lists.forked.de/mailman/listinfo/graph-tool
Permalink | Reply | 2 comments |
headers
Rui Carvalho | 4 Sep 2008 12:57
Picon
Favicon

Re: Betweenness centrality with parallel edges

Hi Tiago,

Thanks for considering it. 

Until you implement it, my understanding is that to get absolute betweenness values we need to multiply
node/edge betweenness by the following factors:
Node betweenness: (N-1)*(N-2)/2
Edge betweenness: N*(N-1)/2

Is this correct?

Cheers,
Rui

P.S.: good luck with the post-doc work ;)

-----Original Message-----
From: graph-tool-bounces <at> forked.de [mailto:graph-tool-bounces <at> forked.de] On Behalf Of Tiago de
Paula Peixoto
Sent: 02 September 2008 14:04
To: Main discussion list for the graph-tool project
Subject: Re: [graph-tool] Betweenness centrality with parallel edges

Hello Rui,

On 09/01/2008 01:05 PM, Rui Carvalho wrote:
> Tiago, would it be possible to include a flag in graph-tool so we can 
> choose to compute normalized/non-normalized betweeness?

I don't object at all to this. I'm incredibly busy at the moment, but I'll see around to implementing this as
soon as I can.

Best regards,
Tiago

--
Tiago de Paula Peixoto <tiago <at> forked.de>
Permalink | Reply | 1 comment |
headers
Tiago de Paula Peixoto | 4 Sep 2008 13:09
Picon
Gravatar

Re: Betweenness centrality with parallel edges

Hi Rui,

On 09/04/2008 12:57 PM, Rui Carvalho wrote:
> Until you implement it, my understanding is that to get absolute
> betweenness values we need to multiply node/edge betweenness by the
> following factors:
> Node betweenness: (N-1)*(N-2)/2
> Edge betweenness: N*(N-1)/2
> 
> Is this correct?

Yes, this is correct for undirected graphs. For directed graphs it
becomes (n-2)*(n-1) and n*(n-1), for vertex and edge betweenness
respectively.

> P.S.: good luck with the post-doc work ;)

Thanks. ;-)

Cheers,
Tiago

--

-- 
Tiago de Paula Peixoto <tiago <at> forked.de>


_______________________________________________
graph-tool mailing list
graph-tool <at> forked.de
http://lists.forked.de/mailman/listinfo/graph-tool
Permalink | Reply | 0 comments |

Gmane