Introduction

A graph is one of the simplest objects in mathematics: some dots (vertices) joined by some lines (edges). Friends on a social network, cities on a road map, neurons in a brain — all graphs. But how do you measure the shape of one? Is it one tight blob or two loosely linked clusters? Where would it break in two?

Spectral graph theory answers these questions with a surprising move: it turns the graph into a matrix and looks at that matrix's eigenvalues — its "spectrum." The standard choice is the Laplacian matrix L = D − A, where DD counts each vertex's connections and AA records who is linked to whom.

From this pile of numbers fall out facts that look nothing like algebra: how many separate pieces the graph has, how fast a rumor (or a random walk) spreads through it, and — most beautifully — a recipe for cutting it into two natural communities. The geometry of a network becomes arithmetic.

Split a Network

Below is a small network with two loosely connected groups. Press Find communities and the demo builds the Laplacian, computes its second-smallest eigenvalue's eigenvector — the famous Fiedler vector — and colors each vertex by the sign of its entry. Watch the two communities appear.

<p class="hint">This network has two loosely connected groups. The computer builds the
<b>Laplacian</b> matrix, finds the <b>Fiedler vector</b> (the eigenvector of the second-smallest
eigenvalue), and colors each vertex by the <b>sign</b> of its entry. Nobody told it where the
groups are.</p>
<svg id="net" viewBox="0 0 360 240" aria-label="network"></svg>
<div class="status" id="status">Press "Find communities".</div>
<div class="readout" id="readout"></div>
<div class="btns">
  <button id="find" type="button">Find communities</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#net { width: 100%; max-width: 360px; height: auto; display: block;
       background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px; }
.edge { stroke: #adb1b8; stroke-width: 1.4; }
.node { stroke: #1d3557; stroke-width: 1.5; fill: #c9ccd1; transition: fill .35s; }
.node.a { fill: #2a9d8f; }
.node.b { fill: #e76f51; }
.label { font: 600 11px ui-monospace, monospace; fill: #1d3557; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0 .2rem; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.readout { font: 500 .82rem ui-monospace, monospace; color: #345; white-space: pre-wrap;
           margin: 0 0 .5rem; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Spectral graph theory: read a network through the eigenvalues of its Laplacian L = D - A.
// The Fiedler vector (eigenvector of the 2nd-smallest eigenvalue) splits the graph by sign.
// Eigenvector via inverse-free shifted power iteration on M = c*I - L (deflated against the
// all-ones vector, which is L’s eigenvector for eigenvalue 0). The top eigenvector of M that
// is orthogonal to ones is exactly the Fiedler vector. This is polynomial-time; the balanced
// cut it approximates is NP-hard (Fiedler 1973; Cheeger’s inequality).
const N = 8;
const POS = [[60,55],[45,120],[80,185],[120,110],   // group 0 (left)
             [240,55],[295,120],[260,185],[210,120]]; // group 1 (right)
const EDGES = [
  [0,1],[0,3],[1,2],[1,3],[2,3],          // dense inside left
  [4,5],[4,7],[5,6],[5,7],[6,7],          // dense inside right
  [3,7]                                   // one weak bridge between groups
];
const A = Array.from({length:N},()=>Array(N).fill(0));
EDGES.forEach(([i,j])=>{ A[i][j]=1; A[j][i]=1; });
const deg = A.map(r=>r.reduce((s,x)=>s+x,0));

// L = D - A ; M = c*I - L so M’s top eigenpair = L’s smallest eigenpair.
const c = 2*Math.max(...deg) + 1;
const M = Array.from({length:N},(_,i)=>Array.from({length:N},(_,j)=>
  (i===j ? c-deg[i] : A[i][j])));

const ones = Array(N).fill(1/Math.sqrt(N));
function dot(u,v){ let s=0; for(let i=0;i<N;i++)s+=u[i]*v[i]; return s; }
function deflate(v){ const p=dot(v,ones); for(let i=0;i<N;i++)v[i]-=p*ones[i]; } // remove ones component
function norm(v){ const n=Math.sqrt(dot(v,v))||1; for(let i=0;i<N;i++)v[i]/=n; return n; }
function matvec(m,v){ return m.map(row=>{ let s=0; for(let j=0;j<N;j++)s+=row[j]*v[j]; return s; }); }

function fiedler(){
  // random start, orthogonal to ones -> power iteration on M converges to Fiedler vector.
  let v = Array.from({length:N},()=>Math.random()-0.5);
  deflate(v); norm(v);
  let lambdaM=0;
  for(let it=0; it<400; it++){
    let w = matvec(M,v);
    deflate(w);                 // keep orthogonal to the trivial eigenvector
    lambdaM = norm(w);
    if(dot(w,v)<0){ for(let i=0;i<N;i++)w[i]=-w[i]; } // stabilize sign for convergence test
    v = w;
  }
  const fiedlerEig = c - lambdaM; // convert M’s eigenvalue back to L’s (the Fiedler value)
  return { vec:v, val:fiedlerEig };
}

function draw(groups){
  const svg=document.getElementById('net'); svg.innerHTML='';
  const NS='http://www.w3.org/2000/svg';
  EDGES.forEach(([i,j])=>{ const l=document.createElementNS(NS,'line');
    l.setAttribute('class','edge'); l.setAttribute('x1',POS[i][0]); l.setAttribute('y1',POS[i][1]);
    l.setAttribute('x2',POS[j][0]); l.setAttribute('y2',POS[j][1]); svg.appendChild(l); });
  for(let i=0;i<N;i++){ const g = groups?(groups[i]>=0?'a':'b'):'';
    const cN=document.createElementNS(NS,'circle'); cN.setAttribute('class','node '+g);
    cN.setAttribute('cx',POS[i][0]); cN.setAttribute('cy',POS[i][1]); cN.setAttribute('r',14); svg.appendChild(cN);
    const t=document.createElementNS(NS,'text'); t.setAttribute('class','label');
    t.setAttribute('x',POS[i][0]); t.setAttribute('y',POS[i][1]+4); t.setAttribute('text-anchor','middle');
    t.textContent=i; svg.appendChild(t); }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function find(){
  const {vec,val}=fiedler();
  const groups=vec.map(x=>x>=0?1:-1);
  draw(groups);
  const A=[],B=[]; groups.forEach((g,i)=>(g>=0?A:B).push(i));
  setStatus(`Two communities found.`,'ok');
  document.getElementById('readout').textContent =
    fmt(`Fiedler value λ₂ ≈ %val%
Group A (green): {%A%}
Group B (orange): {%B%}`, { val: val.toFixed(3), A: A.join(', '), B: B.join(', ') });
  console.log(`Fiedler vector:`, vec.map(x=>x.toFixed(3)).join(' '), '| λ2 =', val.toFixed(4));
}
document.getElementById('find').addEventListener('click',find);
document.getElementById('reset').addEventListener('click',()=>{ draw(null);
  setStatus(`Press "Find communities".`,''); document.getElementById('readout').textContent=''; });
draw(null);
Result
Console

The magic is that nobody told the algorithm where the groups are. It only saw who-is-linked-to-whom, formed a matrix, and the second eigenvector sorted the vertices into two camps. The corresponding eigenvalue — the algebraic connectivity, or Fiedler value — even measures how separable the graph is: near zero means it almost falls apart; large means it is tightly knit.

The Real Complexity

So how hard is any of this?

  • Computing the spectrum is easy. Finding all eigenvalues and eigenvectors of an n×nn \times n matrix runs in polynomial time — roughly O(n3)O(n^{3}), and far faster for sparse graphs where you only want the smallest few. So the Fiedler vector itself is cheap.
  • The cut it approximates is not. What we actually want is the best way to split a graph into two balanced halves cutting as few edges as possible. That balanced minimum cut (and its cousin, sparsest cut) is NP-hard, a relative of the problems behind P vs NP.
  • The spectrum is a relaxation. Mathematician Miroslav Fiedler showed in 1973 that the second-smallest Laplacian eigenvalue lower-bounds how connected a graph is, and Cheeger's inequality pins the true best cut between two functions of that eigenvalue. So the easy eigenvector gives a provably good approximation to the hard cut.
  • One subtlety: isomorphism. Two graphs with the same spectrum need not be the same graph ("isospectral" graphs exist), so the spectrum alone can't always tell graphs apart — that is the open-flavored world of graph isomorphism.

The pattern is classic: an exact answer is intractable, but a continuous relaxation — here, real eigenvalues instead of yes/no cuts — is computable and lands close. Spectral methods turn a combinatorial cliff into a smooth, solvable hill.

Where It Matters

Once you can read a network through its spectrum, the same trick shows up everywhere:

  • Spectral clustering: the Fiedler-vector idea, extended to several eigenvectors, groups data points, communities, or pixels — it is one of the strongest clustering methods known.
  • Image segmentation: treating pixels as a graph, the "normalized cut" splits a photo into objects using exactly these eigenvectors.
  • Search and ranking: PageRank is, at heart, the dominant eigenvector of a graph of web links.
  • Resilience and mixing: the second eigenvalue tells engineers how robust a power grid or communication network is, and how fast a random walk — or an epidemic — mixes through it.
  • Chip and mesh layout: spectral partitioning splits huge circuits and finite-element meshes across processors with few cross-cuts.

Wherever there is structure to find in a network, eigenvalues are usually the fastest honest way to find it.

Conclusion

Spectral graph theory is a small miracle of translation: feed in a graph's connections, get back a list of numbers, and those numbers describe the network's shape — how many pieces, how tightly knit, where it wants to split. The Fiedler vector finds communities nobody labeled, and Cheeger's inequality promises the cut it suggests is close to the best possible.

It is also a lesson about hard problems. The exact balanced cut sits with the NP-hard crowd, but its spectral relaxation is cheap and provably good. When a discrete problem refuses to yield, sometimes the right move is to let it go continuous — and read the answer off the eigenvalues.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/spectral-graph/Content licensed under CC BY-NC 4.0.