Group vertices in clusters using NetworkX

Question

I am trying to represent graphically some graphs, and I need to group in clusters some nodes that have a common characteristics.

I am using NetworkX, and I need to do something similar with the graph from this tutorial, from the slide 44, left figure.

I want to draw some delimiting line around each cluster. My current code is like that:

vec = self.colors
colors = (linspace(0, 1, len(set(vec))) * 20 + 10)
nx.draw_circular(g, node_color=array([colors[x] for x in vec]))
show()

I wish to find an example and see how can I use networkx to cluster the graph.

Answer 1

I'm not positive what your question is. I think you're asking "how do I get networkx to put some nodes close together"

Before I launch into the answer, the drawing documentation for networkx is here: http://networkx.lanl.gov/reference/drawing.html

So that figure you're asking about has 4 different communities that are clustered based on having lots of edges within each community and not many outside.

If you don't want to put much effort into it, spring_layout is often good for putting tightly knit communities together. The basic algorithm of spring_layout acts as if the edges are springs (and nodes repel). So lots of edges keeps nodes close together. Note that it initializes the positions randomly, so each time you'll get a different output.

The easiest way to do this is just

nx.draw_spring(G)

But maybe you want more. If you want to, you can fix every single node's position. Define a dict, usually named pos.

pos = {}
for node in G.nodes_iter():
    pos[node] = (xcoord, ycoord).

where xcoord and ycoord are the coordinates you want the node to be at.

Then just do draw_networkx(G, pos = pos)

That's often a lot of effort. So sometimes you just tell it a few of them have to be in particular places, and let networkx do the rest

Define fixedpos for a few nodes and then run spring_layout telling it what nodes are fixed and giving it fixedpos as the initial positions. Then it will hold those fixed and fit everything else around.

Here is some code which generates a network that has 4 completely connected parts and a few other edges between them. (actually it generates a complete network and then deletes all but a few edges between these parts). Then it draws it with a simple spring layout. Then it fixes 4 of them to be at the corners of a square and places the other nodes around those fixed positions.

import networkx as nx
import random
import pylab as py
from math import floor

G = nx.complete_graph(20)

for edge in G.edges():
    if floor(edge[0]/5.)!=floor(edge[1]/5.):
        if random.random()<0.95:
            G.remove_edge(edge[0],edge[1])


nx.draw_spring(G)
py.show()


fixedpos = {1:(0,0), 6:(1,1), 11:(1,0), 16:(0,1)}
pos = nx.spring_layout(G, fixed = fixedpos.keys(), pos = fixedpos)

nx.draw_networkx(G, pos=pos)

py.show()

You can also specify weights to the edges, pass the weights to spring_layout and larger weights will tell it to keep the corresponding nodes closer together. So once you've identified your communities, increase weights within the communities/clusters if necessary to keep them close together.

Note that you can also specify what color to make each node, so it is straightforward to specify the color for each community/cluster.

If you then want to draw curves around each of those clusters, you'll have to do that through matplotlib.