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

.. only:: html

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

        :ref:`Go to the end <sphx_glr_download_examples_random_walk.py>`
        to download the full example code.

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

.. _sphx_glr_examples_random_walk.py:


Random walks.
============

Probability of a random walker to be on any given vertex after a given number
of steps starting from a given distribution.

.. GENERATED FROM PYTHON SOURCE LINES 8-34

.. code-block:: Python


    # sphinx_gallery_thumbnail_number = 2

    import numpy as np
    from matplotlib import pyplot as plt
    from scipy import sparse

    import pygsp2 as pg

    N = 7
    steps = [0, 1, 2, 3]

    graph = pg.graphs.Grid2d(N)
    delta = np.zeros(graph.N)
    delta[N // 2 * N + N // 2] = 1

    probability = sparse.diags(graph.dw**(-1)).dot(graph.W)

    fig, axes = plt.subplots(1, len(steps), figsize=(12, 3))
    for step, ax in zip(steps, axes):
        state = (probability**step).__rmatmul__(delta)  ## = delta @ probability**step
        graph.plot(state, ax=ax, title=r'$\delta P^{}$'.format(step))
        ax.set_axis_off()

    fig.tight_layout()




.. image-sg:: /examples/images/sphx_glr_random_walk_001.png
   :alt: $\delta P^0$, $\delta P^1$, $\delta P^2$, $\delta P^3$
   :srcset: /examples/images/sphx_glr_random_walk_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 35-36

Stationary distribution.

.. GENERATED FROM PYTHON SOURCE LINES 36-70

.. code-block:: Python


    graphs = [
        pg.graphs.Ring(10),
        pg.graphs.Grid2d(5),
        pg.graphs.Comet(8, 4),
        pg.graphs.BarabasiAlbert(20, seed=42),
    ]

    fig, axes = plt.subplots(1, len(graphs), figsize=(12, 3))

    for graph, ax in zip(graphs, axes):

        if not hasattr(graph, 'coords'):
            graph.set_coordinates(seed=10)

        P = sparse.diags(graph.dw**(-1)).dot(graph.W)

        #    e, u = np.linalg.eig(P.T.toarray())
        #    np.testing.assert_allclose(np.linalg.inv(u.T) @ np.diag(e) @ u.T,
        #                               P.toarray(), atol=1e-10)
        #    np.testing.assert_allclose(np.abs(e[0]), 1)
        #    stationary = np.abs(u.T[0])

        e, u = sparse.linalg.eigs(P.T, k=1, which='LR')
        np.testing.assert_allclose(e, 1)
        stationary = np.abs(u).squeeze()
        assert np.all(stationary < 0.71)

        colorbar = False if type(graph) is pg.graphs.Ring else True
        graph.plot(stationary, colorbar=colorbar, ax=ax, title='$xP = x$')
        ax.set_axis_off()

    fig.tight_layout()
    plt.show()



.. image-sg:: /examples/images/sphx_glr_random_walk_002.png
   :alt: $xP = x$, $xP = x$, $xP = x$, $xP = x$
   :srcset: /examples/images/sphx_glr_random_walk_002.png
   :class: sphx-glr-single-img






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

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

**Estimated memory usage:**  178 MB


.. _sphx_glr_download_examples_random_walk.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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