.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/network/graphs/plot_01_random_graphs.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_01_random_graphs.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_01_random_graphs.py:


Random graphs and the connectivity threshold (Erdős and Rényi 1959)
===================================================================

If each pair of n peers is linked independently with probability p, when is
the whole network connected? Erdős and Rényi found a sharp threshold at
``p = ln n / n``: a little below it there are almost surely isolated peers,
a little above it the graph is almost surely connected. Each peer then needs
only about ``ln n`` random links, which is why Bitcoin's few random outbound
connections per node suffice to hold the network together.

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

The probability of being connected jumps from near 0 to near 1 over a narrow
range of ``p n / ln n`` around 1. Erdős and Rényi also gave the shape of the
jump: with ``p = c ln n / n``, the probability tends to ``exp(-n**(1 - c))``,
about ``1/e`` exactly at the threshold. Just below the threshold, what keeps
the graph disconnected is almost always a single isolated peer.

The history behind this experiment: :doc:`/history/network_breakthroughs`.
See :doc:`/exercises/network` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 26-28

Sweep p around ln n / n
-----------------------

.. GENERATED FROM PYTHON SOURCE LINES 28-52

.. code-block:: Python

    import math

    import matplotlib.pyplot as plt
    import numpy as np

    import blockchainkit as bk
    import blockchainkit.network.visualizers

    scales = np.linspace(0.4, 2.0, 17)
    curves = {}
    for n in (50, 400):
        curves[n] = [
            np.mean(
                [
                    bk.network.erdos_renyi(n, c * math.log(n) / n, seed=s).is_connected()
                    for s in range(30)
                ]
            )
            for c in scales
        ]
    assert curves[400][0] == 0 and curves[400][-1] == 1
    limit = np.exp(-(400.0 ** (1 - scales)))  # Erdős-Rényi's limit law for n = 400.
    assert np.max(np.abs(np.array(curves[400]) - limit)) < 0.25








.. GENERATED FROM PYTHON SOURCE LINES 53-56

What disconnects the graph?
---------------------------
Below the threshold, the second-largest component is usually one peer.

.. GENERATED FROM PYTHON SOURCE LINES 56-75

.. code-block:: Python

    n = 400
    small = []
    for s in range(30):
        g = bk.network.erdos_renyi(n, 0.8 * math.log(n) / n, seed=s)
        if not g.is_connected():
            small.append(len(g.components()[1]))
    print("size of the second-largest component:", sorted(small))
    assert np.mean([size == 1 for size in small]) > 0.8

    fig, (left, right) = plt.subplots(1, 2, figsize=(10, 4))
    for n, curve in curves.items():
        left.plot(scales, curve, marker="o", markersize=3, label=f"n = {n}")
    left.plot(scales, limit, color="black", label="exp(-n^(1-c)), n = 400")
    left.axvline(1, color="#94a3b8", linestyle="--")
    left.set(xlabel="p n / ln n", ylabel="P(connected)", title="A sharp threshold")
    left.legend()
    bk.network.visualizers.plot_graph(bk.network.erdos_renyi(60, 0.06, seed=2), ax=right)
    fig.tight_layout()




.. image-sg:: /api/gallery/network/graphs/images/sphx_glr_plot_01_random_graphs_001.png
   :alt: A sharp threshold, 60 peers, 103 links
   :srcset: /api/gallery/network/graphs/images/sphx_glr_plot_01_random_graphs_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    size of the second-largest component: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]




.. GENERATED FROM PYTHON SOURCE LINES 76-82

Exercise
--------
The expected number of isolated peers is ``n (1 - p)**(n - 1)``, close to
``n exp(-p n)``. Evaluate it at ``p = c ln n / n`` and explain why c = 1
is the threshold. If the number of isolated peers is roughly Poisson,
where does the limit law ``exp(-n**(1 - c))`` come from?


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

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


.. _sphx_glr_download_api_gallery_network_graphs_plot_01_random_graphs.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_01_random_graphs.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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