Below is a small network. Every node starts in its own community, so modularity is low. Press Greedy step and the algorithm moves each node into the neighboring community that raises modularity the most — exactly the move at the heart of the Louvain method.
<p class="hint">Every node starts in its <b>own</b> community, so modularity is low.
Press <b>Greedy step</b>: each node hops into the neighboring community that raises
modularity the most — the move at the heart of the Louvain method. Watch the colors
merge and the score climb.</p>
<svg id="net" viewBox="0 0 360 240" class="net"></svg>
<div class="score">Modularity Q = <span id="q">0.000</span>
· communities: <span id="nc">12</span></div>
<div class="btns">
<button id="step" type="button">Greedy step</button>
<button id="run" type="button">Run to convergence</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 .7rem; line-height: 1.45; }
.net { width: 100%; height: auto; background: #f4f7fa; border: 1px solid #d6e0e8;
border-radius: 10px; display: block; }
.net line { stroke: #b9c4ce; stroke-width: 1.3; }
.net circle { stroke: #2b3a47; stroke-width: 1.5; transition: fill .35s ease; cursor: default; }
.net text { font: 700 9px ui-monospace, monospace; fill: #16242f; pointer-events: none; }
.score { font-size: 1.05rem; font-weight: 700; margin: .6rem 0; color: #1d3557; }
.score #q { font-family: ui-monospace, monospace; }
.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; }
// Community detection by GREEDY MODULARITY MAXIMIZATION (the Louvain local-move).
// Modularity Q = (1/2m) * sum_ij [ A_ij - k_i*k_j/(2m) ] * delta(c_i, c_j).
// Maximizing Q over all partitions is NP-hard (Brandes et al., 2008), so we move
// each node, one at a time, into the neighbor community giving the biggest Q gain.
// A network with three planted communities (0-3, 4-7, 8-11), dense inside, sparse between.
const POS = [
[55,55],[95,40],[60,95],[100,90], // group A
[185,45],[230,40],[180,95],[225,95], // group B
[120,180],[170,175],[140,210],[195,205] // group C
];
const EDGES = [
[0,1],[0,2],[1,2],[1,3],[2,3],[0,3], // A internal
[4,5],[4,6],[5,6],[5,7],[6,7],[4,7], // B internal
[8,9],[8,10],[9,10],[9,11],[10,11],[8,11], // C internal
[3,4],[7,9] // two weak bridges between groups
];
const N = POS.length;
const PALETTE = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#9b5de5','#f08a3c',
'#06a77d','#d62246','#5e60ce','#ff7b00','#118ab2','#8338ec'];
// adjacency + degrees
const adj = Array.from({length:N},()=>[]);
const deg = new Array(N).fill(0);
EDGES.forEach(([a,b])=>{ adj[a].push(b); adj[b].push(a); deg[a]++; deg[b]++; });
const m = EDGES.length; // number of edges
const twoM = 2*m;
let comm; // comm[i] = community id of node i
function reset(){ comm = POS.map((_,i)=>i); draw(); }
// weight of edges between node i and a given community
function edgesToComm(i,c){ let w=0; adj[i].forEach(j=>{ if(comm[j]===c) w++; }); return w; }
// total degree of all nodes currently in community c
function commDegree(c){ let s=0; for(let j=0;j<N;j++) if(comm[j]===c) s+=deg[j]; return s; }
function modularity(){
let q=0;
for(let i=0;i<N;i++) for(let j=0;j<N;j++){
if(comm[i]!==comm[j]) continue;
const aij = adj[i].includes(j) ? 1 : 0;
q += aij - (deg[i]*deg[j])/twoM;
}
return q/twoM;
}
// One greedy pass: try to move each node into the neighbor community with max Q gain.
function greedyPass(){
let moved=false;
for(let i=0;i<N;i++){
const cur=comm[i];
const sumIn = deg[i]; // k_i
// candidate communities = those of neighbours (plus staying put)
const cand=new Set([cur]); adj[i].forEach(j=>cand.add(comm[j]));
let bestC=cur, bestGain=0;
// remove i from its community for fair comparison
comm[i]=-1;
for(const c of cand){
// gain from putting i into c: edgesToComm - k_i*Sigma_tot/(2m)
const gain = edgesToComm(i,c) - sumIn*commDegree(c)/twoM;
if(gain>bestGain+1e-12){ bestGain=gain; bestC=c; }
}
comm[i]=bestC;
if(bestC!==cur) moved=true;
}
return moved;
}
function draw(){
const svg=document.getElementById('net'); svg.innerHTML='';
const NS='http://www.w3.org/2000/svg';
EDGES.forEach(([a,b])=>{ const l=document.createElementNS(NS,'line');
l.setAttribute('x1',POS[a][0]); l.setAttribute('y1',POS[a][1]);
l.setAttribute('x2',POS[b][0]); l.setAttribute('y2',POS[b][1]); svg.appendChild(l); });
POS.forEach((p,i)=>{ const c=document.createElementNS(NS,'circle');
c.setAttribute('cx',p[0]); c.setAttribute('cy',p[1]); c.setAttribute('r',11);
c.setAttribute('fill',PALETTE[comm[i]%PALETTE.length]); svg.appendChild(c);
const t=document.createElementNS(NS,'text'); t.setAttribute('x',p[0]);
t.setAttribute('y',p[1]+3.2); t.setAttribute('text-anchor','middle'); t.textContent=i; svg.appendChild(t); });
document.getElementById('q').textContent = modularity().toFixed(3);
document.getElementById('nc').textContent = new Set(comm).size;
}
document.getElementById('step').addEventListener('click',()=>{ greedyPass(); draw();
console.log('Q =', modularity().toFixed(4), '| communities =', new Set(comm).size); });
document.getElementById('run').addEventListener('click',()=>{ let guard=0;
while(greedyPass() && guard++<50){} draw();
console.log('Converged: Q =', modularity().toFixed(4), '| communities =', new Set(comm).size); });
document.getElementById('reset').addEventListener('click',reset);
reset();
Comments
Loading comments...