Conductance: Graph Community Detection in Python

Conductance is a number between 0 and 1 that scores how well a group of nodes is separated from the rest of a graph. A low score means the group is densely connected inside and barely connected outside — which is what “community” means in network terms. This guide explains the formula in plain language and shows how to compute it in Python, both by hand and with NetworkX.

The intuition#

Imagine drawing a circle around some of the nodes in a network. Two things matter: how many edges you had to cut to draw that circle, and how many edge-ends are inside the circle in total. If you cut very few edges relative to the size of the group, you have found a natural seam in the network.

Conductance is exactly that ratio. A group of friends who all know each other and barely know anyone else has low conductance. A randomly chosen handful of nodes has high conductance, because almost every edge they have leads outside.

The formula#

For a set of nodes S in a graph:

conductance(S) = cut(S) / min( vol(S), vol(complement of S) )

• cut(S) is the number of edges with one end inside S and one end outside.
• vol(S) is the sum of the degrees of all nodes in S — that is, the total number of edge-ends attached to the group.
• Dividing by the smaller of the two volumes stops the measure from being fooled by a group that contains nearly the whole graph.

The result runs from 0 (no edges leave the group at all) to 1 (every edge leaves).

Computing it by hand#

def conductance(adjacency, S):
    """adjacency: dict of node -> set of neighbours. S: a set of nodes."""
    S = set(S)
    all_nodes = set(adjacency)
    T = all_nodes - S

    if not S or not T:
        return 0.0   # nothing to separate

    cut = 0
    vol_s = 0
    for node in S:
        neighbours = adjacency[node]
        vol_s += len(neighbours)
        cut += len(neighbours - S)

    vol_t = sum(len(adjacency[n]) for n in T)
    denominator = min(vol_s, vol_t)

    return cut / denominator if denominator else 0.0

Try it on a graph with two obvious clusters joined by a single edge:

graph = {
    "a": {"b", "c"},
    "b": {"a", "c"},
    "c": {"a", "b", "d"},     # the bridge
    "d": {"c", "e", "f"},
    "e": {"d", "f"},
    "f": {"d", "e"},
}

print(conductance(graph, {"a", "b", "c"}))   # 0.125  - a real community
print(conductance(graph, {"a", "d"}))        # 0.8    - not a community
print(conductance(graph, {"a"}))             # 1.0    - a single node

The first group cuts one edge out of eight edge-ends. The second group is two nodes that are not even connected to each other, so nearly everything they touch is outside.

Using NetworkX#

NetworkX has this built in, and it handles weights and directed graphs for you:

import networkx as nx

G = nx.Graph()
G.add_edges_from([
    ("a", "b"), ("a", "c"), ("b", "c"),
    ("c", "d"),
    ("d", "e"), ("d", "f"), ("e", "f"),
])

first = {"a", "b", "c"}
second = set(G) - first

print(nx.conductance(G, first, second))   # 0.125

You can also compute the pieces separately, which is useful when you want to report them:

print(nx.cut_size(G, first, second))   # 1
print(nx.volume(G, first))             # 8
print(nx.volume(G, second))            # 8

Scoring communities from an algorithm#

Conductance is most useful as a way to compare and rank the groups a community-detection algorithm produced:

import networkx as nx
from networkx.algorithms.community import louvain_communities

G = nx.karate_club_graph()
communities = louvain_communities(G, seed=42)

scored = []
for group in communities:
    rest = set(G) - group
    if rest:
        scored.append((nx.conductance(G, group, rest), len(group), sorted(group)[:4]))

for score, size, sample in sorted(scored):
    print(round(score, 3), "size", size, "e.g.", sample)

The groups that sort to the top are the ones the network genuinely supports. A group with a conductance near 0.5 is barely better than an arbitrary split, whatever the algorithm called it.

Practical cautions#

• Disconnected components. A component with no edges to the rest of the graph has conductance 0 by definition. That is technically correct and usually not an interesting finding.
• Weighted graphs. If your edges carry weights, degree should mean the sum of weights, not the count. NetworkX does this when you pass weight="weight"; the hand-written version above does not.
• Directed graphs. Conductance is defined for undirected graphs. For a directed network, decide first whether you care about in-edges, out-edges or both, and convert deliberately with G.to_undirected() rather than letting a library guess.
• Comparing across graphs. Conductance values are only meaningful within one graph. A 0.2 in a sparse network and a 0.2 in a dense one do not mean the same thing.

Where to go next#

• What is an algorithm? — background for the graph traversal ideas here.
• Python dictionaries explained — the structure the adjacency list is built from.
• Python virtual environments — where to install NetworkX cleanly.