Home / Curated / Algorithms / Definition-filtered Girvan–Newman community detection

Definition-filtered Girvan–Newman community detection

Algorithms AIMech:DefinitionFilteredGirvanNewman DRAFT

Aliases: self-contained Girvan–Newman algorithm, strong/weak community validation for Girvan–Newman

A Girvan–Newman variant that retains a branching event in the reported hierarchy only when at least two resulting groups satisfy a selected strong or weak community definition evaluated against the original graph, while continuing betweenness-based edge deletion within the resulting subgraphs.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 675 native IDs, names, aliases and scoped synonyms before either cohort write; no normalized identity match. Ignored- and hidden-inclusive searches of all three checkouts returned 16,0,0 lines. All sixteen public matches were read: source citations, previously pending reading notes, query logs and the existing Radicchi source lead, not either maintained identity. Semantic assessment covered 64 AIO and 290 native definitions: 46 AIO and 268 native rows match prior inspected context; all 18 newly selected AIO and 22 native definitions were read. Sixteen complete AIO node/edge/generated contexts were verified unchanged and mapping rationales reassessed. Both drafts were compared for inherited betweenness plus definition filtering versus local cycle-score deletion. Retain the source’s self-contained GN variant as an explicit strong/weak community-validation algorithm. The edge selector is inherited from Girvan–Newman; the new maintained mechanism validates branch retention against original adjacency and requires at least two qualifying children. It is distinct from unfiltered GN, modularity agglomeration and the cycle-score replacement in this cohort.

Claims & Grounded Evidence

6 Claims

Mechanism #strong-weak-definitions

A strong community requires every member to have strictly more neighbors inside the group than outside it. A weak community requires the sum of members’ internal degrees to exceed their total external degree, equivalently twice the number of internal edges exceeding the cut-edge count for a simple undirected graph. Strong implies weak; the converse need not hold. These are selected definitions rather than a unique universal meaning of community.

supports Source: Defining and identifying communities in networks · Locator: Section II, PDF p. 3, Equations 1–2 and alternative-definition discussion

Mechanism #original-adjacency

Community validation always uses the full original adjacency matrix, not the graph remaining after edge removal. In a constructed four-vertex path, splitting the middle edge gives two pairs that satisfy the original weak criterion but fail the strong criterion; incorrectly testing the deleted graph would make both pairs strong.

supports Source: Defining and identifying communities in networks · Locator: Section III, PDF p. 4, paragraph after the five-step algorithm; curator calculation in research/discovery/radicchi-boundaries.py

Mechanism #branch-retention

After high-betweenness deletions separate a subgraph, the procedure draws the corresponding branching only if at least two resulting groups satisfy the selected definition. A single qualifying large group is insufficient. Rejecting a displayed branch does not stop processing: the source continues within all subgraphs until no edges remain. The rule does not assert that every child qualifies when there are more than two children.

supports Source: Defining and identifying communities in networks · Locator: Section III, PDF pp. 3–4, random-split motivation and steps 2–5; curator calculation in research/discovery/radicchi-boundaries.py

Scope #hierarchy-scope

The validation criterion filters the hierarchy generated by an edge-removal procedure; it neither enumerates every subgraph meeting the definition nor guarantees a unique optimal flat partition. The same definition test can accompany a different edge selector, including the paper’s modified cycle-score algorithm, without making those selectors equivalent.

supports Source: Defining and identifying communities in networks · Locator: Sections III–IV, PDF pp. 4–5; Conclusions, p. 6

Scope #evaluation-protocol

The synthetic evaluation uses 128 vertices in four groups with independent within- and between-group edge probabilities adjusted to keep expected degree sixteen. Its strict success condition requires all four groups to be recovered exactly and not subdivided further. The fraction of incorrectly assigned nodes is a different, softer metric; a poor strict-success rate need not imply many misclassified vertices.

supports Source: Defining and identifying communities in networks · Locator: Section III, PDF p. 4; Figure 2 legend, p. 8, plot p. 10

Limitation #domain-and-interpretation

The inspected tests concern unweighted undirected graph topology. Satisfying a chosen degree inequality is not independent proof of a social, biological or causal grouping. The source acknowledges alternative community definitions and subjective validation for real collaboration data; directed, weighted and exceptional-input conventions require separate evidence.

supports Source: Defining and identifying communities in networks · Locator: Section II and footnote 2, PDF p. 3; Sections V–VI, pp. 6–7

⚠️ Curated Limitations & Negative Results

The scope is the self-contained GN procedure in arXiv cond-mat/0309488v2. It adds original-adjacency definition filtering to the previously maintained Girvan–Newman selector; it is not the separate local edge-clustering selector.
The source’s at-least-two-child rule is retained literally. It is not strengthened to requiring every child, and an unretained branch does not terminate edge deletion.
The finite four-path example checks definition and adjacency semantics; it does not execute the author software, reproduce a benchmark or certify a universal recovery property.
The record makes no numerical speed claim. The paper’s Figure 5 times concern full-tree construction without community validation and cannot automatically be assigned to this filtered pipeline.
All primary text, equations and figures were inspected, but journal-version differences, author software, supporting community lists and data were not audited. No training or benchmark replication was performed; DRAFT remains.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The procedure filters a graph-grouping hierarchy, relating this algorithm to the hierarchical clustering task without asserting equivalence or an algorithm superclass.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	Groups and acceptance tests use graph topology without training labels; external labels in evaluation do not turn this into supervised classification.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`radicchi2004`	Defining and identifying communities in networks Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, Domenico Parisi	primary paper full_text	ID: arxiv:cond-mat/0309488v2 sha256:02467f9e119b…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T02:08:27Z

Updated: 2026-10-14T02:08:27Z

Source File: data/curated/DefinitionFilteredGirvanNewman.yaml