Subgraph Census¶
Enumeration census — instantiates Network Motif and Pattern Discovery
Exhaustively enumerates every subgraph of a fixed size and tallies how often each canonical shape occurs, producing the complete observed-frequency table.
Before any motif can be called frequent, someone has to actually count — completely, not selectively. Subgraph Census is that count. Fix a size k, and it enumerates every connected k-node subgraph in the network, sorts each into its canonical shape, and reports how many instances of each shape occur and how they are distributed. Its distinctive contribution is exhaustive measurement: a census, not a search for something suspected, and not a judgment about what the counts mean. It aspires to completeness — the guarantee that the observed-frequency table reflects the whole graph rather than the shapes an analyst happened to look for — and it stops there. It hands the raw counts to the steps that will decide whether any of them are enriched.
Example¶
An organizational analyst studying an email network — employees as nodes, "sent mail to" as directed edges — wants the complete profile of three-person communication patterns in the Enron corpus. She runs a triad census: the mechanism visits every connected triple of employees and classifies its pattern into one of the sixteen possible directed three-node types — the mutual triad, the transitive chain, the cyclic triple, and so on.[n1] For each type it returns a count and, importantly, how the count is distributed: whether a shape's instances are spread across many independent trios or piled around a handful of high-traffic executives.
The output is a flat table — sixteen rows, each a triad type with its total and its concentration. One striking figure is the count of transitive triads (A mails B, B mails C, A mails C), far higher than the cyclic type. The census asserts nothing about why; it does not know whether "high" means enriched, and it deliberately reports the concentration so the next step will not be fooled by a count that is really one busy manager appearing in thousands of trios. Its whole deliverable is a complete, honest tally.
How it works¶
The census's distinguishing discipline is completeness and honest counting:
- Fix the size and cover everything. Choose k, then systematically visit every connected k-node subgraph exactly once — no sampling, no seed selection, so the tally is exhaustive for that size.
- Bin by canonical shape. Route each enumerated instance through a canonical key so structurally identical subgraphs land in the same bin and the counts are not inflated by relabelings.
- Tally and profile distribution. Report not just the raw count per shape but its spread — how many independent neighborhoods contribute versus how much rides on a few high-degree nodes — because the same count means different things depending on concentration.
- Handle overlap explicitly. Count instances under a stated overlap rule (all occurrences, or edge-disjoint only), since the convention changes every number.
It produces observed counts; it does not compare them to anything.
Tuning parameters¶
- Subgraph size k — the dominant cost and coverage dial. Exhaustive counting is feasible for k = 3 or 4 on most graphs but explodes combinatorially beyond, so the census trades reach against tractability.
- Overlap convention — count every occurrence, or only node/edge-disjoint instances. Disjoint counting resists inflation by a single dense region; full counting captures true multiplicity.
- Connected-only vs. all — whether disconnected k-node sets are counted; connected-only is the usual, cheaper choice.
- Concentration reporting — whether the census returns just totals or also the distribution across nodes, which downstream steps need to avoid hub artifacts.
- Directed/labeled resolution — how many distinctions the shape-binning respects, which sets the number of census categories.
When it helps, and when it misleads¶
Its strength is completeness: because it counts everything of size k, it cannot be accused of finding only what it went looking for, and its distribution reporting flags when a big number is really one hub in disguise. It is the trustworthy denominator the whole analysis rests on — an observed-frequency table with no selection bias baked in.
Its failure mode is the combinatorial wall and the seduction of raw counts. Push k past four on a large dense graph and exhaustive enumeration becomes infeasible, forcing a switch to sampling (a different mechanism) or a smaller size. And a census total, read alone, invites the frequency-function conflation the archetype warns against: a shape can top the table simply because the graph is dense or a few nodes are enormous. The classic misuse is announcing the most common subgraph as "the network's motif." The guarding discipline is to treat census counts as inputs — always paired with a null and a significance step before any shape is called a motif — and to report concentration so a hub-inflated count is visible.
How it implements the components¶
Subgraph Census fills the exhaustive-measurement layer:
subgraph_enumeration_process— it enumerates every connected k-node subgraph exactly once, the exhaustive coverage that makes the tally complete rather than anecdotal.recurrence_measurement— it counts each canonical shape and profiles how those counts are distributed across the network, the observed-recurrence measurement the analysis is built on.
It does not define the canonical-key format it bins by (isomorphism_and_canonical_labeling) — that is Canonical Adjacency Encoding, which it consumes; and it does not take a configurable grammar or scale via sampling (motif_scope_and_grammar) — that is Graph Motif Mining Algorithm, its nearest twin: the census is an exhaustive count for measurement, whereas the miner is a configurable, samplable search engine.
Related¶
- Instantiates: Network Motif and Pattern Discovery — supplies the complete observed-frequency table the enrichment step consumes.
- Consumes: Canonical Adjacency Encoding — the canonical keys by which it bins structurally identical subgraphs.
- Sibling mechanisms: Graph Motif Mining Algorithm · Canonical Adjacency Encoding · Motif Enrichment Table · Random Graph Null Ensemble · Degree-Preserving Edge Swap · Temporal Sliding-Window Motif Scan
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Subgraph Census operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it exhaustively enumerates every subgraph of a fixed size and tallies how often each canonical shape occurs, producing the complete observed-frequency table.
Independent corroboration: The frozen evidence defines Subgraph Census as 'Exhaustively enumerates every subgraph of a fixed size and tallies how often each canonical shape occurs, producing the complete observed-frequency table', so its operative form is Analysis, Modeling & Optimization.
Nearest alternative: Decision, Gate & Allocation — Subgraph Census includes features of a case-specific gate, selection, routing, prioritization, or resource disposition, but its defining operation is an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Mathematics
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Enumerating fixed-size subgraphs and canonical shapes is graph combinatorics.
Related originating lineages:
- Computer Science & Software Engineering — Algorithms compute censuses.
- Data Science & Analytics — Motif frequencies characterize networks.
Review outcome: Independent reviewer agreement; high confidence.
Notes¶
[n1] The triad census of Paul Holland and Samuel Leinhardt classifies every three-node subgraph of a directed network into sixteen isomorphism types; it is the classic exhaustive subgraph count in social network analysis and the template for size-k census at larger k. ↩