CHINESE-WHISPERS

An Efficient Graph Clustering Algorithm for JavaScript/Node.js

Picture credit: http://www.wikihow.com/Play-Chinese-Whispers

ALGORITHM

Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems

Author: Chris Biemann, University of Leipzig, NLP-Dept. Leipzig, Germany

1. Wikipedia
2. Slide - 2006 TextGraphs 06, NYC, USA
3. Paper

INSTALL

npm install chinese-whispers

EXAMPLE

Talk is cheap, show me the code!

import { ChineseWhispers } from 'chinese-whispers'
 
function weightFunc(a, b) {
  const dist = Math.abs(a - b)
  return 1 / dist
}
 
const cw = new ChineseWhispers({
  weightFunc,
})
 
const dataList = [
  0, 1, 2,
  10, 11, 12,
  20, 21, 22,
]
 
const clusterIndicesList = cw.cluster(dataList)
 
for (const i in clusterIndicesList) {
  const clusterIndices = clusterIndicesList[i]
  const cluster = clusterIndices.map(j => dataList[j])
  console.log('Cluster[' + i + ']: ' + cluster)
}
// Cluster[0]: 0,1,2
// Cluster[1]: 10,11,12
// Cluster[2]: 20,21,22

Source code can be found at: https://github.com/huan/chinese-whispers/blob/master/examples/demo.ts

API

The ChineseWhispers class is all you need to run the Chinese Whispers Algorithm.

1. constructor(options: ChineseWhisperOptions)

interface ChineseWhispersOptions<T> {
  weightFunc: WeightFunc<T>,
  epochs?:    number,
  threshold?: number,
}

• options
  • weightFunc: a function that takes two data item, calculate the weight between them and return the value.
  • epochs: how many epoches to run the algorithm, default 15.
  • threshold: minimum weight required for a edge. default 0.

const nj = require('numjs') // a Javascript implementation of numpy in Python
 
// calculate the distance between vectors
function weightFunc(v1, v2) {
  const njV1 = nj.array(v1)
  const njV2 = nj.array(v2)
  const l2 = njV1.subtract(njV2)
                .pow(2)
                .sum()
  const dist = Math.sqrt(l2)
  return 1 / dist
}
 
const cw = new ChineseWhispers({
  weightFunc,
})

2. cluster(dataList): number[][]

Process dataList which is an array of data, returns the cluster results as an array, each array item is a cluster, and each cluster is an array which includes the indices of dataList that belongs to this cluster.

const clusterIndicesList = cw.cluster(dataList)
 
for (const i in clusterIndicesList) {
  // get the cluster, which stores the array index dataList
  const clusterIndices = clusterIndicesList[i]
  // map the array index of dataList to the actual dataList data
  const cluster = clusterIndices.map(j => dataList[j])
  console.log('Cluster[' + i + ']: ' + cluster)
}

INSPIRATION

The code is heavily inspired by the following implementation:

• facenet chinese whispers(face cluster) in Python - zhly0
• Chinese Whispers Graph Clustering in Python - Alex Loveless
• A Python implementation of Chris Biemann's algorithm for graph clustering
• Implementation of the Chinese Whispers graph clustering algorithm in Java
• Chinese Whispers Graph Clustering Algorithm in Javascript

SEE ALSO

• The meaning and origin of the expression: Chinese whispers
• TensorFlow backed FaceNet implementation for Node.js - Face verification, face recognition and face clustering.

CHANGELOG

v0.2 master

1. Upgrade TypeScript to 3.0
2. DevOps to npm@next

v0.1 Sep 2017

1. ChineseWhispers class
2. cluster() class method
3. Unit test cases
4. Travis CI & CD(publish to NPM automatically)

AUTHOR

Huan LI <zixia@zixia.net> (http://linkedin.com/in/zixia)

COPYRIGHT & LICENSE

• Code & Docs © 2017-2019 Huan LI <zixia@zixia.net>
• Code released under the Apache-2.0 License
• Docs released under Creative Commons