Home / Curated / Algorithms / Clauset–Newman–Moore community detection

Clauset–Newman–Moore community detection

Algorithms AIMech:CNMCommunityDetection DRAFT

Aliases: CNM, CNM community detection, fast modularity community detection

A greedy community-detection algorithm that agglomerates graph vertices using modularity changes, with sparse change tables and heap-based maximum tracking to accelerate the construction of a merge hierarchy and selection of a partition by modularity.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 672 native IDs, names, aliases and scoped synonyms for CNM and publication identifiers; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 79, 0 and 0 lines. All 79 public matches were read and are existing HAC-Q/source/discovery context and rendered counterparts, not this maintained identity. Semantic assessment covered 46 AIO and 267 native definitions: all 46 AIO and 264 previous native rows were unchanged and three new variant definitions and full records were read. Sixteen complete annotated AIO node/edge/generated contexts were verified unchanged and candidate-specific native records assessed. The author catalog identifies CNM with the 2004 sparse greedy modularity method. It is distinct from the 2008 hierarchical random-graph model and the HAC-Q link-prediction variant. The record preserves the earlier greedy objective as context without treating every modularity optimizer as this algorithm.

Claims & Grounded Evidence

7 Claims

Mechanism #modularity-agglomeration

The procedure starts with singleton communities and greedily merges groups according to a degree-corrected modularity objective. For an undirected graph, the objective compares within-group observed edges with degree-product expectations. The merge sequence defines a dendrogram, and the largest modularity encountered selects a cut along that sequence. This is approximate optimization rather than a search over all possible partitions.

supports Source: Finding community structure in very large networks · Locator: Section II, PDF pp. 2–3, Equations 4–7 and algorithm steps; Section III, p. 4 and Figure 1
supports Source: Fast Modularity Community Structure Inference Algorithm · Locator: Mandatory file outputs: .info and .joins; optional .groups output

Mechanism #sparse-update-structures

The efficient formulation stores change entries only for pairs of communities joined by an edge. It uses balanced-tree sparse rows, row maxima and a global maximum heap, together with community degree fractions. Merging two communities changes their neighboring rows using different updates for common and one-sided neighbors. Sparse omission of a nonadjacent pair does not mean that its true modularity change is zero.

supports Source: Finding community structure in very large networks · Locator: Section II, PDF p. 3, three data structures and Equations 8–10

Limitation #printed-normalization-boundary

In the inspected arXiv v2, the connected-pair initialization in Equation 8 is one half of the modularity change derived from Equations 4 and 7, while the later one-sided updates retain a factor of two. On a three-vertex path, the printed first gain is one eighth instead of one quarter, and the next printed update is zero instead of one eighth. Literal accumulation from the defined initial modularity ends at minus one quarter even though the one-block modularity is zero. The record preserves this printed mismatch without asserting that the authors’ software or experiments use it.

supports Source: Finding community structure in very large networks · Locator: Section II, PDF pp. 2–3, Equations 4, 7, 8 and 10, algorithm step 2; curator calculation in research/discovery/cnm-boundaries.py

Scope #documented-input-and-output-scope

The author’s documentation requires the original unweighted program to receive a single connected undirected graph without self-loops or parallel edges. This restriction matters because the sparse adjacent-pair procedure can otherwise exhaust eligible merges before one community remains. The documentation exposes both merge/modularity history and communities at a selected step; a separately linked weighted version is outside this record’s inspected implementation scope.

supports Source: Fast Modularity Community Structure Inference Algorithm · Locator: Introduction and October 2008 update; Input file requirements; Common error messages; File outputs
supports Source: Finding community structure in very large networks · Locator: Section II, PDF p. 3, sparse support and stopping step; curator disconnected-components example in research/discovery/cnm-boundaries.py

Scope #complexity-and-ties

The stated runtime bound is O(m d log n), where m is the edge count, n is the vertex count and d is the resulting dendrogram depth. The O(n log-squared n) specialization additionally assumes sparse input and roughly balanced depth. The paper also describes a row-scan implementation with a worse worst-case bound and notes that tie handling can change the hierarchy. These choices do not support universal linear runtime or identical outputs across every implementation.

supports Source: Finding community structure in very large networks · Locator: Section II, PDF pp. 3–4, runtime argument and scan implementation; Conclusions, p. 5

Limitation #greedy-optimality-boundary

A small exact-definition reference calculation on a six-vertex path illustrates that the best cut encountered by greedy merging need not maximize modularity globally. With fixed lexicographic ties and gains recomputed from the objective, the trajectory peaks at thirteen fiftieths, while the partition into two consecutive triples scores three tenths. This example is separate from the printed initialization mismatch and does not execute author software.

supports Source: Finding community structure in very large networks · Locator: Section II, PDF p. 2, approximate optimization and Equation 4; curator reference calculation in research/discovery/cnm-boundaries.py

Scope #evaluation-scope

The demonstration uses the largest connected component of an August 2003 Amazon co-purchasing network after ignoring link direction. High modularity, an interpretable visualization and informal descriptions of product groups support a descriptive case study. They do not establish a universally correct community definition, recovery against comprehensive ground truth, or a general predictive-performance advantage. The exploratory community-size distribution is not adopted here as a universal law.

supports Source: Finding community structure in very large networks · Locator: Section III and Conclusions, PDF pp. 4–5, Figures 1–3 and Table I; Reference note 14, p. 6

⚠️ Curated Limitations & Negative Results

The record covers the 2004 CNM sparse greedy modularity algorithm and the explicitly scoped author documentation. It is not the 2008 Clauset–Moore–Newman hierarchical random-graph model or the full family of modularity-optimization methods.
The earlier Newman greedy method supplies algorithmic context, while the retained HAC-Q record concerns a related score used with hierarchical link-density estimates. Shared scores do not establish identical data structures, tie behavior or downstream representations.
A high objective value is not a biological, social or semantic truth certificate. The degree-product null term is an expected adjacency contribution, not necessarily a Bernoulli probability bounded by one.
The printed initialization discrepancy is scoped to the inspected arXiv v2. The journal PDF, earlier preprint, source archives and later library implementations were not compared; no author-code defect or experimental invalidity is asserted.
The author documentation snapshot has a 2005 footer and updates through 2009; these dates do not establish the revision of any uninspected code archive. Program-specific file-format requirements are not universal requirements of community-detection mathematics.
The original documented input is connected and simple, with a positive edge count needed by the modularity denominator. Weighted, directed, disconnected and signed variants require separate evidence and implementation conventions.
No author code, experimental data, model training or paid service was executed. Exact finite formula and reference-procedure checks are not benchmark replication or formal certification of every proof. The record remains DRAFT.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The algorithm constructs an agglomerative hierarchy of vertex groups. The target is a related clustering task, not an equivalent named algorithm or asserted superclass.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	Graph topology and a prescribed objective determine the groups rather than supervised class labels. This task relation preserves the algorithm/task distinction.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`clauset2004`	Finding community structure in very large networks Aaron Clauset, M. E. J. Newman, Cristopher Moore	primary paper full_text	ID: arxiv:cond-mat/0408187v2 sha256:a0f3adfe111b…
`cnm-docs`	Fast Modularity Community Structure Inference Algorithm Aaron Clauset	official documentation documentation	sha256:589febc76921…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T01:37:06Z

Updated: 2026-10-14T01:37:06Z

Source File: data/curated/CNMCommunityDetection.yaml