Repository: networkx/networkx
Pull request: fix greedy_modularity when multiple components exist.
Fixes #5530 

After the community merging iteration stops, we have to check whether the number of communities is still too many for the `best_n` criteria.  If so, merge the biggest 2 components repeatedly to keep modularity as big as we can.




Problem statement:
greedy_modularity_communities raises StopIteration for unconnected (?) graph
<!--- Provide a general summary of the issue in the Title above -->

After an update of `networkx` from 2.6.3 to 2.8, one of my tests suddenly failed with
```
Traceback (most recent call last):
  File "/usr/lib/python3.10/runpy.py", line 196, in _run_module_as_main
    return _run_code(code, main_globals, None,
  File "/usr/lib/python3.10/runpy.py", line 86, in _run_code
    exec(code, run_globals)
  File "/home/gereon/Develop/lexedata/src/lexedata/report/nonconcatenative_morphemes.py", line 159, in <module>
    networkx.algorithms.community.greedy_modularity_communities(graph),
  File "/home/gereon/.local/etc/lexedata/lib/python3.10/site-packages/networkx/algorithms/community/modularity_max.py", line 354, in greedy_modularity_communities
    dq = next(community_gen)
StopIteration

```
It turns out that the internals of `greedy_modularity_communities` have changed, so the function doesn't work any more with unconnected graphs.

### Current Behavior
<!--- Tell us what happens instead of the expected behavior -->

`networkx.algorithms.community.greedy_modularity_communities` fails with undocumented error message for unconnected graphs, or graphs without edges

### Expected Behavior
<!--- Tell us what should happen -->

 - Either document the requirement to have a connected graph with at least one edge and throw `ValueError` instead of `StopIteration` when it is not fulfilled, or run the graph through `nx.connected_components()` first.
 - If the graph has only one node and no edges, return that node.

### Steps to Reproduce
<!--- Provide a minimal example that reproduces the bug -->

```
>>> G = nx.Graph()
>>> G.add_edges_from([(0,1),(2,3)])
>>> greedy_modularity_communities(G)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/gereon/.local/etc/lexedata/lib/python3.10/site-packages/networkx/algorithms/community/modularity_max.py", line 354, in greedy_modularity_communities
    dq = next(community_gen)
StopIteration
```

```
>>> G = nx.Graph()
>>> G.add_nodes_from([1])
>>> greedy_modularity_communities(G)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/gereon/.local/etc/lexedata/lib/python3.10/site-packages/networkx/algorithms/community/modularity_max.py", line 350, in greedy_modularity_communities
    communities = next(community_gen)
  File "/home/gereon/.local/etc/lexedata/lib/python3.10/site-packages/networkx/algorithms/community/modularity_max.py", line 79, in _greedy_modularity_communities_generator
    q0 = 1 / m
ZeroDivisionError: division by zero

```
### Environment
<!--- Please provide details about your local environment -->
Python version: 3.10.2
NetworkX version: 2.8

Hints from issue discussion:
Thanks for the report @Anaphory - you are correct, there indeed has been a behavior changed for unconnected graphs. Your suggestions as to what to do about it seem sensible, though I'm not sure which approach we should take (i.e. document the new behavior or treat this as a regression). I'd like to know what others thing, especially @martacki & @dschult 
I would like us to handle disconnected graphs for the user (and not making them split the graph into connected components first). We have to figure out what the new `cutoff` and `best_n` parameters mean in that case though... Maybe we will have to ensure that `cutoff` is at least the number of connected components. Or maybe we can simply use a try-except on a StopIteration for the `next` call.  We should try to mimic the previous behavior of this function as much as we can. The intent was to leave the results the same for people who don't use the `cutoff` or `best_n` parameters. 

Handling graphs with zero edges is definitely something we should do.  I'm pretty sure that used to fail with the older code too. It's easy to treat that corner case specially and we should do that.

Commit message: fix greedy_modularity when multiple components exist.

After merging iteration stops, have to check whether number
of communities is still too many for the `best_n` criteria.
If so, merge the components with biggest first to keep modularity big.

Patch to review:
diff --git a/networkx/algorithms/community/modularity_max.py b/networkx/algorithms/community/modularity_max.py
index 264a0dc0735..59b095a40bf 100644
--- a/networkx/algorithms/community/modularity_max.py
+++ b/networkx/algorithms/community/modularity_max.py
@@ -326,6 +326,8 @@ def greedy_modularity_communities(
             raise ValueError(f"best_n must be between 1 and {len(G)}. Got {best_n}.")
         if best_n < cutoff:
             raise ValueError(f"Must have best_n >= cutoff. Got {best_n} < {cutoff}")
+        if best_n == 1:
+            return [set(G)]
     else:
         best_n = G.number_of_nodes()
     if n_communities is not None:
@@ -351,7 +353,20 @@ def greedy_modularity_communities(
 
     # continue merging communities until one of the breaking criteria is satisfied
     while len(communities) > cutoff:
-        dq = next(community_gen)
+        try:
+            dq = next(community_gen)
+        # StopIteration occurs when communities are the connected components
+        except StopIteration:
+            communities = sorted(communities, key=len, reverse=True)
+            # continue to merge even though modularity goes down?
+            while len(communities) > best_n:
+                # merge the biggest sets
+                comm1, comm2, *rest = communities
+                communities = [comm1 ^ comm2]
+                communities.extend(rest)
+            return communities
+
+        # keep going unless max_mod is reached or best_n says to merge more
         if dq < 0 and len(communities) <= best_n:
             break
         communities = next(community_gen)
diff --git a/networkx/algorithms/community/tests/test_modularity_max.py b/networkx/algorithms/community/tests/test_modularity_max.py
index 784e4a97b3b..776fd711b32 100644
--- a/networkx/algorithms/community/tests/test_modularity_max.py
+++ b/networkx/algorithms/community/tests/test_modularity_max.py
@@ -44,6 +44,17 @@ def test_modularity_communities_categorical_labels(func):
     assert set(func(G)) == expected
 
 
+def test_greedy_modularity_communities_components():
+    # Test for gh-5530
+    G = nx.Graph([(0, 1), (2, 3), (4, 5), (5, 6)])
+    # usual case with 3 components
+    assert greedy_modularity_communities(G) == [{4, 5, 6}, {0, 1}, {2, 3}]
+    # best_n can make the algorithm continue even when modulatiry goes down
+    assert greedy_modularity_communities(G, best_n=3) == [{4, 5, 6}, {0, 1}, {2, 3}]
+    assert greedy_modularity_communities(G, best_n=2) == [{0, 1, 4, 5, 6}, {2, 3}]
+    assert greedy_modularity_communities(G, best_n=1) == [{0, 1, 2, 3, 4, 5, 6}]
+
+
 def test_greedy_modularity_communities_relabeled():
     # Test for gh-4966
     G = nx.balanced_tree(2, 2)
@@ -306,7 +317,7 @@ def test_cutoff_parameter():
 def test_best_n():
     G = nx.barbell_graph(5, 3)
 
-    # Same result as without enforcing n_communities:
+    # Same result as without enforcing cutoff:
     best_n = 3
     expected = [frozenset(range(5)), frozenset(range(8, 13)), frozenset(range(5, 8))]
     assert greedy_modularity_communities(G, best_n=best_n) == expected


Code review comments:
diff_hunk: @@ -44,6 +44,17 @@ def test_modularity_communities_categorical_labels(func):
     assert set(func(G)) == expected
 
 
+def test_greedy_modularity_communities_components():
+    # Test for gh-5530
+    G = nx.Graph([(0, 1), (2, 3), (4, 5), (5, 6)])
+    # usual case with 3 components
+    assert greedy_modularity_communities(G) == [{4, 5, 6}, {0, 1}, {2, 3}]
+    # best_n can make the algorithm continue even when modulatiry goes down
path: networkx/algorithms/community/tests/test_modularity_max.py
text: @user1:
```suggestion
    # best_n can make the algorithm continue even when modularity goes down
```

diff_hunk: @@ -351,7 +353,20 @@ def greedy_modularity_communities(
 
     # continue merging communities until one of the breaking criteria is satisfied
     while len(communities) > cutoff:
-        dq = next(community_gen)
+        try:
+            dq = next(community_gen)
+        # StopIteration occurs when communities are the connected components
+        except StopIteration:
+            communities = sorted(communities, key=len, reverse=True)
+            # continue to merge even though modularity goes down?
path: networkx/algorithms/community/modularity_max.py
text: @user1:
I have no idea what makes the most sense in this case, so I'd defer to the graph/network experts!

If no one's entirely sure what should happen here, one option could be to simply return the `communities` in the `best_n=None` (default) case and punt when `best_n!=None`, e.g. something like:

```python
# StopIteration occurs when communities are the connected components
except StopIteration:
    if best_n was None:  # Would need a variable to keep track of the original value of `best_n`
        return communities
    else:
        raise <exception-with-better-message-than-stop-iteration>
```
At least that would fix the returning-the-components regression part of the issue without having to necessarily make a decision on what to do with `best_n`.

@author:
Luckily, the only value of `best_n` that would represent an `original_best_n is None` is when `best_n == len(G)`.
And in that case, the following while loop is passed over and we return `communities` just as in your suggestion.

I think the question mark in the comment on this line (361) should be removed -- and made more clear.
Once we include a parameter `best_n` we have to expect that sometimes we will merge communities that decrease the modularity. The parameter indicates to keep merging until we get `best_n` communities.
How about a change for that comment to:
```#  if best_n requires more merging, merge the biggest to keep modularity high```
and then can remove comment 3 lines down.