Home / Curated / Algorithms / Flake exact-flow community identification

Flake exact-flow community identification

Algorithms AIMech:FlakeExactFlowCommunity DRAFT

Aliases: EXACT-FLOW-COMMUNITY, Flake exact-flow community algorithm

A seeded web-graph grouping procedure that adds infinite-capacity source arcs to seed vertices, makes original hyperlink connections bidirectional with a common capacity, connects nonseed vertices to an artificial sink with unit capacity, and extracts source-reachable original vertices from the residual graph after maximum flow.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 677 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 20,0,0 lines, all read: prior source-deduplication logs and the Flake source lead, not either maintained concept. Semantic search covered 70 AIO and 318 native definitions; 64 AIO and 290 native rows match prior inspected context, and all six newly selected AIO and 28 native definitions were read. Eleven complete AIO node/edge/generated contexts were assessed, five verified unchanged and six newly read. The full EM record and previously inspected GN/Radicchi records provide native identity context. Both drafts were compared for a fixed-graph exact core versus a versioned crawl/reseed family. The maintained target is the2002 exact augmented-graph procedure, using the prose convention that only original graph edges are rescaled. The2000 theorem discussion is context with explicit limits, not an asserted universal exact-recovery guarantee. This core solves one supplied graph and is distinct from repeated crawl/reseed acquisition.

Claims & Grounded Evidence

6 Claims

Mechanism #augmentation-convention

The prose specifies three distinct arc classes: infinite source-to-seed arcs, bidirectional original-graph arcs of capacity k, and unit nonseed-to-sink arcs. This record follows that prose convention. Figure 2a instead prints an all-E rescaling loop after adding source arcs; a literal interpretation that also rescales those new arcs would remove seed forcing. The distinction concerns the inspected presentation, not an audited author implementation.

supports Source: Self-Organization and Identification of Web Communities · Locator: Augmenting the Web Graph, Figure 2a and its caption, printed p. 68 / PDF p. 3; curator calculation in research/discovery/flow-community-boundaries.py

Mechanism #cut-objective

For the simple undirected graph induced by the bidirectional original connections, a finite cut whose original-vertex source side C contains all seeds S has capacity k times the number of original edges crossing C plus the number of included nonseed vertices. The latter term comes from the unit sink arcs. Thus this is an augmented minimum-cut objective with seed constraints, not modularity maximization or a dendrogram construction.

supports Source: Self-Organization and Identification of Web Communities · Locator: Augmenting the Web Graph and Figure 2a, printed p. 68 / PDF p. 3; curator cut-capacity calculation in research/discovery/flow-community-boundaries.py

Limitation #seed-guarantee-boundary

The one-vertex cut-improvement argument applies to removable nonseed vertices and does not automatically certify a forced seed’s internal-over-external degree inequality. For a four-vertex star with its center forced as the sole seed and k = 1, the finite reference finds eight minimum cuts of value three, including the seed alone with zero internal and three external neighbors. Exact cut optimality therefore does not establish the stated community inequality for every supplied seed under arbitrary input choices.

supports Source: Self-Organization and Identification of Web Communities · Locator: Web Communities, printed p. 66 / PDF p. 1; exact-flow guarantee discussion and Figure 2a, printed p. 68 / PDF p. 3; curator calculation in research/discovery/flow-community-boundaries.py

Limitation #preselected-community-boundary

The earlier KDD paper’s source/sink degree conditions do not by themselves ensure recovery of any preselected qualifying community. In the finite reference, two four-cliques joined by one edge form a qualifying eight-vertex group with two edges to a third four-clique; source and sink internal degrees are three, exceeding that boundary of two. Yet the unique minimum source-side cut selects the first four-clique at cost one. This is a counterexample to the broad exact-recovery reading, not a failure of maximum-flow optimization.

supports Source: Efficient Identification of Web Communities · Locator: Section 3.1, Definitions 1–2 and Theorem 1, printed p. 152 / PDF p. 3; curator calculation in research/discovery/flow-community-boundaries.py

Scope #version-and-input-scope

The 2002 procedure operates on a supplied graph and positive seed set. Its guarantee discussion assumes access to the full Web graph, while experiments use the separate approximate crawling wrapper. The 2000 paper uses a non-strict internal-degree definition in Definition 1 and describes different practical boundary wiring; those versions must not be treated as identical executable procedures or unconditional claims about today’s Web.

supports Source: Efficient Identification of Web Communities · Locator: Sections 3.1–3.3, printed pp. 152–154 / PDF pp. 3–5
supports Source: Self-Organization and Identification of Web Communities · Locator: Figure 2 and exact-flow versus approximate-flow discussion, printed p. 68 / PDF p. 3

Limitation #evaluation-boundary

The inspected 2002 experiments evaluate approximate-flow crawling from three scientist seed pages, followed by link-score ranking and text-based characterization. They do not independently benchmark this exact core on the complete Web or prove universal semantic relevance, absence of bias or recovery of one uniquely correct community.

supports Source: Self-Organization and Identification of Web Communities · Locator: Experimental Results and Table 1 discussion, printed pp. 69–70 / PDF pp. 4–5

⚠️ Curated Limitations & Negative Results

The maintained scope is the 2002 prose augmentation and residual extraction. The all-E pseudocode ambiguity is retained; no author software was inspected to resolve it.
Constructed cut calculations use explicit simple undirected graph conventions and exact finite enumeration. They are not author-code conformance tests, historical web crawls or universal theorem certification.
The record separates optimality of an augmented cut from seed quality, complete input coverage, unique community identity and semantic interpretation.
Positive seeds are supplied by the caller. The algorithm does not learn a general classifier or perform statistical expectation maximization.
Both complete primary papers and their displayed methods were read. Historical datasets, implementation details beyond those papers and modern crawling services remain uninspected. No training, paid services or benchmark replication was performed; DRAFT remains.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:Clustering` Clustering	related_match	The procedure groups graph vertices using link topology and supplied positive seeds. This relates the named algorithm to the general clustering task without asserting equivalence, hierarchy or purely unsupervised operation.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`flake2002`	Self-Organization and Identification of Web Communities Gary William Flake, Steve Lawrence, C. Lee Giles, Frans M. Coetzee	primary paper full_text	ID: doi:10.1109/2.989932 sha256:104f1461e300…
`flake2000`	Efficient Identification of Web Communities Gary William Flake, Steve Lawrence, C. Lee Giles	primary paper full_text	ID: doi:10.1145/347090.347121 sha256:016ffe67913e…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T02:24:50Z

Updated: 2026-10-14T02:24:50Z

Source File: data/curated/FlakeExactFlowCommunity.yaml