Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 36 ยท Spectral Graph Theory

Spectral Clustering and Random Walks

Cluster a graph with Laplacian eigenvectors and k-means, see how random walks converge to degree-proportional distributions, and compute PageRank by power iteration.

In the previous lesson one eigenvector split a graph in two. What if there are three, five or twenty communities? And what does the same matrix say about a walker who moves randomly from vertex to vertex? This lesson answers both questions and shows that they are two sides of the same coin: clustering finds regions where a random walk gets trapped, and PageRank asks where a random walker spends its time.

Spectral clustering

The recipe, in four steps, generalizes spectral bisection to k clusters:

  1. Build the (normalized) Laplacian L_sym = I โˆ’ D^(โˆ’1/2) A D^(โˆ’1/2).
  2. Compute the k eigenvectors for the k smallest eigenvalues and stack them as columns of an n ร— k matrix U. Each vertex now corresponds to a row of U, a point in k dimensions.
  3. Normalize each row to unit length (for the normalized version).
  4. Run k-means on the rows. Vertices in the same community land close together.

Why does it work? A graph with k perfectly disconnected communities has k zero eigenvalues, and their eigenvectors are constant on each community, so rows of U take exactly k distinct values. If the communities are only loosely joined, the eigenvectors are perturbed slightly and the rows form k tight clouds. The eigengap ฮป_(k+1) โˆ’ ฮป_k tells you how clear the structure is, and a large gap after the k-th eigenvalue suggests k clusters.

Spectral clustering pipeline

Laplacian Normalized L from the graph
k eigenvectors Smallest eigenvalues
Embed One point per vertex
k-means Group the points

Graph in, labels out

1 / 2
Python Spectral clustering from scratch on a planted-partition graph

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 printed eigenvalues show a gap after the third: that is the hint to pick k = 3. The graph itself is random but seeded, so the result is reproducible.

Random walks on graphs

A random walk starts at a vertex and repeatedly moves to a uniformly chosen neighbor. Its transition matrix is P = D^(โˆ’1) A: P[i][j] = 1/deg(i) when i ~ j. Each row sums to 1 (a stochastic matrix). If p_t is the row vector of probabilities at time t, then p_(t+1) = p_t P, so p_t = p_0 P^t.

Two classical facts for a connected, non-bipartite undirected graph:

  • The walk converges to the stationary distribution ฯ€(i) = deg(i) / (2|E|). High-degree vertices are visited more often. (Bipartite graphs oscillate between sides and never converge; a lazy walk that stays put with probability 1/2 fixes that.)
  • The speed of convergence is controlled by the spectral gap: the eigenvalues of P are 1 = ฮผ1 > ฮผ2 โ‰ฅ โ€ฆ โ‰ฅ ฮผn โ‰ฅ โˆ’1, and the distance to stationarity shrinks like ฮผ2^t. A bottleneck (small Laplacian ฮป2) means ฮผ2 is near 1 and the walk mixes slowly, which is why random walkers stay trapped inside communities.
Python A random walk converges to degree / 2m

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.

PageRank

For the web, links are directed, so no stationary distribution proportional to degree exists. PageRank defines importance as the stationary distribution of a random surfer who follows a random out-link with probability d (the damping factor, typically 0.85) and teleports to a uniformly random page with probability 1 โˆ’ d. Teleporting makes the chain irreducible and aperiodic, so the answer always exists and is unique:

r = d ยท Mแต€ r + (1 โˆ’ d)/n ยท 1, where M[i][j] = 1/outdeg(i) for each link i โ†’ j.

Pages with no out-links ("dangling nodes") are treated as linking to every page. We compute r by power iteration: start from the uniform vector and apply the update until it stops changing. Each iteration is a sparse matrix-vector product, which is why PageRank scales to billions of pages.

Python PageRank by power iteration, checked against the eigenvector

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 result sums to 1 and ranks home highest, since most pages link to it. The page orphan, which nobody links to, still gets the teleport mass (1 โˆ’ d)/n plus its share from dangling nodes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In spectral clustering, what are the points that k-means groups?

    Each vertex is embedded as its row in the n ร— k matrix of eigenvectors, and k-means clusters those rows.
  2. 2. What is the stationary distribution of a random walk on a connected, non-bipartite undirected graph?

    ฯ€(i) = deg(i) / (2|E|), so higher-degree vertices are visited more often in the long run.
  3. 3. Why does PageRank include teleportation?

    Teleporting to a random page with probability 1 โˆ’ d connects every page to every other page, which guarantees a unique stationary distribution.
  4. 4. A large eigengap after the k-th smallest Laplacian eigenvalue suggests

    k near-zero eigenvalues followed by a gap indicates k nearly disconnected communities.

Summary

  • Spectral clustering embeds vertices with the k smallest eigenvectors of the normalized Laplacian and groups them with k-means; the eigengap suggests k.
  • A random walk has transition matrix P = D^(โˆ’1) A and converges to deg(i)/(2|E|) on connected non-bipartite graphs.
  • The spectral gap controls mixing speed; bottlenecks trap walkers inside communities.
  • PageRank is the stationary distribution of a random surfer with teleportation, computed by power iteration.

Next: Centrality Measures