Skip to content

Instantly share code, notes, and snippets.

@lucashmorais

lucashmorais/labelprop.html

Created November 18, 2025 16:09
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lucashmorais/87b5b78f29e0c42fa1b119f8f4bf57da to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lucashmorais/87b5b78f29e0c42fa1b119f8f4bf57da to your computer and use it in GitHub Desktop.
Download ZIP
Raw
labelprop.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Label Propagation Algorithm Animation</title>
<style>
:root {
--bg-color: #1a1a1a;
--panel-bg: #2d2d2d;
--text-color: #f0f0f0;
--accent: #4caf50;
--border: #444;
}
body {
margin: 0;
padding: 0;
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
background-color: var(--bg-color);
color: var(--text-color);
overflow: hidden;
display: flex;
flex-direction: column;
height: 100vh;
}
header {
padding: 1rem;
background-color: var(--panel-bg);
border-bottom: 1px solid var(--border);
display: flex;
justify-content: space-between;
align-items: center;
z-index: 10;
box-shadow: 0 2px 10px rgba(0,0,0,0.3);
}
h1 { margin: 0; font-size: 1.2rem; }
.controls {
display: flex;
gap: 10px;
align-items: center;
}
button {
background-color: var(--border);
color: white;
border: none;
padding: 8px 16px;
cursor: pointer;
border-radius: 4px;
font-weight: bold;
transition: background 0.2s;
}
button:hover { background-color: #555; }
button.primary { background-color: var(--accent); }
button.primary:hover { background-color: #43a047; }
button:disabled { opacity: 0.5; cursor: not-allowed; }
.stats {
font-family: monospace;
font-size: 0.9rem;
color: #aaa;
margin-left: 20px;
}
#canvas-container {
flex-grow: 1;
position: relative;
width: 100%;
height: 100%;
}
canvas {
display: block;
width: 100%;
height: 100%;
}
.legend {
position: absolute;
bottom: 20px;
left: 20px;
background: rgba(0, 0, 0, 0.7);
padding: 10px;
border-radius: 4px;
font-size: 0.85rem;
pointer-events: none;
}
</style>
</head>
<body>
<header>
<div style="display:flex; align-items:center;">
<h1>Label Propagation</h1>
<div class="stats">
Iteration: <span id="iter-count">0</span> |
Communities: <span id="comm-count">0</span> |
Status: <span id="status">Idle</span>
</div>
</div>
<div class="controls">
<button id="btn-reset">New Graph</button>
<button id="btn-step">Step</button>
<button id="btn-run" class="primary">Run Animation</button>
</div>
</header>
<div id="canvas-container">
<canvas id="graphCanvas"></canvas>
<div class="legend">
Nodes adopt the label (color)<br>
shared by the majority of their neighbors.<br>
Tie? Random choice.
</div>
</div>
<script>
/* --- CONFIGURATION --- */
const CONFIG = {
nodeCount: 150,
clusterCount: 5, // We artificially create clusters to make the algo interesting
connectionRadius: 80,
nodeRadius: 6,
animationSpeed: 200, // ms between frames
};
/* --- STATE --- */
const canvas = document.getElementById('graphCanvas');
const ctx = canvas.getContext('2d');
let width, height;
let nodes = [];
let edges = [];
let iteration = 0;
let isRunning = false;
let timer = null;
// Color palette cache
const colorCache = {};
/* --- INITIALIZATION --- */
function resize() {
width = canvas.width = canvas.parentElement.clientWidth;
height = canvas.height = canvas.parentElement.clientHeight;
if (nodes.length > 0) draw();
}
window.addEventListener('resize', resize);
function initGraph() {
stopAnimation();
nodes = [];
edges = [];
iteration = 0;
colorCache[0] = '#ffffff'; // fallback
// 1. Create Cluster Centers
const centers = [];
for(let i=0; i<CONFIG.clusterCount; i++) {
centers.push({
x: Math.random() * (width * 0.8) + (width * 0.1),
y: Math.random() * (height * 0.8) + (height * 0.1)
});
}
// 2. Create Nodes around centers (Gaussian-ish distribution)
for (let i = 0; i < CONFIG.nodeCount; i++) {
const centerIndex = Math.floor(Math.random() * CONFIG.clusterCount);
const center = centers[centerIndex];
// Random offset
const angle = Math.random() * Math.PI * 2;
const dist = Math.random() * 100; // spread
const x = Math.min(Math.max(center.x + Math.cos(angle) * dist, 10), width - 10);
const y = Math.min(Math.max(center.y + Math.sin(angle) * dist, 10), height - 10);
nodes.push({
id: i,
x: x,
y: y,
label: i, // Every node starts with its own unique label
neighbors: []
});
}
// 3. Create Edges (Geometric Graph)
for (let i = 0; i < nodes.length; i++) {
for (let j = i + 1; j < nodes.length; j++) {
const dx = nodes[i].x - nodes[j].x;
const dy = nodes[i].y - nodes[j].y;
const dist = Math.sqrt(dx*dx + dy*dy);
if (dist < CONFIG.connectionRadius) {
edges.push({ source: nodes[i], target: nodes[j] });
nodes[i].neighbors.push(nodes[j]);
nodes[j].neighbors.push(nodes[i]);
}
}
}
updateUI();
draw();
}
/* --- HELPER: COLORS --- */
// Generate a consistent color for a label ID
function getColor(labelId) {
if (colorCache[labelId]) return colorCache[labelId];
// Use Golden Angle approximation to spread colors distinctively
const hue = (labelId * 137.508) % 360;
const color = `hsl(${hue}, 70%, 55%)`;
colorCache[labelId] = color;
return color;
}
/* --- ALGORITHM LOGIC --- */
function performLPAStep() {
// LPA works best if update order is random to prevent oscillation
// Create a shuffled order index list
const order = Array.from({length: nodes.length}, (_, i) => i);
shuffleArray(order);
let changed = false;
// Iterate through nodes in random order
for (let i of order) {
const node = nodes[i];
if (node.neighbors.length === 0) continue;
// 1. Count neighbor labels
const labelCounts = {};
node.neighbors.forEach(neighbor => {
const l = neighbor.label;
labelCounts[l] = (labelCounts[l] || 0) + 1;
});
// 2. Find max frequency
let maxCount = -1;
let bestLabels = [];
for (const [lbl, count] of Object.entries(labelCounts)) {
if (count > maxCount) {
maxCount = count;
bestLabels = [parseInt(lbl)];
} else if (count === maxCount) {
bestLabels.push(parseInt(lbl));
}
}
// 3. Tie-breaking: Randomly choose one of the best labels
if (bestLabels.length > 0) {
// If current label is already one of the best, prefer keeping it (stability)
// otherwise pick random
if (!bestLabels.includes(node.label)) {
const newLabel = bestLabels[Math.floor(Math.random() * bestLabels.length)];
if (node.label !== newLabel) {
node.label = newLabel;
changed = true;
}
}
}
}
if (changed) iteration++;
updateUI();
draw();
return changed;
}
// Fisher-Yates Shuffle
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
function getCommunityCount() {
const s = new Set();
nodes.forEach(n => s.add(n.label));
return s.size;
}
/* --- DRAWING --- */
function draw() {
// Clear
ctx.fillStyle = '#1a1a1a';
ctx.fillRect(0, 0, width, height);
// Draw Edges
ctx.strokeStyle = '#444';
ctx.lineWidth = 1;
ctx.beginPath();
for (const edge of edges) {
ctx.moveTo(edge.source.x, edge.source.y);
ctx.lineTo(edge.target.x, edge.target.y);
}
ctx.stroke();
// Draw Nodes
for (const node of nodes) {
ctx.beginPath();
ctx.arc(node.x, node.y, CONFIG.nodeRadius, 0, Math.PI * 2);
ctx.fillStyle = getColor(node.label);
ctx.fill();
ctx.strokeStyle = '#fff';
ctx.lineWidth = 1;
ctx.stroke();
}
}
/* --- CONTROL LOGIC --- */
const btnReset = document.getElementById('btn-reset');
const btnStep = document.getElementById('btn-step');
const btnRun = document.getElementById('btn-run');
const statusSpan = document.getElementById('status');
const iterSpan = document.getElementById('iter-count');
const commSpan = document.getElementById('comm-count');
function updateUI() {
iterSpan.textContent = iteration;
commSpan.textContent = getCommunityCount();
}
function stopAnimation() {
isRunning = false;
clearTimeout(timer);
btnRun.textContent = "Run Animation";
btnStep.disabled = false;
statusSpan.textContent = "Paused";
statusSpan.style.color = "#aaa";
}
function runAnimationLoop() {
if (!isRunning) return;
const changed = performLPAStep();
if (!changed) {
stopAnimation();
statusSpan.textContent = "Converged";
statusSpan.style.color = "#4caf50";
btnRun.textContent = "Finished";
btnStep.disabled = true;
return;
}
timer = setTimeout(() => {
requestAnimationFrame(runAnimationLoop);
}, CONFIG.animationSpeed);
}
btnReset.addEventListener('click', initGraph);
btnStep.addEventListener('click', () => {
const changed = performLPAStep();
statusSpan.textContent = "Stepped";
if(!changed) {
statusSpan.textContent = "Converged (No changes)";
statusSpan.style.color = "#4caf50";
}
});
btnRun.addEventListener('click', () => {
if (isRunning) {
stopAnimation();
} else {
isRunning = true;
btnRun.textContent = "Stop";
btnStep.disabled = true;
statusSpan.textContent = "Running...";
statusSpan.style.color = "#ffeb3b";
runAnimationLoop();
}
});
// Start
resize();
initGraph();
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment