Repository: networkx/networkx

Issue:
Intermittent test failures for test_directed_edge_swap
It looks like CI is occasionally tripping up on the tests added in #6426 due to going over the maximum number of attempted swaps. It should be investigated whether these tests can incorporate a seed to remove this variability (and double check that `double_edge_swap` is performing well!)

Discussion:
dschult: Ack -- I now realize that random_tree is deprecated. So we can merge this but we will need to replace it soon.
Not only that, but the proposed replacement doesn't handle random directed trees -- only undirected trees.
So, in the end we need to add something about directed trees to follow up on the revamp of random trees from #6758 

Shall we merge this to fix the bug and then solve the directed random_tree problem as a different issue?

Patch:
diff --git a/doc/reference/algorithms/community.rst b/doc/reference/algorithms/community.rst
index 1d1070997..b031bcb34 100644
--- a/doc/reference/algorithms/community.rst
+++ b/doc/reference/algorithms/community.rst
@@ -14,6 +14,15 @@ Bipartitions
 
    kernighan_lin_bisection
 
+Divisive Communities
+---------------------
+.. automodule:: networkx.algorithms.community.divisive
+.. autosummary::
+   :toctree: generated/
+
+   edge_betweenness_partition
+   edge_current_flow_betweenness_partition
+
 K-Clique
 --------
 .. automodule:: networkx.algorithms.community.kclique
diff --git a/networkx/algorithms/community/__init__.py b/networkx/algorithms/community/__init__.py
index fa782201d..40549aff2 100644
--- a/networkx/algorithms/community/__init__.py
+++ b/networkx/algorithms/community/__init__.py
@@ -14,6 +14,7 @@ functions as attributes of ``community``. For example::
 """
 from networkx.algorithms.community.asyn_fluid import *
 from networkx.algorithms.community.centrality import *
+from networkx.algorithms.community.divisive import *
 from networkx.algorithms.community.kclique import *
 from networkx.algorithms.community.kernighan_lin import *
 from networkx.algorithms.community.label_propagation import *
diff --git a/networkx/algorithms/community/divisive.py b/networkx/algorithms/community/divisive.py
new file mode 100644
index 000000000..7dbf70ca3
--- /dev/null
+++ b/networkx/algorithms/community/divisive.py
@@ -0,0 +1,194 @@
+import functools
+
+import networkx as nx
+
+__all__ = [
+    "edge_betweenness_partition",
+    "edge_current_flow_betweenness_partition",
+]
+
+
+def edge_betweenness_partition(G, number_of_sets, *, weight=None):
+    """Partition created by iteratively removing the highest edge betweenness edge.
+
+    This algorithm works by calculating the edge betweenness for all
+    edges and removing the edge with the highest value. It is then
+    determined whether the graph has been broken into at least
+    `number_of_sets` connected components.
+    If not the process is repeated.
+
+    Parameters
+    ----------
+    G : NetworkX Graph, DiGraph or MultiGraph
+      Graph to be partitioned
+
+    number_of_sets : int
+      Number of sets in the desired partition of the graph
+
+    weight : key, optional, default=None
+      The key to use if using weights for edge betweenness calculation
+
+    Returns
+    -------
+    C : list of sets
+      Partition of the nodes of G
+
+    Raises
+    ------
+    NetworkXError
+      If number_of_sets is <= 0 or if number_of_sets > len(G)
+
+    Examples
+    --------
+    >>> G = nx.karate_club_graph()
+    >>> part = nx.community.edge_betweenness_partition(G, 2)
+    >>> {0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21} in part
+    True
+    >>> {2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33} in part
+    True
+
+    See Also
+    --------
+    edge_current_flow_betweenness_partition
+
+    Notes
+    -----
+    This algorithm is fairly slow, as both the calculation of connected
+    components and edge betweenness relies on all pairs shortest
+    path algorithms. They could potentially be combined to cut down
+    on overall computation time.
+
+    References
+    ----------
+    .. [1] Santo Fortunato 'Community Detection in Graphs' Physical Reports
+       Volume 486, Issue 3-5 p. 75-174
+       http://arxiv.org/abs/0906.0612
+    """
+    if number_of_sets <= 0:
+        raise nx.NetworkXError("number_of_sets must be >0")
+    if number_of_sets == 1:
+        return [set(G)]
+    if number_of_sets == len(G):
+        return [{n} for n in G]
+    if number_of_sets > len(G):
+        raise nx.NetworkXError("number_of_sets must be <= len(G)")
+
+    H = G.copy()
+    partition = list(nx.connected_components(H))
+    while len(partition) < number_of_sets:
+        ranking = nx.edge_betweenness_centrality(H, weight=weight)
+        edge = max(ranking, key=ranking.get)
+        H.remove_edge(*edge)
+        partition = list(nx.connected_components(H))
+    return partition
+
+
+def edge_current_flow_betweenness_partition(G, number_of_sets, *, weight=None):
+    """Partition created by removing the highest edge current flow betweenness edge.
+
+    This algorithm works by calculating the edge current flow
+    betweenness for all edges and removing the edge with the
+    highest value. It is then determined whether the graph has
+    been broken into at least `number_of_sets` connected
+    components. If not the process is repeated.
+
+    Parameters
+    ----------
+    G : NetworkX Graph, DiGraph or MultiGraph
+      Graph to be partitioned
+
+    number_of_sets : int
+      Number of sets in the desired partition of the graph
+
+    weight : key, optional (default=None)
+      The edge attribute key to use as weights for
+      edge current flow betweenness calculations
+
+    Returns
+    -------
+    C : list of sets
+      Partition of G
+
+    Raises
+    ------
+    NetworkXError
+      If number_of_sets is <= 0 or number_of_sets > len(G)
+
+    Examples
+    --------
+    >>> G = nx.karate_club_graph()
+    >>> part = nx.community.edge_current_flow_betweenness_partition(G, 2)
+    >>> {0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21} in part
+    True
+    >>> {8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33} in part
+    True
+
+
+    See Also
+    --------
+    edge_betweenness_partition
+
+    Notes
+    -----
+    This algorithm is extremely slow, as the recalculation of the edge
+    current flow betweenness is extremely slow.
+
+    References
+    ----------
+    .. [1] Santo Fortunato 'Community Detection in Graphs' Physical Reports
+       Volume 486, Issue 3-5 p. 75-174
+       http://arxiv.org/abs/0906.0612
+    """
+    if number_of_sets <= 0:
+        raise nx.NetworkXError("number_of_sets must be >0")
+    elif number_of_sets == 1:
+        return [set(G)]
+    elif number_of_sets == len(G):
+        return [{n} for n in G]
+    elif number_of_sets > len(G):
+        raise nx.NetworkXError("number_of_sets must be <= len(G)")
+
+    rank = functools.partial(
+        nx.edge_current_flow_betweenness_centrality, normalized=False, weight=weight
+    )
+
+    # current flow requires a connected network so we track the components explicitly
+    H = G.copy()
+    partition = list(nx.connected_components(H))
+    if len(partition) > 1:
+        Hcc_subgraphs = [H.subgraph(cc).copy() for cc in partition]
+    else:
+        Hcc_subgraphs = [H]
+
+    ranking = {}
+    for Hcc in Hcc_subgraphs:
+        ranking.update(rank(Hcc))
+
+    while len(partition) < number_of_sets:
+        edge = max(ranking, key=ranking.get)
+        for cc, Hcc in zip(partition, Hcc_subgraphs):
+            if edge[0] in cc:
+                Hcc.remove_edge(*edge)
+                del ranking[edge]
+                splitcc_list = list(nx.connected_components(Hcc))
+                if len(splitcc_list) > 1:
+                    # there are 2 connected components. split off smaller one
+                    cc_new = min(splitcc_list, key=len)
+                    Hcc_new = Hcc.subgraph(cc_new).copy()
+                    # update edge rankings for Hcc_new
+                    newranks = rank(Hcc_new)
+                    for e, r in newranks.items():
+                        ranking[e if e in ranking else e[::-1]] = r
+                    # append new cc and Hcc to their lists.
+                    partition.append(cc_new)
+                    Hcc_subgraphs.append(Hcc_new)
+
+                    # leave existing cc and Hcc in their lists, but shrink them
+                    Hcc.remove_nodes_from(cc_new)
+                    cc.difference_update(cc_new)
+                # update edge rankings for Hcc whether it was split or not
+                newranks = rank(Hcc)
+                for e, r in newranks.items():
+                    ranking[e if e in ranking else e[::-1]] = r
+                break
+    return partition


Test patch:
diff --git a/networkx/algorithms/community/tests/test_divisive.py b/networkx/algorithms/community/tests/test_divisive.py
new file mode 100644
index 000000000..f3857613d
--- /dev/null
+++ b/networkx/algorithms/community/tests/test_divisive.py
@@ -0,0 +1,109 @@
+import pytest
+
+import networkx as nx
+
+
+def test_edge_betweenness_partition():
+    G = nx.barbell_graph(3, 0)
+    C = nx.community.edge_betweenness_partition(G, 2)
+    answer = [{0, 1, 2}, {3, 4, 5}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    G = nx.barbell_graph(3, 1)
+    C = nx.community.edge_betweenness_partition(G, 3)
+    answer = [{0, 1, 2}, {4, 5, 6}, {3}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_betweenness_partition(G, 7)
+    answer = [{n} for n in G]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_betweenness_partition(G, 1)
+    assert C == [set(G)]
+
+    C = nx.community.edge_betweenness_partition(G, 1, weight="weight")
+    assert C == [set(G)]
+
+    with pytest.raises(nx.NetworkXError):
+        nx.community.edge_betweenness_partition(G, 0)
+
+    with pytest.raises(nx.NetworkXError):
+        nx.community.edge_betweenness_partition(G, -1)
+
+    with pytest.raises(nx.NetworkXError):
+        nx.community.edge_betweenness_partition(G, 10)
+
+
+def test_edge_current_flow_betweenness_partition():
+    pytest.importorskip("numpy")
+
+    G = nx.barbell_graph(3, 0)
+    C = nx.community.edge_current_flow_betweenness_partition(G, 2)
+    answer = [{0, 1, 2}, {3, 4, 5}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    G = nx.barbell_graph(3, 1)
+    C = nx.community.edge_current_flow_betweenness_partition(G, 2)
+    answer = [{0, 1, 2, 3}, {4, 5, 6}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 3)
+    answer = [{0, 1, 2}, {4, 5, 6}, {3}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 4)
+    answer = [{1, 2}, {4, 5, 6}, {3}, {0}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 5)
+    answer = [{1, 2}, {5, 6}, {3}, {0}, {4}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 6)
+    answer = [{2}, {5, 6}, {3}, {0}, {4}, {1}]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 7)
+    answer = [{n} for n in G]
+    assert len(C) == len(answer)
+    for s in answer:
+        assert s in C
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 1)
+    assert C == [set(G)]
+
+    C = nx.community.edge_current_flow_betweenness_partition(G, 1, weight="weight")
+    assert C == [set(G)]
+
+    with pytest.raises(nx.NetworkXError):
+        nx.community.edge_current_flow_betweenness_partition(G, 0)
+
+    with pytest.raises(nx.NetworkXError):
+        nx.community.edge_current_flow_betweenness_partition(G, -1)
+
+    with pytest.raises(nx.NetworkXError):
+        nx.community.edge_current_flow_betweenness_partition(G, 10)
+
+    N = 10
+    G = nx.empty_graph(N)
+    for i in range(2, N - 1):
+        C = nx.community.edge_current_flow_betweenness_partition(G, i)
+        assert C == [{n} for n in G]
diff --git a/networkx/algorithms/tests/test_swap.py b/networkx/algorithms/tests/test_swap.py
index 378c8ecfa..c4aeb0682 100644
--- a/networkx/algorithms/tests/test_swap.py
+++ b/networkx/algorithms/tests/test_swap.py
@@ -3,7 +3,7 @@ import pytest
 import networkx as nx
 
 cycle = nx.cycle_graph(5, create_using=nx.DiGraph)
-tree = nx.random_tree(10, create_using=nx.DiGraph)
+tree = nx.random_tree(10, create_using=nx.DiGraph, seed=42)
 path = nx.path_graph(5, create_using=nx.DiGraph)
 binomial = nx.binomial_tree(3, create_using=nx.DiGraph)
 HH = nx.directed_havel_hakimi_graph([1, 2, 1, 2, 2, 2], [3, 1, 0, 1, 2, 3])