chinese-whispers/dist/src/chinese-whispers.js

/**
 * Chinese Whispers Algorithm for Node.js
 *
 * https://github.com/huan/chinese-whispers
 * License: Apache-2.0
 * Author: Huan LI <zixia@zixia.net>
 *
 * Inspired by:
 *  - http://blog.csdn.net/liyuan123zhouhui/article/details/70312716
 *  - http://alexloveless.co.uk/data/chinese-whispers-graph-clustering-in-python/
 *  - https://github.com/uhh-lt/chinese-whispers
 *  - https://github.com/anvaka/ngraph.cw
 *
 */
import { EventEmitter } from 'events';
export { VERSION } from './version';
const jsnx = require('jsnetworkx');
const { knuthShuffle } = require('knuth-shuffle');
export class ChineseWhispers extends EventEmitter {
    constructor(options) {
        super();
        this.weightFunc = options.weightFunc;
        this.epochs = options.epochs || 15;
        this.threshold = options.threshold;
        this.on('change', () => this.changeCounter++);
    }
    on(event, listener) {
        super.on(event, listener);
        return this;
    }
    emit(event, ...args) {
        return super.emit(event, ...args);
    }
    cluster(dataList) {
        // this.dataList = dataList
        this.graph = this.buildNetwork(dataList, this.weightFunc, this.threshold);
        // initial epoch
        this.emit('epoch', this.graph, -1);
        // run Chinese Whispers
        // I default to 10 iterations. This number is usually low.
        // After a certain number (individual to the data set) no further clustering occurs
        let epochs = this.epochs;
        while (epochs--) {
            this.changeCounter = 0;
            this.iterate();
            this.emit('epoch', this.graph, this.changeCounter);
        }
        const clusterList = this.buildClusterList(this.graph);
        return clusterList;
    }
    iterate() {
        const nodeList = this.graph.nodes();
        // I randomize the nodes to give me an arbitrary start point
        knuthShuffle(nodeList); // orignal array modified
        for (const node of nodeList) {
            this.relabelNode(node);
        }
    }
    relabelNode(node) {
        const newLabel = this.recalcLabel(node);
        const nodeAttr = this.graph.node.get(node);
        if (nodeAttr.label !== newLabel) {
            // set the label of target node to the winning local label
            this.emit('change', node, nodeAttr.label, newLabel);
            nodeAttr.label = newLabel;
            // console.log('set node ' + this.data[node] + ' label to ' + this.data[parseInt(newLabel)])
        }
    }
    recalcLabel(node) {
        const nxNode = this.graph.get(node);
        const neighborList = this.graph.neighbors(node);
        if (neighborList.length === 0) {
            const attr = this.graph.node.get(node);
            return attr.label; // return self label if no neighbors
        }
        // console.log('neighbors of node ' + this.data[node]
        //     + ' is: ', neighborList.map((i: number) => this.data[i]))
        const labelWeightMap = {};
        // do an inventory of the given nodes neighbours and edge weights
        for (const neighbor of neighborList) {
            const neighborAttr = this.graph.node.get(neighbor);
            const label = neighborAttr.label;
            if (!(label in labelWeightMap)) {
                labelWeightMap[label] = 0;
            }
            const edgeAttr = nxNode.get(neighbor);
            const weight = edgeAttr.weight;
            // console.log('### ', weight, ' ###')
            labelWeightMap[label] += weight;
        }
        // find the label with the highest edge weight sum
        let max = 0;
        // In javascript the keys of object can only be strings
        //  - https://stackoverflow.com/a/41870625/1123955
        let maxLabel = '-1';
        // for (const label in labelWeightMap) {
        //   console.log('labelWeight node: ' + this.data[node] + ' - '
        //       + this.data[parseInt(label)] + ' is: ', labelWeightMap[label])
        // }
        for (const label in labelWeightMap) {
            if (labelWeightMap[label] > max) {
                max = labelWeightMap[label];
                maxLabel = label;
            }
        }
        return maxLabel;
    }
    buildClusterList(G) {
        const clusterList = [];
        const labelIndexMap = {};
        let index = 0;
        for (const node of G.nodes()) {
            const label = G.node.get(node).label;
            if (!(label in labelIndexMap)) {
                labelIndexMap[label] = index++;
            }
            const labelIndex = labelIndexMap[label];
            if (!(labelIndex in clusterList)) {
                clusterList[labelIndex] = [];
            }
            clusterList[labelIndex].push(node);
        }
        return clusterList;
    }
    buildNetwork(dataList, weightFunc, threshold) {
        const nodeList = Object.keys(dataList).map(k => parseInt(k, 10)); // [0, 1, 2, ..., data.length - 1]
        // const nodeList: CWNode[] = [...data.keys()] // [0, 1, 2, ..., data.length - 1]
        const edgeList = [];
        for (let i = 0; i < dataList.length; i++) {
            for (let j = i + 1; j < dataList.length; j++) {
                const weight = weightFunc(dataList[i], dataList[j]);
                if (threshold && threshold > weight) {
                    // console.log('threshold: ', threshold, ' weight: ', weight)
                    // skip this edge because it's weight is below threshold
                    this.emit('edge');
                }
                else {
                    const edge = [i, j, { weight }];
                    edgeList.push(edge);
                    this.emit('edge', edge);
                }
            }
        }
        // initialize the graph
        const G = new jsnx.Graph();
        // Add nodes
        G.addNodesFrom(nodeList);
        // CW needs an arbitrary, unique label for each node before initialisation
        // Here I use the ID of the node since I know it's unique
        // You could use a random number or a counter or anything really
        for (const n of G.nodes()) {
            const nodeAttr = G.node.get(n);
            nodeAttr.label = n;
        }
        // add edges
        G.addEdgesFrom(edgeList);
        // console.log(edgeList)
        return G;
    }
}
export default ChineseWhispers;
//# sourceMappingURL=chinese-whispers.js.map