.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "tutorials/cluster_contraction.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. .. rst-class:: sphx-glr-example-title .. _sphx_glr_tutorials_cluster_contraction.py: .. _tutorials-cluster-graph: =========================== Generating Cluster Graphs =========================== This example shows how to find the communities in a graph, then contract each community into a single node using :class:`igraph.clustering.VertexClustering`. For this tutorial, we'll use the *Donald Knuth's Les Miserables Network*, which shows the coapperances of characters in the novel *Les Miserables*. .. GENERATED FROM PYTHON SOURCE LINES 10-14 .. code-block:: Python import igraph as ig import matplotlib.pyplot as plt .. GENERATED FROM PYTHON SOURCE LINES 15-17 We begin by load the graph from file. The file containing this network can be downloaded `here `_. .. GENERATED FROM PYTHON SOURCE LINES 17-19 .. code-block:: Python g = ig.load("./lesmis/lesmis.gml") .. GENERATED FROM PYTHON SOURCE LINES 20-24 Now that we have a graph in memory, we can generate communities using :meth:`igraph.Graph.community_edge_betweenness` to separate out vertices into clusters. (For a more focused tutorial on just visualising communities, check out :ref:`tutorials-visualize-communities`). .. GENERATED FROM PYTHON SOURCE LINES 24-26 .. code-block:: Python communities = g.community_edge_betweenness() .. GENERATED FROM PYTHON SOURCE LINES 27-28 For plots, it is convenient to convert the communities into a VertexClustering: .. GENERATED FROM PYTHON SOURCE LINES 28-30 .. code-block:: Python communities = communities.as_clustering() .. GENERATED FROM PYTHON SOURCE LINES 31-32 We can also easily print out who belongs to each community: .. GENERATED FROM PYTHON SOURCE LINES 32-37 .. code-block:: Python for i, community in enumerate(communities): print(f"Community {i}:") for v in community: print(f"\t{g.vs[v]['label']}") .. rst-class:: sphx-glr-script-out .. code-block:: none 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 .. GENERATED FROM PYTHON SOURCE LINES 38-40 Finally we can proceed to plotting the graph. In order to make each community stand out, we set "community colors" using an igraph palette: .. GENERATED FROM PYTHON SOURCE LINES 40-47 .. code-block:: Python 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 .. GENERATED FROM PYTHON SOURCE LINES 48-49 We can use a dirty hack to move the labels below the vertices ;-) .. GENERATED FROM PYTHON SOURCE LINES 49-51 .. code-block:: Python g.vs["label"] = ["\n\n" + label for label in g.vs["label"]] .. GENERATED FROM PYTHON SOURCE LINES 52-53 Finally, we can plot the communities: .. GENERATED FROM PYTHON SOURCE LINES 53-65 .. code-block:: Python fig1, ax1 = plt.subplots() ig.plot( communities, target=ax1, mark_groups=True, palette=palette1, vertex_size=15, edge_width=0.5, ) fig1.set_size_inches(20, 20) .. image-sg:: /tutorials/images/sphx_glr_cluster_contraction_001.png :alt: cluster contraction :srcset: /tutorials/images/sphx_glr_cluster_contraction_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 66-69 Now let's try and contract the information down, using only a single vertex to represent each community. We start by defining x, y, and size attributes for each node in the original graph: .. GENERATED FROM PYTHON SOURCE LINES 69-74 .. code-block:: Python layout = g.layout_kamada_kawai() g.vs["x"], g.vs["y"] = list(zip(*layout)) g.vs["size"] = 15 g.es["size"] = 15 .. GENERATED FROM PYTHON SOURCE LINES 75-78 Then we can generate the cluster graph that compresses each community into a single, "composite" vertex using :meth:`igraph.VertexClustering.cluster_graph`: .. GENERATED FROM PYTHON SOURCE LINES 78-90 .. code-block:: Python cluster_graph = communities.cluster_graph( combine_vertices={ "x": "mean", "y": "mean", "color": "first", "size": "sum", }, combine_edges={ "size": "sum", }, ) .. GENERATED FROM PYTHON SOURCE LINES 91-104 .. note:: We took the mean of x and y values so that the nodes in the cluster graph are placed at the centroid of the original cluster. .. 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 :meth:`igraph.GraphBase.contract_vertices`. .. GENERATED FROM PYTHON SOURCE LINES 107-109 Finally, we can assign colors to the clusters and plot the cluster graph, including a legend to make things clear: .. GENERATED FROM PYTHON SOURCE LINES 109-147 .. code-block:: Python 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(20, size) 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) .. image-sg:: /tutorials/images/sphx_glr_cluster_contraction_002.png :alt: cluster contraction :srcset: /tutorials/images/sphx_glr_cluster_contraction_002.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 1.462 seconds) .. _sphx_glr_download_tutorials_cluster_contraction.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: cluster_contraction.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: cluster_contraction.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: cluster_contraction.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_