Condition in test_louvain::test_threshold not representative of graphs with same parameters but different seed.

[ebokai]

Current Behavior

def test_threshold():
    G = nx.LFR_benchmark_graph(
        250, 3, 1.5, 0.009, average_degree=5, min_community=20, seed=10
    )
    partition1 = nx.community.louvain_communities(G, threshold=0.3, seed=2)
    partition2 = nx.community.louvain_communities(G, seed=2)
    mod1 = nx.community.modularity(G, partition1)
    mod2 = nx.community.modularity(G, partition2)

    assert mod1 < mod2

The test for the Louvain algorithm asserts if the modularity of a partition obtained using threshold=0.3 is smaller than the modularity when using the default value for a specific graph generated using the LFR_benchmark_graph. However, if the graph used for testing is changed, this condition no longer holds in general (see Steps to Reproduce).

Expected Behavior

I suggest changing the test to assert mod1 <= mod2 instead.

Steps to Reproduce

If we use the same settings for the graph generation but allow for a different seed we do not always pass the assertion.

generating = True
tries = 0
while generating:
    seed = np.random.randint(50000) 
    try:
        G = nx.LFR_benchmark_graph(250, 3, 1.5, 0.009, average_degree = 5, min_community = 20, seed = seed)
        print(f'generated graph {seed}')
        generating = False
    except:
        tries += 1
print(tries)

check = 0
for i in range(100):
    random_seed = np.random.randint(50000)
    p1 = nx.community.louvain_communities(G, threshold = 0.3, seed = random_seed)
    p2 = nx.community.louvain_communities(G, seed = random_seed)
    m1 = nx.community.modularity(G, p1)
    m2 = nx.community.modularity(G, p2)
    print(m1, m2)
    if m1 < m2:
        check += 1
print(check)

On my machine, it took 28 tries to generate a graph (seed = 26537). For this graph, the test was successful 83/100 times. If we relax the test condition to assert m1 <= m2 the test succeeds 100/100 times.

Environment

Python version: 3.10
NetworkX version: 3.1

[dschult]

Thanks @ebokai for this great reproducing example code!