Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 36 · Spectral Graph Theory

The Laplacian and the Fiedler Vector

Learn the graph Laplacian L = D - A, why its eigenvalues count components, how algebraic connectivity measures robustness, and bisect graphs with the Fiedler vector.

The adjacency matrix tells you who is connected to whom. The Laplacian tells you how a graph behaves: how heat flows across it, how well connected it is, and where its natural cut lies. It is the single most important matrix in spectral graph theory, and it is built from the two matrices you already know.

Definition and the energy form

Let A be the adjacency matrix and D the diagonal matrix of degrees. The graph Laplacian is

L = D − A.

So L[i][i] = degree(i), L[i][j] = −1 if i and j are adjacent, and 0 otherwise. Each row sums to zero, so the all-ones vector 1 satisfies L·1 = 0.

The deeper meaning shows in the quadratic form. For a vector x that assigns a number x_i to each vertex:

xᵀ L x = Σ over edges (i, j) of (x_i − x_j)².

This sum is large when neighbors have very different values and zero when x is constant across every connected piece. It is the "energy" of the labeling x. Because it is a sum of squares, L is positive semidefinite: all its eigenvalues are real and non-negative, so we sort them 0 = λ1 ≤ λ2 ≤ … ≤ λn.

Python Build L and verify the energy identity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Eigenvalue 0 counts components

The eigenvalue 0 has eigenvectors x with xᵀLx = 0, which forces x_i = x_j across every edge, so x is constant on each connected component. Hence:

The multiplicity of the eigenvalue 0 equals the number of connected components.

This is an exact algebraic test for connectivity that you can compute without any graph search. It also hints at a robust version: if λ2 is tiny but not zero, the graph is almost disconnected.

Algebraic connectivity

The second smallest eigenvalue λ2 is the algebraic connectivity (Fiedler value). It satisfies:

  • λ2 > 0 iff the graph is connected.
  • λ2 never decreases when you add edges. Complete graph K_n has λ2 = n, the maximum.
  • λ2 ≤ vertex connectivity for non-complete graphs, so a bigger λ2 means harder to disconnect.
  • Paths and long cycles have small λ2 (about π²/n² for a path); expanders have a large λ2.
flowchart LR
    P["Path, n=8: 0.15"] --> Q["Cycle, n=8: 0.59"]
    Q --> R["Star, n=8: 1"]
    R --> S["Complete, n=8: 8"]

Algebraic connectivity of four 8-vertex graphs: higher means better connected and harder to split.

Python Algebraic connectivity of different graphs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Fiedler vector: finding the natural cut

The eigenvector belonging to λ2 is the Fiedler vector. Among all vectors that are orthogonal to the constant vector 1 and have unit length, it minimizes the energy xᵀLx (this is the Rayleigh-Ritz principle). A vector with low energy changes slowly across edges, so it assigns similar values to well-connected vertices and a jump only where few edges connect two regions. That means the signs of the Fiedler vector split the graph into two clusters with few edges between them.

Spectral bisection is the heart of spectral partitioning: compute the Fiedler vector, then split the vertices by sign (or by the median for a balanced split). The theoretical justification is Cheeger's inequality, which sandwiches λ2 between the best possible cut ratio h(G) (edges cut divided by the smaller side's size):

h(G)² / (2·d_max) ≤ λ2 ≤ 2·h(G).

A small λ2 means a bottleneck exists, and a bottleneck means a small λ2.

Python Spectral bisection of a barbell-shaped network

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Fiedler vector finds the bridge with one eigenvector computation, and the Cheeger bounds hold. Brute-force expansion costs 2^n, which is why spectral methods are attractive: they replace an exponential search with a linear-algebra routine.

Normalized Laplacian and what comes next

The normalized Laplacian L_sym = I − D^(−1/2) A D^(−1/2) has eigenvalues in [0, 2] and treats vertices of different degrees fairly; its second eigenvector relates to the normalized cut. A related matrix, the random-walk Laplacian I − D^(−1) A, links the spectrum to how fast a random walker mixes across the graph. We use both in spectral clustering and random walks.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the Laplacian of a graph?

    The Laplacian is the degree matrix minus the adjacency matrix.
  2. 2. A graph has Laplacian eigenvalue 0 with multiplicity 3. What does that mean?

    The multiplicity of the zero eigenvalue equals the number of connected components.
  3. 3. What does the quadratic form xᵀ L x compute?

    xᵀLx = Σ over edges (x_i − x_j)², which is why L is positive semidefinite.
  4. 4. How do you partition a graph into two clusters with the Fiedler vector?

    Entries of the eigenvector for λ2 change little inside well-connected regions, so grouping by sign (or by median) yields a low-cut bisection.

Summary

  • The Laplacian L = D − A has energy form xᵀLx = Σ (x_i − x_j)² and is positive semidefinite.
  • The multiplicity of eigenvalue 0 equals the number of connected components.
  • The algebraic connectivity λ2 is positive iff the graph is connected and grows with robustness.
  • The Fiedler vector bisects a graph along its natural bottleneck, and Cheeger's inequality ties λ2 to the best cut.

Next: Spectral Clustering and Random Walks