Repository: networkx/networkx (python)

Issue:
Not using sparse algorithm in stochastic_block_model code

<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

### Current Behavior

In the main loop over the blocks there is a check for a diagonal block `i==j` and at the end of this `if` the edges for this block are added. There is then a check whether to use the `sparse` algorithm, and then the edges for the block are added again. 

<!--- Tell us what happens instead of the expected behavior -->

### Expected Behavior

Because the `edges` iterator has been consumed, the edges are not duplicated again, but the sparse algorithm is never used for the diagonal blocks. To fix this simply delete the

`         for e in edges:
                if seed.random() < p[i][j]:
                    g.add_edge(*e)`

from the `if i==j:` scope 

<!--- Tell us what should happen -->

### Steps to Reproduce

<!--- Provide a minimal example that reproduces the bug -->


### Environment

<!--- Please provide details about your local environment -->

Python version:
NetworkX version:

### Additional context

<!--- Add any other context about the problem here, screenshots, etc. -->



Patch:
diff --git a/networkx/generators/community.py b/networkx/generators/community.py
index a7f2294c5cf..ab23b82fe3e 100644
--- a/networkx/generators/community.py
+++ b/networkx/generators/community.py
@@ -552,14 +552,14 @@ def stochastic_block_model(
     >>> H = nx.quotient_graph(g, g.graph["partition"], relabel=True)
     >>> for v in H.nodes(data=True):
     ...     print(round(v[1]["density"], 3))
-    0.245
-    0.348
-    0.405
+    0.244
+    0.354
+    0.398
     >>> for v in H.edges(data=True):
     ...     print(round(1.0 * v[2]["weight"] / (sizes[v[0]] * sizes[v[1]]), 3))
-    0.051
-    0.022
-    0.07
+    0.047
+    0.02
+    0.071
 
     See Also
     --------
@@ -635,9 +635,6 @@ def stochastic_block_model(
                 edges = itertools.combinations(parts[i], 2)
                 if selfloops:
                     edges = itertools.chain(edges, zip(parts[i], parts[i]))
-            for e in edges:
-                if seed.random() < p[i][j]:
-                    g.add_edge(*e)
         else:
             edges = itertools.product(parts[i], parts[j])
         if sparse:


Test patch:
diff --git a/networkx/generators/tests/test_community.py b/networkx/generators/tests/test_community.py
index 2fa107f6dde..f7ea1baf6e5 100644
--- a/networkx/generators/tests/test_community.py
+++ b/networkx/generators/tests/test_community.py
@@ -189,7 +189,7 @@ def test_stochastic_block_model():
     C = G.graph["partition"]
     assert len(C) == 3
     assert len(G) == 450
-    assert G.size() == 22160
+    assert G.size() == 21842
 
     GG = nx.stochastic_block_model(sizes, probs, range(450), seed=0)
     assert G.nodes == GG.nodes
@@ -220,6 +220,21 @@ def test_stochastic_block_model():
     assert G.nodes == GG.nodes
 
 
+def test_sbm_sparse_applies_to_diagonal_blocks():
+    # see gh-8557 sparse heuristic applies to diagonal blocks
+    # Single block = only a diagonal block (i==j)
+    sizes = [50]
+    probs = [[0.5]]
+
+    G_sparse = nx.stochastic_block_model(sizes, probs, seed=42, sparse=True)
+    G_dense = nx.stochastic_block_model(sizes, probs, seed=42, sparse=False)
+
+    # These would be equal before the fix because diagonal blocks
+    # always took the dense path. Now they differ because they use
+    # different RNG consumption patterns.
+    assert G_sparse.edges() != G_dense.edges()
+
+
 def test_generator():
     n = 250
     tau1 = 3