I am trying to implement the Chinese Whispers Algorithm, but I can not figure out the issue below: the result that I want to get is like in the picture below
import networkx as nx
from random import shuffle as shuffle
# build nodes and edge lists
nodes = [
(1,{'attr1':1}),
(2,{'attr1':1})
]
edges = [
(1,2,{'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[v[0]]["class"] = v[1]["attr1"]
# 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) :
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
I want to make this output enter image description here
As noted in the answer by @Shridhar R Kulkarni, you want to use G.nodes when referencing nodes for updating/adding attributes.
Another problem with the script is that for shuffling, you want only the list of node identifiers:
gn = list(G.nodes()) # use list() to allow shuffling
shuffle(gn)
If you are interested in just the computation, rather than (re)implementation, you could also use an existing library chinese-whispers.