Home

Welcome to the chinese-whispers wiki!

PYTHON VERSION

from random import shuffle
import networkx as nx

# build nodes and edge lists
nodes = [
    (0,{'attr1':1}),
    (1,{'attr1':1}),
    (2,{'attr1':1}),
    (3,{'attr1':1}),
    (4,{'attr1':1}),
    (5,{'attr1':1}),
    (6,{'attr1':1}),
    (7,{'attr1':1}),
    (8,{'attr1':1}),
    (9,{'attr1':1}),
]
edges = [
    (1,2,{'weight': 0.732}),
    (1,3,{'weight': 0.732}),
    (1,4,{'weight': 0.732}),
    (1,5,{'weight': 0.732}),
    (6,7,{'weight': 0.732}),
    (6,8,{'weight': 0.732}),
    (6,9,{'weight': 0.732}),
]

# initialize the graph
G = nx.Graph()

# Add nodes
G.add_nodes_from(nodes)
# CW needs an arbitrary, unique class 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 n, v in enumerate(nodes):
    G.node[n]['class'] = n

# add edges
G.add_edges_from(edges)

# 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
iterations = 10
for z in range(0,iterations):
    gn = G.nodes()
    # I randomize the nodes to give me an arbitrary start point
    shuffle(gn)
    for node in gn:
        neighs = G[node]
        classes = {}
        # do an inventory of the given nodes neighbours and edge weights
        for ne in neighs:
            if isinstance(ne, int) :
                # print(classes)
                # print(G.node[ne]['class'])
                if G.node[ne]['class'] in classes:
                    classes[G.node[ne]['class']] += G[node][ne]['weight']
                else:
                    classes[G.node[ne]['class']] = G[node][ne]['weight']
        # find the class with the highest edge weight sum
        max = 0
        maxclass = 0
        for c in classes:
            if classes[c] > max:
                max = classes[c]
                maxclass = c
        # set the class of target node to the winning local class
        G.node[node]['class'] = maxclass

print(G.node)

TYPESCRIPT VERSION

const jsnx              = require('jsnetworkx')
const { knuthShuffle }  = require('knuth-shuffle')

// build nodes and edge lists
const nodes = [
    [0, {'attr1':1}],
    [1, {'attr1':1}],
    [2, {'attr1':1}],
    [3, {'attr1':1}],
    [4, {'attr1':1}],
    [5, {'attr1':1}],
    [6, {'attr1':1}],
    ['c', {'attr1':1}],
    ['b', {'attr1':1}],
    ['a', {'attr1':1}],
]
const edges = [
    [1,2,{'weight': 0.732}],
    [1,3,{'weight': 0.732}],
    [1,4,{'weight': 0.732}],
    [1,5,{'weight': 0.732}],
    [6,'c',{'weight': 0.732}],
    [6,'b',{'weight': 0.732}],
    [6,'a',{'weight': 0.732}],
]

// initialize the graph
const G = new jsnx.Graph()

// Add nodes
G.addNodesFrom(nodes)
// CW needs an arbitrary, unique class 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 (let n of G.nodes()) {
  G.node.get(n)['class'] = n
}

// add edges
G.addEdgesFrom(edges)

// 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 iterations = 10
while (iterations--) {
  const gn = G.nodes()
  // I randomize the nodes to give me an arbitrary start point
  knuthShuffle(gn)  // orignal array modified
  for (let node of gn) {
    const neighs = G.neighbors(node)
    const classes: any = {}
    // do an inventory of the given nodes neighbours and edge weights
    // console.log(neighs)
    for (const ne of neighs) {
      // console.log('ne', ne)
      if (typeof ne === 'number') {
        // console.log(classes)
        // console.log('class: ', G.node.get(ne)['class'])
        if (G.node.get(ne)['class'] in classes) {
          classes[G.node.get(ne)['class']] += G.get(node).get(ne)['weight']
        } else {
          classes[G.node.get(ne)['class']] = G.get(node).get(ne)['weight']
          // console.log('else: ', G.node.get(ne)['class'], G.get(node).get(ne)['weight'])
        }
      }
    }
    // find the class with the highest edge weight sum
    let max = 0
    let maxclass = 0
    Object.keys(classes).forEach(c => {
      if (classes[c] > max) {
        max = classes[c]
        maxclass = c as any
      }
    })
    // set the class of target node to the winning local class
    G.node.get(node)['class'] = maxclass
  }
}
console.log(G.node)