girvan_newman ValueError: max() arg is an empty sequence

[gfairchild]

First off, I'm running Python 3.4.3 and NetworkX 2.0.dev20151006145736 (installed earlier today from the latest Git master).

I have a simple graph (download the pickle here) that I'm trying to run girvan_newman on:

communities = nx.girvan_newman(graph)
pprint.pprint(list(communities))

I'm getting the following error:

> ./community_detection.py ../data/en_Influenza_1.pickle 
Traceback (most recent call last):
  File "./community_detection.py", line 32, in <module>
    communities = nx.girvan_newman(args.graph)
  File "[path]/env/lib/python3.4/site-packages/networkx/algorithms/community/centrality.py", line 39, in girvan_newman
    _remove_max_edge(g, weight)
  File "[path]/env/lib/python3.4/site-packages/networkx/algorithms/community/centrality.py", line 61, in _remove_max_edge
    max_value = max(betweenness.values())
ValueError: max() arg is an empty sequence

I'm guessing there's just an edge case in the girvan_newman code that was missed.

[hagberg]

There are definitely some issues with the girvan_newman() algorithm.

1. Your case is triggering a bug where self-loops are not considered - Self loops need to be removed, e.g.

    g = G.copy().to_undirected()
    g.remove_edges_from(g.selfloop_edges())

2. Your original graph has betweenness centralities all equal which triggers a bug where all of the edges are removed in the first pass (one community). The _remove_edge code needs to be something like

    number_components = nx.number_connected_components(G)
    while nx.number_connected_components(G) <= number_components:
        betweenness = nx.edge_betweenness_centrality(G, weight=weight)
        edge = max(betweenness, key=(lambda k:betweenness[k]))
        G.remove_edge(*edge)

3. The tests are hard to understand and possibly not robust to alternate edge orderings that may occur and are still correct.