Re: [igraph] average path length for graphs containing multiple components

[Giovanni Marco Dall'Olio]

Hi, I solved this by myself..
This is the code for calculating the average path length in python:
- https://gist.github.com/4124710

Feel free to use it and modify it. I'll see if I can post a version for calculating the weighted average path length, or other similar centralities.

On Tue, Nov 20, 2012 at 11:04 PM, Giovanni Marco Dall'Olio <address@hidden> wrote:

Hello,
how is the average path length calculated for graphs that contain more than one component?
I am using the python igraph library.

I am trying to write a function to calculate the weighted average path length of a graph, and in order to do so, I need to reimplement the average_path_length function in python.
I made many trials, and also wrote some test cases where I calculated the average path length manually:
- https://gist.github.com/4121433
However, my tests fail when there is more than one connected component, so there it should be something that I am missing. I do not understand how the average path length is calculated when there are multiple components. It is not the average of the average path lengths of each component, nor their sum.

Let's say we have the following graph, using the igraph python library:

g = igraph.Graph()
g.add_vertices(20)
g.add_edges([(1, 4), (3, 7), (6, 10), (5, 11), (8, 11), (6, 12), (11, 12)])

The average path length for this graph, according to igraph, is:
print g.average_path_length
2.0

However, if I calculate the average_path_length of the single components, I get the following:

for component_nodes in g.components():
    subgraph = g.subgraph(component_nodes)
    print subgraph.average_path_length()
   ....:    
nan
1.0
nan
1.0
2.13333333333
nan
nan
nan
nan
nan
nan
nan
nan

How do 1.0, 1.0 and 2.13 combine to get an average_path_length of 2.0?

Thank you very much for your help,
Giovanni


--
Giovanni Dall'Olio, phd student
IBE, Institut de Biologia Evolutiva, CEXS-UPF (Barcelona, Spain)

My blog on bioinformatics: http://bioinfoblog.it

--
Giovanni Dall'Olio, phd student
IBE, Institut de Biologia Evolutiva, CEXS-UPF (Barcelona, Spain)

My blog on bioinformatics: http://bioinfoblog.it