Re: [igraph] average path length decreases between edge deleted graphs

[Tamás Nepusz]

> 
> graphs are identical except that one graph is a filtered graph, i.e. some 
> edges have been deleted. The graphs are disconnected, undirected and 
> unweighted. When I ask for the average path length I get 1.564 for the 
> original network. For the filtered network I get 1.552. I know that the 
> difference isn't much but I don't understand how the average can go down when 
> I delete edges! How is this possible?
It is because average.path.length considers only the _existing_ paths by 
default; in other words, if a pair of vertices are reachable from each other in 
the original network but not in the filtered network, then the pair is simply 
left out from the average in the filtered case but not in the undirected case. 
If the path that was left out this way had a larger-than-average path length, 
then excluding it will push the average down.

The solution is to specify unconnected=FALSE as an argument to 
average.path.length. When unconnected=FALSE, pairs of vertices with no path 
between them will contribute to the average with a hypothetical path length of 
vcount(g), which is one larger than the maximum possible path length in a graph 
with the same vertex count.

> The only thing I can think of is to look at each of the sub-graphs and find 
> the average path length for those to check. However, I'm not sure how to 
> automatically isolate sub-graphs. How can I do this?
See decompose.graph; this will generate a list of graphs for you, each 
corresponding to one connected component of the original graph.

Best,
Tamas