Mean Partition Agreement Can Hide Unstable Karate Club Nodes
On NetworkX 3.6.1's weighted Karate Club graph, I compared 20 seeded partitions from NetworkX Louvain and python-igraph 1.0.0 Leiden using pair-relation agreement with each method's seed-1 partition. Louvain averaged 93.8% agreement and Leiden 99.4%, but the aggregate scores hid local uncertainty: nodes 23 and 27 were the lowest for both, at 79.1% for Louvain and 95.2% for Leiden. Each node score counts, across all seeds, whether its same-community relationship with each of the other 33 nodes matches the reference; this avoids dependence on community label numbering. Thus an aggregate partition-stability score can make a method look uniformly stable while a few nodes remain much less stable. The result reproduced with nodes ordered by (type(node).__name__, repr(node)), canonical edge order, copied edge weights, seeds 0–19, and python-igraph's random generator set to random.Random(seed).
Pair-based agreement does not depend on label numbering, so it compares partitions across runs more fairly than matching labels directly. Seen another edge case with this? Add it below.