NetworkXError: Graph is not connected. average_shortest_path_length

[Jean Christophe Ketzinger]

I beg your pardon, but I'm asking myself why there is this error limitation. Is it impossible to ask for the average shortest path in an unconnected graph?
Here is my solution to solve this issue, hope it gonna help and give idea to make this function evolve! Thanks for this wonderful library!

def average_shortest_path_length_for_all(G):
    tempgraph=G.copy();
    if nx.is_connected(tempgraph):
        # Normal case, the graph is connected
        average=nx.average_shortest_path_length(tempgraph);
    else:
        # Try to see if the graph is not connected because of isolated nodes
        tempgraph.remove_nodes_from(nx.isolates(tempgraph));
        if nx.is_connected(tempgraph):
            # Compute the graph average path without isolated nodes
            average=nx.average_shortest_path_length(tempgraph);
        else:
            # Compute the average shortest path for each subgraph and mean it!
            subgraphs = nx.connected_component_subgraphs(tempgraph)
            average=0;
            for sb in subgraphs:
                pprint.pprint(sb.degree());
                average+=nx.average_shortest_path_length(sb);
            average/=(len(subgraphs)*1.0)
return average;

[Helmet Karim]

I recently ran into this issue as well. I think that a weighted average would be more appropriate. So, as a slight modification to your code, after the second "else" (i.e. after checking for isolated nodes) I would add:

        else:

            # calculate the path of each of the subgraphs (or connected component) and store them in path_temp

            path_temp = []

            for g in nx.connected_component_subgraphs(G):

                path_temp.append(nx.average_shortest_path_length(g,weight = 'weight'))

            

            # create a variable weight that holds the size of each subgraph (or connected component)

            # alternatively I have weighted by graph size but we could use anything to weight the average

            weights = []

            for components in range(numpy.size(nx.connected_components(G))):

                weights.append(numpy.size(nx.connected_components(G)[components]))

            

            # compute the weighted average

            average = numpy.average(path_temp,weights = weights) 

It only came up as a thought because I had an issue where one component was large and the other contained 2 nodes. Thus, the average was very biased to a very small component. 

[Daπid]

On 24 June 2013 11:21, Jean Christophe Ketzinger <jc.ket...@gmail.com> wrote:

I beg your pardon, but I'm asking myself why there is this error limitation. Is it impossible to ask for the average shortest path in an unconnected graph?

This is ill-defined, as the shortest path between two nodes in different components will be infinity. If could make sense for certain applications, though, but I think it would be too specific.

Some comments on your code:

def average_shortest_path_length_for_all(G):
    tempgraph=G.copy();

You are not modifying the graph, so the copy is unnecessary. Also, in Python you are not supposed to end the lines with ;.

 

    if nx.is_connected(tempgraph):

There is no need to check. Better apologise than ask for permission. Call average_shortest_path_length inside a try... except, and if it is indeed connected, it will work.
 

        # Normal case, the graph is connected
        average=nx.average_shortest_path_length(tempgraph);

You don't need to save it on a variable, you can just return it.

    else:
        # Try to see if the graph is not connected because of isolated nodes
        tempgraph.remove_nodes_from(nx.isolates(tempgraph));

This can be avoided, for each subgraph check that it has more than 1 node.

 

        if nx.is_connected(tempgraph):
            # Compute the graph average path without isolated nodes
            average=nx.average_shortest_path_length(tempgraph);

Again, you don't need to store it. You got the value, return inmediately.
 

        else:
            # Compute the average shortest path for each subgraph and mean it!
            subgraphs = nx.connected_component_subgraphs(tempgraph)
            average=0;
            for sb in subgraphs:
                pprint.pprint(sb.degree());

You probably left this for debugging.

 

                average+=nx.average_shortest_path_length(sb);
            average/=(len(subgraphs)*1.0)

If the number of graphs is very big, you will get bitten by numerical errors. I would do:

subgraphs = [sbg for sbg in nx.connected_component_subgraphs(G) if if len(sbg) > 1]

return  math.fsum(nx.average_shortest_path_length(sg) for sg in subgraphs) / len(subgraphs)

Or, if you want to weight by the size:

subgraphs = [sbg for sbg in nx.connected_component_subgraphs(G) if if len(sbg) > 1]

return  math.fsum(len(sg) * nx.average_shortest_path_length(sg) for sg in subgraphs) / sum(len(sg) for sg in subgraphs)

return average;

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at http://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/groups/opt_out.