Re: [igraph] Selecting vertices for centrality analysis in R

[Jorge Gil]

Hi Gabor,

Thanks for the tips. Indeed using shortest.paths and get.all.shortest.paths I should be able to do "by hand" the analyses to get closeness and betweenness for a set of target vertices.

Regarding the betweenness estimate in NetworkX, the value is obtained as you describe. It selects a given number k of vertices n, and calculates all shortest paths from k to n. See http://tinyurl.com/9pc4a67

The R2 I got was "only" .997 for 10% of the vertices, still surprising. This must be very influenced by the type of network, and might be much worse in some cases. In my case I'm using road networks and it seems to give a very good result taking only 10% of the time to calculate.

Best regards,
Jorge

On 18/12/2012 19:24, Gábor Csárdi wrote:

On Tue, Dec 18, 2012 at 7:47 AM, Jorge Gil <address@hidden> wrote:

[...]

But maybe providing a set of vertices for origin - destination pairs, to calculate only the routes between those, would be very useful. This could cut time dramatically.

You can relatively easily do this "by hand", i.e. using get.all.shortest.paths(). But I see the point, so feel free to submit a bug report for this at https://bugs.launchpad.net/igraph. Thanks.

 

In the networkX pacakge for python there's a version of betweenness centrality where we can set a random percentage of vertices to use. I did some tests and in my networks using 10% of the routes the result has a .999 R2 to the full calculation. The final values are different, but the ranking of nodes is exactly the same.

.999 is a bit surprising. Btw. what exactly is 10% of the routes? You select 10% of the vertices and then calculate shortest paths from these to all vertices?

 

Adding the selection of target vertices to the closeness or degree functions would also be useful, allowing to qualify centrality results with regards to specific sub-groups.

Please add a bug report for these as well, at https://bugs.launchpad.net/igraph, if you really want to have them in igraph. Thanks!

G.

 

[...]

-- 
Jorge Gil
PhD Candidate

TU Delft / Faculty of Architecture
Department of Urbanism
Chair of Spatial Planning and Strategy

Julianalaan 134
2628 BL Delft
P.O. Box 5043
2600 GA Delft
The Netherlands

www.tudelft.nl