One Graph, Different Questions
Community-detection methods do not all ask the same question about a cell graph. Modularity asks whether the within-community edge density exceeds a degree-based null expectation. Label propagation uses the labels most common among a vertex’s neighbors. Infomap asks whether a partition helps describe random walks on the graph with a shorter code. Since these criteria differ, the resulting partitions can differ too.
We will use one small, undirected, unweighted graph throughout. Its vertices are \(a,b,c,d,e,f\). The edges are \(ab, ac, bc, cd, de, df, ef\): two triangles joined by the single edge \(cd\). Thus there are \(m=7\) edges. This deliberately simple graph lets us track every calculation. It is a teaching example, not a claim that real cell graphs have this structure.
For the modularity comparison, use the standard undirected modularity with resolution fixed at its default value. For the flow-based comparison, use the map equation for the stationary random walk on this graph. The graph is connected, so the walk has a unique stationary distribution; because it is undirected, the stationary probability of a vertex is proportional to its degree. Label propagation is a local procedure, and its output can depend on update order and tie-breaking.
Worked Example: Modularity Favors the Two Triangles Over One Community
Worked Example: Calculating Modularity for the Split
Consider the partition \(C_1=\{a,b,c\}\), \(C_2=\{d,e,f\}\). Each community contains three internal edges. The degrees of \(a,b,c\) are \(2,2,3\), respectively, so \(K_1=7\). The degrees of \(d,e,f\) are \(3,2,2\), so \(K_2=7\). The edge count is \(m=7\).
Substituting these values into the definition gives
The exact expression is \(2(3/7-1/4)=5/14\), which rounds to \(0.3571\). If all six vertices are put in one community, then \(l_C=m=7\) and \(K_C=2m=14\), giving \(Q=7/7-(14/14)^2=0\). Thus the two-triangle split has greater modularity than the one-community partition.
This calculation compares two candidate partitions; it does not, by itself, prove that every possible partition has lower modularity. A modularity-based algorithm searches for a partition with a high objective value, often using local moves and aggregation. On this graph, the split is a natural high-modularity result: joining the two triangles adds one crossing edge to the internal edge count, but also incurs a large degree-based penalty. The calculation establishes the comparison we need without treating an algorithm’s heuristic search as a proof of global optimality.
Worked Example: A Tie-Dependent Label-Propagation Run
In basic label propagation, each vertex begins with a label, often its own. A vertex is updated by adopting a label that occurs most often among its neighbors. If multiple labels tie for the largest count, a tie-breaking rule chooses among them. The process repeats until labels stop changing or a stopping rule is reached. Vertices with the same final label form a community.
Worked Example: Tracing One Legal Update Sequence
Start with distinct labels \(A,B,C,D,E,F\) on vertices \(a,b,c,d,e,f\). Update vertices in the order \(c,a,b,d,e,f\), using the following permitted choices when there is a tie.
Update \(c\). Its neighbors \(a,b,d\) have labels \(A,B,D\), each occurring once. Choose \(D\), so \(c\) takes label \(D\).
Update \(a\). Its neighbors \(b,c\) have labels \(B,D\), tied at one occurrence each. Choose \(D\). Then update \(b\): its neighbors \(a,c\) both have label \(D\), so \(b\) takes \(D\).
Update \(d\). Its neighbors \(c,e,f\) have labels \(D,E,F\), again tied. Choose \(D\). Update \(e\): its neighbors \(d,f\) have labels \(D,F\), tied, so choose \(D\). Finally, \(f\) has neighbors \(d,e\), both labeled \(D\), and adopts \(D\).
All six vertices now have label \(D\), so the run has reached the one-community partition. It is stable: every vertex has only neighbors with label \(D\). This is a valid outcome of the stated update rule, but it is not the two-triangle partition found above. Other tie choices or update orders can produce a different result. In particular, this example shows why a label-propagation output should not be described as the unique partition implied by the graph.
Worked Example: Comparing Random-Walk Code Lengths
Infomap’s map equation scores how economically a random walk can be encoded when vertices are grouped into modules. For a proposed partition, let \(q_i\) be the stationary probability flow exiting module \(i\), and let \(q=\sum_i q_i\). The index codebook records module changes; each module has a codebook for visits to its vertices and exits from that module. The map equation’s expected description length, in bits per step, is
where \(H\) is Shannon entropy in bits, \(Q\) is the distribution of exits among modules, \(P_i\) is the code distribution for module \(i\), and \(p_i\) is the stationary probability of being at a vertex in that module. Lower \(L\) means a shorter expected description under this coding scheme.
Worked Example: One Module Versus Two
For this undirected graph, the vertex degrees are \(2,2,3,3,2,2\), with total degree \(14\). The stationary probabilities are therefore degree divided by \(14\). For the one-module partition, there is no module exit, and the codebook contains the six vertex probabilities. Its entropy is
Now use the two-triangle partition. The only crossing edge is \(cd\). In the stationary walk, the probability of traversing that edge in either specified direction is \(1/14\). Each module therefore has exit flow \(q_i=1/14\), and total exit flow is \(q=1/7\). The stationary probability mass of vertices in either module is \(p_i=7/14=1/2\). The index codebook has two equally likely exits, so \(H(Q)=1\) bit.
Within either module’s codebook, the exit probability is \((1/14)/(1/2+1/14)=1/8\). The vertex probabilities in that codebook are \(3/8,1/4,1/4\): the vertex at the bridge has degree 3, and the other two have degree 2. Thus
The two modules have identical codebook distributions, so
For these two candidate partitions, the two-module description is shorter: \(2.321<2.557\) bits per step. This comparison supports the split under the map equation. As with the modularity calculation, comparing these candidates alone does not establish a global optimum over every partition. A flow-based algorithm searches for a partition with a short description, and its result depends on the method’s search procedure as well as its objective.
What the Comparison Shows
On this graph, the modularity comparison favors the two-triangle partition over the single community, and the map-equation comparison also favors the split over one community. The traced label-propagation run, however, ends with all vertices together. That outcome does not contradict the other calculations: label propagation follows local neighbor-label frequencies and the particular tie choices, rather than directly optimizing either of those global scores.
| Method | Criterion used here | Illustrated result | Important qualification |
|---|---|---|---|
| Modularity-based detection | Within-community edges relative to a degree-based null expectation | The two-triangle split has \(Q\approx0.3571\), versus \(Q=0\) for one community | A heuristic search need not prove a global optimum |
| Label propagation | Most frequent neighboring label at each update | The chosen tie sequence reaches one community | Update order and tie-breaking can change the result |
| Infomap | Expected map-equation code length for random walks | The split has shorter code length than one community | Candidate score comparisons are not an exhaustive search |
For single-cell analysis, these partitions describe structure in a constructed neighborhood graph. A community is not automatically a cell type, and a partition score is not evidence of biological causation or validation. Compare the assignments with the analysis goal and relevant biological information; do not treat a higher modularity or shorter code length as proof that the partition is biologically correct.
Diagnostics, Limitations, and a Common Pitfall
Before interpreting a result, check that the methods were applied to the intended graph: confirm whether edges are directed or undirected, whether weights were used, and whether disconnected or isolated vertices are present. The examples here assume an undirected, unweighted, connected graph. Changing those conditions can change degree calculations, random-walk flows, and the behavior of community-detection algorithms. Also check whether the returned labels are stable across reasonable runs when the method includes stochastic choices.
A useful comparison reports both the partition and the criterion used to obtain it. For modularity, report the objective value for the candidate partition and specify the graph on which it was computed. For Infomap, the map-equation value is measured as expected code length, not as a probability or a test statistic. For label propagation, document the implementation and tie-breaking or convergence settings, since local updates need not optimize a single global score.
Common mistake: “Modularity is higher for the split, so the split must be the true cell-type partition.” This confuses an objective value with biological truth. The correction is to say that the split scores higher under the specified modularity definition on this graph; evaluating its biological meaning requires separate evidence. A second related mistake is to assume that all methods should return the same partition. They need not: each method uses a different criterion, and some have additional dependence on update order or search choices.
Check Your Understanding
Answer the questions, then compare with the solutions below.
- For the two-triangle partition, state \(l_C\), \(K_C\), and the contribution of either community to modularity.
- Why is the all-one-community partition stable at the end of the label-propagation run, and why does that not show it has the highest modularity?
- In the map-equation calculation, what is the total exit flow for the two-module partition, and what does a lower \(L\) mean?
- Name one graph assumption made in the worked calculations and explain what could change if it were violated.
- Is a higher modularity score evidence that a partition is a true cell-type classification? Explain.
Solutions. (1) Each triangle community has \(l_C=3\) internal edges and degree sum \(K_C=7\). Its modularity contribution is \(3/7-(7/14)^2=5/28\approx0.1786\). (2) Every vertex has only neighbors with the same label, so no update changes a label. Stability under local label updates does not mean the partition maximizes modularity; the all-in-one partition has \(Q=0\), lower than the split’s \(Q=5/14\). (3) The total exit flow is \(q=1/14+1/14=1/7\). A lower \(L\) means a shorter expected description of the random walk under the map equation. (4) The calculations assume an undirected, unweighted, connected graph. Directed edges, weights, or isolated vertices can alter degrees or stationary flows and therefore change scores and algorithm behavior. (5) No. A higher score means the partition scores better under that objective on the specified graph; biological interpretation requires separate evidence.