[igraph] average path length for graphs containing multiple components
From:
Giovanni Marco Dall'Olio
Subject:
[igraph] average path length for graphs containing multiple components
Date:
Tue, 20 Nov 2012 23:04:39 +0100
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:
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)