Why Represent Communities at More Than One Level?
A community partition gives one grouping of the vertices in a graph. In a cell-neighborhood graph, that grouping might be used to summarize local structure among cells. But a single partition cannot show how smaller groups relate to larger ones. A hierarchy represents such relationships: communities at a finer level are contained within communities at a coarser level.
This is not the same as running a clustering method several times and placing its outputs in order of cluster count or resolution. For outputs to belong to one hierarchy, their memberships must be nested. A dendrogram displays that nesting as a sequence of merges, making it possible to examine partitions at several levels without treating them as unrelated answers.
Nestedness alone does not require that only two communities merge at each step. A binary agglomerative hierarchy has the stronger property that each transition replaces exactly one pair of current communities with their union, leaving every other community unchanged. Other nested hierarchies may include a step that merges three or more communities at once.
From Merge Sequence to Dendrogram
An agglomerative procedure starts from small groups—often one vertex per community—and repeatedly merges communities according to a method-specific rule. That rule might use a graph-based objective or a measure of similarity or distance. The procedure can record each merge and, when relevant, a value called its height. The resulting tree is a dendrogram: leaves represent vertices or starting groups, and internal nodes represent merges.
The dendrogram records membership relationships. If two leaves join at a node, they belong to the same community at every cut that includes that node. If their branches do not join until a higher node, they remain in separate communities at cuts below that merge. A horizontal cut across the tree defines a partition: each group of leaves connected below the cut is one community.
Height requires care. In one dendrogram it may be a dissimilarity; in another it may encode a method-specific merge score or level. The meaning depends on the method and its display convention. Do not assume that a large height always means a stronger community, or that heights are comparable across different methods. First check what the height represents. The branching structure still indicates the merge order, but the height's numerical interpretation is method-specific.
Worked Example: Reading a Sequence of Binary Merges
Suppose a hypothetical graph has six vertices, \(A,B,C,D,E,F\). An agglomerative method reports merges at dissimilarity heights \(0.10, 0.15, 0.28, 0.35,\) and \(0.90\), in this order: \(A\) with \(B\); \(D\) with \(E\); the group \(\{A,B\}\) with \(C\); the group \(\{D,E\}\) with \(F\); and finally \(\{A,B,C\}\) with \(\{D,E,F\}\). These values are hypothetical and are interpreted here as dissimilarities, so a cut includes merges at or below its height.
Initially there are six singleton communities. The first merge replaces \(\{A\}\) and \(\{B\}\) with \(\{A,B\}\), leaving four singletons: there are \(6-1=5\) communities. The second merge gives \(\{A,B\},\{D,E\},\{C\},\{F\}\), or \(5-1=4\) communities. Each later binary merge reduces the count by one.
At a cut of height \(0.30\), the merges at \(0.10, 0.15,\) and \(0.28\) have occurred, but the merge at \(0.35\) has not. The partition is \(\{\{A,B,C\},\{D,E\},\{F\}\}\), with three communities. At height \(0.40\), the merge at \(0.35\) is included, so the partition is \(\{\{A,B,C\},\{D,E,F\}\}\), with two communities. The final merge at \(0.90\) produces one community containing all six vertices.
The cut gives a partition, not a claim that this number of communities is uniquely correct. Choosing a useful cut requires an interpretation of the method, its merge values, and the analysis goal.
What the Nesting Property Guarantees
Nesting is the key structural condition behind a dendrogram. If \(\mathcal{P}_{f}\) is finer than \(\mathcal{P}_{c}\), then no community at the finer level is split across two coarser communities. This lets a reader trace a smaller group upward to exactly one containing group at each coarser level.
For a binary agglomerative hierarchy, the community count also has a simple bookkeeping rule. If a partition has \(k\) communities, merging exactly two of them replaces two sets by their union, so the new count is \(k-2+1=k-1\). Starting from \(n\) singleton vertices and ending with one community therefore requires \(n-1\) binary merges, since each of those merges reduces the count by exactly one.
This count is a useful check on a merge record, but it does not establish that the merges are statistically or biologically meaningful. It only follows from the definition of a binary merge.
Worked Example: A Nested Step That Is Not Binary
Consider five vertices \(a,b,c,d,e\), initially partitioned as \(\mathcal{P}_{0}=\{\{a\},\{b\},\{c\},\{d\},\{e\}\}\). Suppose the next partition is \(\mathcal{P}_{1}=\{\{a,b,c\},\{d\},\{e\}\}\).
Every community in \(\mathcal{P}_{0}\) is contained in exactly one community in \(\mathcal{P}_{1}\), so the transition is nested. But the number of communities drops from five to three: \(5-3=2\). A single binary merge would reduce the count from five to four, not three. Here, \(a,b,c\) have been combined in one multiway step, so this transition is not a binary agglomerative merge.
The example shows why containment and “exactly one pair merges” must not be treated as equivalent definitions. The first describes a nested relationship; the second imposes an additional restriction on consecutive steps.
Hierarchical Output Versus a Flat Clustering
A flat clustering reports one partition. It may be the output of a graph community detection method at a chosen setting, or a partition selected for a particular analysis. That output does not, by itself, say which communities would combine at a coarser level or how they arose from finer groups.
A hierarchy contains a family of nested partitions, so a cut can provide a flat partition while retaining its relationship to other levels. By contrast, independently produced flat partitions need not be nested—even if one has more communities than the other. In the earlier material on choosing a clustering resolution, the focus was on selecting a useful resolution from graph structure. Here the additional question is whether results at different levels form one coherent merge tree.
Worked Example: Two Flat Partitions That Cannot Be Consecutive Levels
Suppose two hypothetical runs on the same six vertices return \(\mathcal{P}_{3}=\{\{A,B\},\{C,D\},\{E,F\}\}\) and \(\mathcal{P}_{2}=\{\{A,B,C\},\{D,E,F\}\}\). The subscripts show the number of communities, not a guaranteed relationship between the partitions.
For \(\mathcal{P}_{3}\) to be finer than \(\mathcal{P}_{2}\), each of its communities must fit entirely inside one community of \(\mathcal{P}_{2}\). The set \(\{C,D\}\) does not: \(C\) belongs to \(\{A,B,C\}\), while \(D\) belongs to \(\{D,E,F\}\). Therefore these partitions are not nested.
The community count decreases from three to two, but that fact alone does not make the transition a merge in a hierarchy. In a binary merge from \(\mathcal{P}_{3}\), one of its three entire communities would be joined to another, while the third would remain unchanged. The reported two-community partition instead splits the membership of \(\{C,D\}\) across its groups. These are separate flat outputs, not consecutive levels of one binary hierarchy.
How to Check and Compare Hierarchical Results
When interpreting a dendrogram, first identify the vertices or groups represented by its leaves and the meaning of its heights. Then trace the branches at a chosen cut to list the resulting communities. If the output is provided as a sequence of partitions rather than a tree, check the containment condition directly. For a binary agglomerative sequence, also check that exactly two communities are replaced by their union at every step and that all other communities are unchanged.
| Output | What it reports | What it does not establish by itself |
|---|---|---|
| One flat partition | One grouping of the graph's vertices | How groups relate to a finer or coarser level |
| Several partitions from separate runs | Several groupings, possibly at different settings | That memberships are nested or belong to one merge sequence |
| A nested hierarchy | Communities and their containment across levels | That any particular cut is the best or biologically correct choice |
| A binary agglomerative dendrogram | A nested merge history with one pair merged at each step | That the merge rule found a globally optimal hierarchy |
Methods that return a single community partition can be useful when one grouping is required. A hierarchical method is useful when the relationships between levels are part of the question. Some graph clustering procedures can produce or be used to construct a merge hierarchy; the earlier material on Walktrap clustering is one example of a graph method associated with hierarchical merges. The method's criterion and stopping rule determine the reported hierarchy, so a dendrogram should not be interpreted as though every possible merge order had been evaluated.
A useful diagnostic is to compare the displayed tree with the recorded merge list. If a cut yields a different number of communities than the merge history implies, check whether the cut passes through a merge, how ties are handled, or whether the display uses a nonstandard height convention. Also inspect whether the displayed leaves correspond to all vertices or to pre-aggregated starting groups. A tree can be read correctly only when those conventions are clear.
Limitations and Common Pitfalls
A hierarchy summarizes relationships among partitions, but it does not certify that its communities are stable, uniquely determined, or biologically meaningful. Those questions require evidence beyond the tree structure. In particular, the dendrogram's height is not automatically a p-value, a confidence measure, or a measure of biological separation. It is an encoded quantity whose meaning comes from the method.
- Assuming more communities means “finer” in the required sense. A larger community count is not enough; check that every finer community is contained in one coarser community.
- Calling every nested hierarchy binary. A multiway merge can preserve nesting. Binary agglomeration specifically requires one pairwise merge per step.
- Treating a cut as a discovered truth. A cut defines one partition from the hierarchy; it does not prove that the chosen level is uniquely correct.
- Reading merge height without its definition. A height may represent dissimilarity, a score, or another method-specific quantity. Confirm its convention before interpreting high and low values.
- Assuming a merge tree is globally optimal. An agglomerative algorithm makes choices according to its merge rule; a dendrogram alone does not show that the complete hierarchy is optimal under every possible criterion.
Check Your Understanding
Answer each question, then compare your reasoning with the brief solutions.
- A binary agglomerative algorithm begins with 12 singleton vertices and ends with one community. How many merges occur?
- Can a nested transition reduce the community count from eight to five? Is it a single binary merge?
- Two partitions have four and three communities, respectively. What must be checked before calling the three-community partition a coarser level of the four-community partition?
- What information does a dendrogram cut provide, and what does it not prove about the selected partition?
Solutions. (1) Each binary merge reduces the count by one, so \(12-1=11\) merges are required. (2) Yes, if four communities are combined in one multiway step while all other groups remain appropriately contained; it is not one binary merge because the count decreases by \(8-5=3\), rather than one. (3) Check that each community in the four-community partition is contained entirely within one community in the three-community partition. The counts alone do not establish nestedness. (4) The cut gives a partition by grouping leaves whose branches have joined below that cut. It does not prove that this cut is uniquely best, stable, or biologically correct.