DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

RatioCut and normalized cut for a finite weighted graph

Definition

Let $n \geq 1$ , $V = {1, \dots, n}$ , and let $W = (w_{i j}) \in R^{n \times n}$ be symmetric, entrywise nonnegative, and zero-diagonal. Define $d_{i} = \sum_{j} w_{i j}$ , $D = diag (d_{1}, \dots, d_{n})$ , $L = D - W$ , and $V_{+} = {i : d_{i} > 0}$ . For $A \subseteq V$ , put $A^{c} = V ∖ A$ , $cut (A, A^{c}) = \sum_{i \in A, j \in A^{c}} w_{i j}$ , and $vol (A) = \sum_{i \in A} d_{i}$ . For a partition $A = (A_{1}, \dots, A_{k})$ of $V$ into pairwise disjoint nonempty sets, define $RatioCut (A) = \sum_{r = 1}^{k} \frac{cut (A_{r}, A_{r}^{c})}{∣ A_{r} ∣} .$ For a partition of $V_{+}$ into pairwise disjoint nonempty sets, each of positive volume, define $Ncut (A) = \sum_{r = 1}^{k} \frac{cut (A_{r}, A_{r}^{c})}{vol (A_{r})} .$ For these partitions, the RatioCut indicator column is $h_{r} = 1_{A_{r}} / \sqrt{∣ A_{r} ∣}$ , and the Ncut indicator column is $h_{r} = 1_{A_{r}} / \sqrt{vol (A_{r})}$ , extended by zero on isolated vertices.

Definition references

Finite weighted graph Laplacian

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Depends on

Finite weighted graph Laplacian

Used by

Dependency tree · one level

1 result within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007 (standard reference, not scraped)
Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013 (standard reference, not scraped)