Generating Cluster Graphs ¶
Generating Cluster Graphs¶
This example shows how to find the communities in a graph, then contract each community into a single node using cluster_graph()
. For this tutorial, we’ll use the Donald Knuth’s Les Miserables Network, which shows the coapperances of characters in the novel Les Miserables. The network can be obtained here.
import igraph as ig
import matplotlib.pyplot as plt
# Load the graph
g = ig.load("./lesmis/lesmis.gml")
First, let’s visualise the original communities, using community_edge_betweenness()
to separate out vertices into clusters. (For a more focused tutorial on just visualising communities, check out Communities).
# Generate communities
communities = g.community_edge_betweenness()
communities = communities.as_clustering() # Convert into a VertexClustering for plotting
# Print them out
for i, community in enumerate(communities):
print(f"Community {i}:")
for v in community:
print(f"\t{g.vs[v]['label']}")
# Set community colors
num_communities = len(communities)
palette1 = ig.RainbowPalette(n=num_communities)
for i, community in enumerate(communities):
g.vs[community]["color"] = i
community_edges = g.es.select(_within=community)
community_edges["color"] = i
g.vs["label"] = ["\n\n" + label for label in g.vs["label"]] # Move the labels below the vertices
# Plot the communities
fig1, ax1 = plt.subplots()
ig.plot(
communities,
target=ax1,
mark_groups=True,
palette=palette1,
vertex_size=0.1,
edge_width=0.5,
)
fig1.set_size_inches(20, 20)
fig1.savefig("../figures/communities.png", dpi=200)
Now let’s try and contract the information down, using only a single vertex to represent each community. We start by defining attribute values for each of the nodes in the original graph.
# Assign x, y, and sizes for each node
layout = g.layout_kamada_kawai()
g.vs["x"], g.vs["y"] = list(zip(*layout))
g.vs["size"] = 1
g.es["size"] = 1
This is so we can define how each of these attributes get combined together when we call cluster_graph()
.
# Generate cluster graph
cluster_graph = communities.cluster_graph(
combine_vertices={
"x": "mean",
"y": "mean",
"color": "first",
"size": "sum",
},
combine_edges={
"size": "sum",
},
)
Here, we take the mean of x and y values so that the nodes in the cluster graph are placed at the center of the original cluster’s position.
Note
mean
, first
, and sum
are all built-in collapsing functions, along with prod
, median
, max
, min
, last
, random
. You can also define your own custom collapsing functions, which take in a list and return a single element representing the combined attribute value. For more details on igraph contraction, see contract_vertices()
Finally we plot out the graph using our calculated attributes:
# Plot the cluster graph
palette2 = ig.GradientPalette("gainsboro", "black")
g.es["color"] = [palette2.get(int(i)) for i in ig.rescale(cluster_graph.es["size"], (0, 255), clamp=True)]
fig2, ax2 = plt.subplots()
ig.plot(
cluster_graph,
target=ax2,
palette=palette1,
# set a minimum size on vertex_size, otherwise vertices are too small
vertex_size=[max(0.2, size / 20) for size in cluster_graph.vs["size"]],
edge_color=g.es["color"],
edge_width=0.8,
)
# Add a legend
legend_handles = []
for i in range(num_communities):
handle = ax2.scatter(
[], [],
s=100,
facecolor=palette1.get(i),
edgecolor="k",
label=i,
)
legend_handles.append(handle)
ax2.legend(
handles=legend_handles,
title='Community:',
bbox_to_anchor=(0, 1.0),
bbox_transform=ax2.transAxes,
)
fig2.set_size_inches(10, 10)
fig2.savefig("../figures/cluster_graph.png", dpi=150)
The two figures are shown side by side here:
… and the final output of the communities we printed out are displayed below:
Community 0:
Myriel
Napoleon
MlleBaptistine
MmeMagloire
CountessDeLo
Geborand
Champtercier
Cravatte
Count
OldMan
Community 1:
Labarre
Valjean
MmeDeR
Isabeau
Gervais
Bamatabois
Simplice
Scaufflaire
Woman1
Judge
Champmathieu
Brevet
Chenildieu
Cochepaille
Community 2:
Marguerite
Tholomyes
Listolier
Fameuil
Blacheville
Favourite
Dahlia
Zephine
Fantine
Perpetue
Community 3:
MmeThenardier
Thenardier
Javert
Pontmercy
Eponine
Anzelma
Gueulemer
Babet
Claquesous
Montparnasse
Brujon
Community 4:
Cosette
Woman2
Gillenormand
Magnon
MlleGillenormand
MmePontmercy
MlleVaubois
LtGillenormand
BaronessT
Toussaint
Community 5:
Fauchelevent
MotherInnocent
Gribier
Community 6:
Boulatruelle
Community 7:
Jondrette
MmeBurgon
Community 8:
Gavroche
Marius
Mabeuf
Enjolras
Combeferre
Prouvaire
Feuilly
Courfeyrac
Bahorel
Bossuet
Joly
Grantaire
MmeHucheloup
Community 9:
MotherPlutarch
Community 10:
Child1
Child2