Communities as Sparse Separations
A proposed community in a social network should have many connections within the group and relatively few connections to the rest of the network. A graph cut records the edges between a group and its complement. The number of crossing edges is useful, but on its own it can favor separating a very small group. Conductance adjusts the cut size for the total degree of the groups being separated.
Throughout, \(G=(V,E)\) is a finite, simple, undirected graph. An edge is written \(uv\), and \(G[S]\) denotes the induced subgraph on \(S\subseteq V\): it contains every edge of \(G\) whose two endpoints lie in \(S\). We consider a proposed split \(S,V\setminus S\), where \(S\) is nonempty and is not all of \(V\). A partition here means these two disjoint sets together cover \(V\); either set may contain a single vertex.
The edge boundary is a set of edges, not a set of vertices. An edge belongs to \(\partial S\) exactly when one endpoint is in \(S\) and the other is outside it. In particular, edges with both endpoints in \(S\) do not cross the cut. Volume counts degree, so an edge internal to \(S\) contributes two to \(\operatorname{vol}(S)\), while a boundary edge contributes one.
The denominator uses the smaller of the two volumes. This makes conductance a relative measure: it compares the number of crossing edges with the total degree on the less-connected side. If either side has volume zero, the displayed ratio is undefined; we use the definition only when both volumes are positive. For a graph with at least one edge, every partition into two nonempty sets has positive volume on each side only if neither side consists solely of isolated vertices. Isolated vertices therefore require care: their presence does not add to volume, and a split whose one side has volume zero has no conductance under this definition.
Why Volume Complements Cut Size
Proof. In the sum \(\operatorname{vol}(S)=\sum_{v\in S}\deg(v)\), each edge of \(G[S]\) is counted once at each of its two endpoints, giving a total contribution of two. Each edge of \(\partial S\) is counted once, at its endpoint in \(S\). Edges with both endpoints outside \(S\) contribute nothing. These are all possible edge types, so \(\operatorname{vol}(S)=2|E(G[S])|+|\partial S|\). In particular, \(|\partial S|\leq\operatorname{vol}(S)\). Applying the same argument to \(V\setminus S\) gives \(|\partial S|\leq\operatorname{vol}(V\setminus S)\), since \(\partial(V\setminus S)=\partial S\). Thus the numerator is nonnegative and no larger than the minimum in the denominator, which proves \(0\leq\phi(S)\leq1\). Finally, replacing \(S\) by its complement leaves the boundary size unchanged and swaps the two volumes, so it leaves their minimum unchanged. Therefore \(\phi(S)=\phi(V\setminus S)\). \(\square\)
This identity also explains why volume is not simply the number of vertices in a group. A group with a few high-degree vertices can have greater volume than a larger group with few connections. Conductance compares the cut with connection totals, not with group sizes.
Comparing Candidate Splits
Worked Example: Two Triangles Joined by One Edge
Let \(G\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,13,23,45,46,56,34\}\). The first three vertices form a triangle, the last three form a triangle, and \(34\) joins the two triangles. Compare the split \(S=\{1,2,3\}\) with the split \(T=\{1\}\).
For \(S\), the only edge with one endpoint in \(S\) and one outside is \(34\), so \(|\partial S|=1\). The degrees of \(1,2,3\) are respectively \(2,2,3\); hence \(\operatorname{vol}(S)=2+2+3=7\). The degrees of \(4,5,6\) are \(3,2,2\), giving \(\operatorname{vol}(V\setminus S)=3+2+2=7\). Therefore \(\phi(S)=1/\min(7,7)=1/7\).
For \(T=\{1\}\), the boundary consists of \(12\) and \(13\), so \(|\partial T|=2\). Its volume is \(\deg(1)=2\), while the complementary volume is \(14-2=12\): the total degree is \(2+2+3+3+2+2=14\). Thus \(\phi(T)=2/\min(2,12)=1\).
Check: The edge list has seven edges, so the total degree is \(2|E|=2\cdot7=14\), agreeing with the degree sum. The first split has one crossing edge and conductance \(1/7\); the singleton split has two crossing edges and conductance \(1\). Both measures favor the triangle split in this example.
The example illustrates the intended interpretation: the two triangles each have several internal edges, while only one edge connects them. A cut with few edges is a useful clue, but its size should be read relative to the amount of connection on each side.
Worked Example: A High-Degree Vertex Between Groups
Let \(G\) have \(V=\{a,b,c,d,e,f,h\}\). Its edges are \(ab,ac,bc,de,df,ef\), together with \(ha,hb,hc,hd,he,hf\). Thus \(a,b,c\) form a triangle, \(d,e,f\) form another, and the high-degree vertex \(h\) is adjacent to all six triangle vertices.
Consider \(S=\{a,b,c\}\). Each of \(a,b,c\) has degree \(3\): two neighbors in its triangle and the neighbor \(h\). Hence \(\operatorname{vol}(S)=3+3+3=9\). The boundary is exactly \(ha,hb,hc\), so its size is \(3\). The other triangle vertices each have degree \(3\), and \(h\) has degree \(6\); therefore \(\operatorname{vol}(V\setminus S)=3+3+3+6=15\). The conductance is \(3/\min(9,15)=1/3\).
If instead \(h\) is placed with \(a,b,c\), the split is \(\{a,b,c,h\},\{d,e,f\}\). Its boundary consists of \(hd,he,hf\), again three edges. The volumes are \(9+6=15\) and \(3+3+3=9\), so its conductance is also \(3/\min(15,9)=1/3\). The two assignments of \(h\) tie: assigning this high-degree vertex to either group leaves three edges crossing.
As a contrasting candidate, isolate \(h\): take \(S=\{h\}\). Its boundary contains all six incident edges, its volume is \(6\), and the complementary volume is \(24-6=18\). Here the total degree is \(3+3+3+3+3+3+6=24\). Thus \(\phi(\{h\})=6/\min(6,18)=1\).
Check: There are twelve edges, so the total degree must be \(2\cdot12=24\), matching the calculation. The hub’s degree contributes six to the volume of whichever group contains it, and its ties to the other group create crossing edges. A high-degree vertex can therefore affect both the cut and its normalizing volume; it should not be treated as just one ordinary vertex when interpreting a proposed split.
This example also warns against assigning community membership from degree alone. The graph gives no reason to prefer one of the two hub assignments by conductance: they have the same boundary size and the same smaller-side volume. Other information about the network may be needed to decide whether the hub belongs with one group, functions as a connector, or should be treated separately.
When Conductance Changes the Ranking
Worked Example: A Smaller Cut Is Not Always the Better Split
Let \(G\) have \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,13,23,45,46,56,34,26,17\}\). Vertices \(1,2,3\) form a triangle, vertices \(4,5,6\) form another, edges \(34\) and \(26\) connect the triangles, and \(17\) attaches vertex \(7\) to vertex \(1\).
First take the singleton \(A=\{7\}\). Its only boundary edge is \(17\), so \(|\partial A|=1\). The volume of \(A\) is \(\deg(7)=1\), and the complement has volume \(17\), as the total degree is \(18\). Thus \(\phi(A)=1/\min(1,17)=1\).
Now take \(B=\{1,2,3,7\}\). The crossing edges are \(34\) and \(26\), so \(|\partial B|=2\). The degrees of \(1,2,3,7\) are \(3,3,3,1\), giving \(\operatorname{vol}(B)=10\). The degrees of \(4,5,6\) are \(3,2,3\), giving \(\operatorname{vol}(V\setminus B)=8\). Therefore \(\phi(B)=2/\min(10,8)=1/4\).
The singleton has the smaller cut size, \(1\) rather than \(2\), but the two-triangle split has the lower conductance, \(1/4\) rather than \(1\). A cut-size-only comparison prefers peeling off the leaf; conductance favors the separation between the two groups, relative to the connections on the smaller-volume side.
Check: The listed edges give degrees \(3,3,3,3,2,3,1\), whose sum is \(18\); the edge count is \(9\), so \(2|E|=2\cdot9=18\) as required. The boundary counts also follow directly from the edge list: only \(17\) crosses for \(A\), while \(34\) and \(26\) cross for \(B\).
Common Pitfall and Practical Interpretation
Using the number of vertices as the denominator. For the split \(B=\{1,2,3,7\}\) in the previous example, an incorrect calculation might divide the two crossing edges by the four vertices in \(B\), obtaining \(2/4=1/2\). This is not conductance: the definition uses the smaller volume, not the smaller vertex count. The two side volumes are \(10\) and \(8\), so the correct calculation is \(2/\min(10,8)=2/8=1/4\).
Neither cut size nor conductance proves that a group is a real-world community. They quantify particular structural features of a chosen partition. Cut size counts crossing edges; conductance scales that count by the smaller side’s degree volume. A high-degree vertex can increase volume substantially and may connect strongly to several groups at once. Interpret the numerical comparison alongside the network’s context, and compare candidate partitions using the same definitions.
Check Your Understanding
For each question, identify the boundary edges before calculating a cut size or conductance.
- For the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\), calculate the cut size, both volumes, and conductance for \(S=\{1,2\}\).
- Explain why an edge with both endpoints in \(S\) contributes two to \(\operatorname{vol}(S)\) but contributes nothing to \(|\partial S|\).
- Give a partition with positive volumes for which the cut size is \(1\) but conductance is \(1\). State its graph and verify the values.
- Why can a high-degree vertex change both the boundary and volume when it is assigned to one side of a proposed split?
- Show from the definition that swapping the two sides of any partition with positive volumes leaves conductance unchanged.