.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/network/graphs/plot_02_small_world.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_network_graphs_plot_02_small_world.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_network_graphs_plot_02_small_world.py:


Small-world networks: a few shortcuts (Watts and Strogatz 1998)
===============================================================

A ring lattice, where each peer knows its nearest neighbors, is highly
clustered: your neighbors know each other. But messages crawl around it,
taking about ``n / 2k`` hops. Watts and Strogatz rewired each link to a
random peer with a small probability and found that a handful of shortcuts
collapses path lengths almost to those of a random graph while clustering
barely changes: a *small world*, like "six degrees of separation".

What to look for
----------------

On the log scale of the rewiring probability, the path length L falls long
before the clustering C does. Around 1% rewiring, paths are already short
and the network is still clustered. Gossip benefits directly: it crosses
the network in a few hops.

The history behind this experiment: :doc:`/history/network_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 24-26

Reproduce the 1998 figure
-------------------------

.. GENERATED FROM PYTHON SOURCE LINES 26-45

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    import blockchainkit as bk
    from blockchainkit.network.visualizers import plot_graph

    n, k = 400, 10
    lattice = bk.network.ring_lattice(n, k)
    L0, C0 = lattice.average_path_length(), lattice.clustering()
    betas = np.logspace(-4, 0, 13)
    L, C = [], []
    for beta in betas:
        g = bk.network.watts_strogatz(n, k, float(beta), seed=1)
        L.append(g.average_path_length() / L0)
        C.append(g.clustering() / C0)
    i = int(np.argmin(abs(betas - 0.01)))
    print(f"beta = {betas[i]:.3f}: L/L0 = {L[i]:.2f}, C/C0 = {C[i]:.2f}")
    assert L[i] < 0.5 and C[i] > 0.9





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    beta = 0.010: L/L0 = 0.42, C/C0 = 0.98




.. GENERATED FROM PYTHON SOURCE LINES 46-48

Gossip on the two graphs
------------------------

.. GENERATED FROM PYTHON SOURCE LINES 48-69

.. code-block:: Python

    rounds = {
        name: bk.network.spread_rumor(g, seed=2).rounds
        for name, g in [
            ("lattice", lattice),
            ("1% rewired", bk.network.watts_strogatz(n, k, 0.01, seed=1)),
        ]
    }
    print(rounds)
    assert rounds["1% rewired"] < 0.6 * rounds["lattice"]

    fig, (left, mid, right) = plt.subplots(1, 3, figsize=(12, 4))
    left.semilogx(betas, L, "o", label="L(p) / L(0)")
    left.semilogx(betas, C, "s", label="C(p) / C(0)")
    left.set(xlabel="rewiring probability p", title="Short paths, still clustered")
    left.legend()
    plot_graph(bk.network.ring_lattice(30, 4), ax=mid)
    plot_graph(bk.network.watts_strogatz(30, 4, 0.1, seed=3), ax=right)
    mid.set_title("lattice")
    right.set_title("10% rewired")
    fig.tight_layout()




.. image-sg:: /api/gallery/network/graphs/images/sphx_glr_plot_02_small_world_001.png
   :alt: Short paths, still clustered, lattice, 10% rewired
   :srcset: /api/gallery/network/graphs/images/sphx_glr_plot_02_small_world_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    {'lattice': 104, '1% rewired': 50}




.. GENERATED FROM PYTHON SOURCE LINES 70-76

Exercise
--------
Watts and Strogatz explained the gap with one shortcut: it cuts the path
between many pairs at once, but changes the clustering of only the two
nodes it touches. Check this by rewiring a single edge of the lattice by
hand and recomputing L and C.


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 1.399 seconds)


.. _sphx_glr_download_api_gallery_network_graphs_plot_02_small_world.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/network/graphs/plot_02_small_world.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_small_world.ipynb <plot_02_small_world.ipynb>`

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

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

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_small_world.zip <plot_02_small_world.zip>`


.. only:: html

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

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