how to draw communities with networkx
Answer
The documentation for networkx.draw_networkx_nodes and networkx.draw_networkx_edges explains how to set the node and edge colors. The patches bounding the communities can be made by finding the positions of the nodes for each community and then drawing a patch (e.g. matplotlib.patches.Circle) that contains all positions (and then some).
The hard bit is the graph layout / setting the node positions. AFAIK, there is no routine in networkx to achieve the desired graph layout "out of the box". What you want to do is the following:
1) Position the communities with respect to each other: create a new, weighted graph, where each node corresponds to a community, and the weights correspond to the number of edges between communities. Get a decent layout with your favourite graph layout algorithm (e.g.spring_layout).
2) Position the nodes within each community: for each community, create a new graph. Find a layout for the subgraph.
3) Combine node positions in 1) and 3). E.g. scale community positions calculated in 1) by a factor of 10; add those values to the positions of all nodes (as computed in 2)) within that community.
I have been wanting to implement this for a while. I might do it later today or over the weekend.
EDIT:
Voila. Now you just need to draw your favourite patch around (behind) the nodes.
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
def community_layout(g, partition):
"""
Compute the layout for a modular graph.
Arguments:
----------
g -- networkx.Graph or networkx.DiGraph instance
graph to plot
partition -- dict mapping int node -> int community
graph partitions
Returns:
--------
pos -- dict mapping int node -> (float x, float y)
node positions
"""
pos_communities = _position_communities(g, partition, scale=3.)
pos_nodes = _position_nodes(g, partition, scale=1.)
# combine positions
pos = dict()
for node in g.nodes():
pos[node] = pos_communities[node] + pos_nodes[node]
return pos
def _position_communities(g, partition, **kwargs):
# create a weighted graph, in which each node corresponds to a community,
# and each edge weight to the number of edges between communities
between_community_edges = _find_between_community_edges(g, partition)
communities = set(partition.values())
hypergraph = nx.DiGraph()
hypergraph.add_nodes_from(communities)
for (ci, cj), edges in between_community_edges.items():
hypergraph.add_edge(ci, cj, weight=len(edges))
# find layout for communities
pos_communities = nx.spring_layout(hypergraph, **kwargs)
# set node positions to position of community
pos = dict()
for node, community in partition.items():
pos[node] = pos_communities[community]
return pos
def _find_between_community_edges(g, partition):
edges = dict()
for (ni, nj) in g.edges():
ci = partition[ni]
cj = partition[nj]
if ci != cj:
try:
edges[(ci, cj)] += [(ni, nj)]
except KeyError:
edges[(ci, cj)] = [(ni, nj)]
return edges
def _position_nodes(g, partition, **kwargs):
"""
Positions nodes within communities.
"""
communities = dict()
for node, community in partition.items():
try:
communities[community] += [node]
except KeyError:
communities[community] = [node]
pos = dict()
for ci, nodes in communities.items():
subgraph = g.subgraph(nodes)
pos_subgraph = nx.spring_layout(subgraph, **kwargs)
pos.update(pos_subgraph)
return pos
def test():
# to install networkx 2.0 compatible version of python-louvain use:
# pip install -U git+https://github.com/taynaud/python-louvain.git@networkx2
from community import community_louvain
g = nx.karate_club_graph()
partition = community_louvain.best_partition(g)
pos = community_layout(g, partition)
nx.draw(g, pos, node_color=list(partition.values())); plt.show()
return