scripts/clustering.js - master - komarovdd/GraphViz

scripts/clustering.js
226 строк7 KB
komarovdd
new vers
10 фев 2026, 10:21
10 фев 2026, 10:21d49b515
/**
 * Base class for all clustering algorithms.
 */
class ClusteringAlgorithm {
    constructor(name) {
        this.name = name;
    }

    /**
     * Executes the clustering algorithm.
     * @param {Graph} graph 
     * @returns {Map<string, number>} Map of nodeId -> clusterId
     */
    run(graph) {
        throw new Error("Method run() must be implemented");
    }
}

/**
 * K-Core Algorithm (Structural Clustering)
 * Identifies the core-shell structure of the graph.
 */
class KCoreClustering extends ClusteringAlgorithm {
    constructor() {
        super("K-Core (Topology)");
    }

    run(graph, params = {}) {
        const nodes = Array.from(graph.nodes.keys());
        const degrees = new Map();
        const adj = new Map();

        nodes.forEach(id => {
            degrees.set(id, 0);
            adj.set(id, []);
        });

        graph.edges.forEach(e => {
            if (e.weight < (params.minWeight || 0)) return;
            const u = e.source, v = e.target;
            if (adj.has(u) && adj.has(v)) {
                adj.get(u).push(v);
                adj.get(v).push(u);
                degrees.set(u, degrees.get(u) + 1);
                degrees.set(v, degrees.get(v) + 1);
            }
        });

        const coreness = new Map();
        const sortedNodes = [...nodes].sort((a, b) => degrees.get(a) - degrees.get(b));

        // Simplistic O(V+E) coreness algorithm
        let currentK = 0;
        const exists = new Set(nodes);

        while (sortedNodes.length > 0) {
            sortedNodes.sort((a, b) => degrees.get(a) - degrees.get(b));
            const v = sortedNodes.shift();
            currentK = Math.max(currentK, degrees.get(v));
            coreness.set(v, currentK);
            exists.delete(v);

            (adj.get(v) || []).forEach(u => {
                if (exists.has(u)) {
                    degrees.set(u, degrees.get(u) - 1);
                }
            });
        }

        const filtered = new Map();
        const minK = params.kcoreK || 1;
        coreness.forEach((k, v) => {
            if (k >= minK && (adj.get(v) || []).length > 0) filtered.set(v, k);
        });
        return filtered;
    }
}

/**
 * Leiden algorithm (Topological Clustering)
 */
class LeidenClustering extends ClusteringAlgorithm {
    constructor() {
        super("Leiden (Topological)");
    }

    run(graph, params = {}) {
        const minW = params.minWeight || 0;
        const res = params.res || 1.0;
        const iterations = params.iterations || 10;
        const nodes = Array.from(graph.nodes.keys());
        const validEdges = graph.edges.filter(e => e.weight >= minW);

        const activeNodes = new Set();
        validEdges.forEach(e => { activeNodes.add(e.source); activeNodes.add(e.target); });

        let communities = new Map();
        activeNodes.forEach(id => communities.set(id, id));

        const m2 = validEdges.reduce((acc, e) => acc + e.weight, 0) * 2 || 1;
        const degs = new Map();
        activeNodes.forEach(id => degs.set(id, 0));
        validEdges.forEach(e => {
            degs.set(e.source, (degs.get(e.source) || 0) + e.weight);
            degs.set(e.target, (degs.get(e.target) || 0) + e.weight);
        });

        const activeNodesArr = Array.from(activeNodes);
        for (let i = 0; i < iterations; i++) {
            let moved = false;
            activeNodesArr.sort(() => Math.random() - 0.5);
            activeNodesArr.forEach(u => {
                const curC = communities.get(u);
                const neighborC = new Map();
                validEdges.forEach(e => {
                    if (e.source === u || e.target === u) {
                        const v = e.source === u ? e.target : e.source;
                        const c = communities.get(v);
                        neighborC.set(c, (neighborC.get(c) || 0) + e.weight);
                    }
                });

                let bestC = curC, maxG = 0;
                const ki = degs.get(u);
                neighborC.forEach((k_in, c) => {
                    let sigma = 0;
                    communities.forEach((comm, node) => { if (comm === c) sigma += degs.get(node); });
                    const gain = (k_in / m2) - res * (ki * (sigma - (c === curC ? ki : 0)) / (m2 * m2));
                    if (gain > maxG) { maxG = gain; bestC = c; }
                });
                if (bestC !== curC) { communities.set(u, bestC); moved = true; }
            });
            if (!moved) break;
        }
        return communities;
    }
}

/**
 * K-Means Algorithm (Spatial Clustering)
 */
class KMeansClustering extends ClusteringAlgorithm {
    constructor() {
        super("K-Means (Spatial)");
    }

    run(graph, params = {}) {
        const k = params.k || 3;
        const nodes = Array.from(graph.nodes.values());
        if (nodes.length < k) return new Map();

        let centroids = nodes.slice(0, k).map(n => ({ x: n.x, y: n.y }));
        let clusters = new Map();

        for (let iter = 0; iter < 10; iter++) {
            clusters = new Map();
            nodes.forEach(n => {
                let minDist = Infinity, best = 0;
                centroids.forEach((c, i) => {
                    const d = Math.hypot(n.x - c.x, n.y - c.y);
                    if (d < minDist) { minDist = d; best = i; }
                });
                clusters.set(n.id, best);
            });

            const newCentroids = Array.from({ length: k }, () => ({ x: 0, y: 0, count: 0 }));
            nodes.forEach(n => {
                const c = newCentroids[clusters.get(n.id)];
                c.x += n.x; c.y += n.y; c.count++;
            });
            centroids = newCentroids.map(c => c.count > 0 ? { x: c.x / c.count, y: c.y / c.count } : { x: Math.random() * 800, y: Math.random() * 600 });
        }
        return clusters;
    }
}

/**
 * DBSCAN Algorithm (Spatial Clustering)
 */
class DBScanClustering extends ClusteringAlgorithm {
    constructor() {
        super("DBSCAN (Spatial)");
    }

    run(graph, params = {}) {
        const eps = params.eps || 100, minPts = params.minPts || 2;
        const nodes = Array.from(graph.nodes.values());
        const m = new Map();
        const visited = new Set(), noise = new Set();
        let clusterCount = 0;

        const getNeighbors = n => nodes.filter(other => Math.hypot(n.x - other.x, n.y - other.y) < eps);

        nodes.forEach(n => {
            if (visited.has(n.id)) return;
            visited.add(n.id);
            const neighbors = getNeighbors(n);
            if (neighbors.length < minPts) {
                noise.add(n.id);
            } else {
                const cId = clusterCount++;
                m.set(n.id, cId);
                const stack = [...neighbors];
                while (stack.length) {
                    const curr = stack.pop();
                    if (noise.has(curr.id)) { noise.delete(curr.id); m.set(curr.id, cId); }
                    if (visited.has(curr.id)) continue;
                    visited.add(curr.id);
                    m.set(curr.id, cId);
                    const currNeighbors = getNeighbors(curr);
                    if (currNeighbors.length >= minPts) stack.push(...currNeighbors);
                }
            }
        });
        return m;
    }
}

const clusteringRegistry = [
    new KCoreClustering(),
    new LeidenClustering(),
    new KMeansClustering(),
    new DBScanClustering()
];

export { ClusteringAlgorithm, clusteringRegistry };