Implementation of the Label Propagation (LP) algorithm

// Function to initialize labels at all nodes function initializeLabels(graph) { const labels = new Map(); graph.nodes.forEach(node => { labels.set(node, node); // Initialize label at each node to itself }); return labels; }

# Shuffle

// Function to randomly shuffle an array 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]]; } return array; }

// Function to randomly shuffle an array 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]]; } return array; }

// Function to apply Label Propagation algorithm function labelPropagation(graph, tmax) { const labels = initializeLabels(graph); let t = 0; while (t < tmax) { let changed = false; const nodes = shuffleArray(Array.from(graph.nodes)); // Randomize node order nodes.forEach(node => { const neighbors = graph.neighbors(node); const neighborLabels = Array.from(neighbors.values()).map(neighbor => labels.get(neighbor)); const frequencies = new Map(); // Count frequencies of neighbor labels neighborLabels.forEach(label => { frequencies.set(label, (frequencies.get(label) || 0) + 1); }); // Find label with highest frequency (ties broken randomly) const maxFrequency = Math.max(...frequencies.values()); const maxLabels = Array.from(frequencies.entries()).filter(([label, freq]) => freq === maxFrequency); const newLabel = maxLabels[Math.floor(Math.random() * maxLabels.length)][0]; // Update label if different from current label if (newLabel !== labels.get(node)) { labels.set(node, newLabel); changed = true; } }); if (!changed) { break; // Stop if no label changes occurred } t++; } return labels; }

// Example usage: // Assuming you have a graph object called 'graph' const tmax = 100; // Maximum number of iterations const communityLabels = labelPropagation(graph, tmax); console.log("Community Labels:", communityLabels);

~