chinese-whispers
Chinese Whispers Algorithm
Last updated 2 years ago by zixia .
Apache-2.0 · Repository · Bugs · Original npm · Tarball · package.json
`\$ cnpm install chinese-whispers `
SYNC missed versions from official npm registry.

# 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:

## 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)

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

## Current Tags

• 0.2.11                                ...           latest (2 years ago)
• 0.3.9                                ...           next (a year ago)

## 24 Versions

• 0.3.9                                ...           a year ago
• 0.3.7                                ...           a year ago
• 0.3.4                                ...           a year ago
• 0.3.2                                ...           2 years ago
• 0.3.1                                ...           2 years ago
• 0.2.11                                ...           2 years ago
• 0.2.10                                ...           2 years ago
• 0.2.9                                ...           2 years ago
• 0.2.8                                ...           2 years ago
• 0.2.7                                ...           2 years ago
• 0.2.6                                ...           2 years ago
• 0.2.5                                ...           2 years ago
• 0.1.5                                ...           3 years ago
• 0.1.4                                ...           3 years ago
• 0.1.3                                ...           3 years ago
• 0.1.2                                ...           3 years ago
• 0.1.1                                ...           3 years ago
• 0.0.15                                ...           3 years ago
• 0.0.14                                ...           3 years ago
• 0.0.13                                ...           3 years ago
• 0.0.12                                ...           3 years ago
• 0.0.11                                ...           3 years ago
• 0.0.10                                ...           3 years ago
• 0.0.5                                ...           3 years ago
Maintainers (1)