
.. 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 <sphx_glr_download_tutorials_cluster_contraction.py>`
        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-13

.. code-block:: Python

    import igraph as ig
    import matplotlib.pyplot as plt








.. GENERATED FROM PYTHON SOURCE LINES 14-16

We begin by load the graph from file. The file containing this network can be
downloaded `here <http://www-personal.umich.edu/~mejn/netdata/>`_.

.. GENERATED FROM PYTHON SOURCE LINES 16-18

.. code-block:: Python

    g = ig.load("./lesmis/lesmis.gml")








.. GENERATED FROM PYTHON SOURCE LINES 19-23

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 23-25

.. code-block:: Python

    communities = g.community_edge_betweenness()








.. GENERATED FROM PYTHON SOURCE LINES 26-27

For plots, it is convenient to convert the communities into a VertexClustering:

.. GENERATED FROM PYTHON SOURCE LINES 27-29

.. code-block:: Python

    communities = communities.as_clustering()








.. GENERATED FROM PYTHON SOURCE LINES 30-31

We can also easily print out who belongs to each community:

.. GENERATED FROM PYTHON SOURCE LINES 31-36

.. 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 37-39

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 39-46

.. 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 47-48

We can use a dirty hack to move the labels below the vertices ;-)

.. GENERATED FROM PYTHON SOURCE LINES 48-50

.. code-block:: Python

    g.vs["label"] = ["\n\n" + label for label in g.vs["label"]]








.. GENERATED FROM PYTHON SOURCE LINES 51-52

Finally, we can plot the communities:

.. GENERATED FROM PYTHON SOURCE LINES 52-64

.. 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 65-68

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 68-73

.. 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 74-77

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 77-89

.. 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 90-103

.. 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 106-108

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 108-142

.. 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.805 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 <cluster_contraction.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: cluster_contraction.py <cluster_contraction.py>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_
