Generative Models for Random Graphs¶

Prerequisites¶

First, we need to set up our Python environment that has PyTorch, PyTorch Geometric and PathpyG installed. Depending on where you are executing this notebook, this might already be (partially) done. E.g. Google Colab has PyTorch installed by default so we only need to install the remaining dependencies. The DevContainer that is part of our GitHub Repository on the other hand already has all of the necessary dependencies installed.

In the following, we install the packages for usage in Google Colab using Jupyter magic commands. For other environments comment in or out the commands as necessary. For more details on how to install pathpyG especially if you want to install it with GPU-support, we refer to our documentation. Note that %%capture discards the full output of the cell to not clutter this tutorial with unnecessary installation details. If you want to print the output, you can comment %%capture out.

In [53]:

import pathpyG as pp
import string 
import numpy as np

import pathpyG as pp import string import numpy as np

pathpyG provides implementations for several basic generative models for random graphs, such as different variants of the Erdös-Renyi model for random graphs, the Molloy-Reed configuration model for random graphs with given degree sequence or distribution, or the Watts-Strogatz models for small-world graphs.

These models are implemented in the module pathpyG.algorithms.generative_models.

To generate a random Erdös-Renyi graph using the so-called $G(n,p)$ model where $n$ is the number of nodes and $p$ is the probability for each node pair to be connected, we can call:

In [7]:

g = pp.algorithms.generative_models.erdos_renyi_gnp(n=20, p=0.2)
pp.plot(g);

g = pp.algorithms.generative_models.erdos_renyi_gnp(n=20, p=0.2) pp.plot(g);

{'edges': [{'uid': '0-12', 'source': '0', 'target': '12', 'weight': 1}, {'uid': '1-14', 'source': '1', 'target': '14', 'weight': 1}, {'uid': '1-17', 'source': '1', 'target': '17', 'weight': 1}, {'uid': '1-12', 'source': '1', 'target': '12', 'weight': 1}, {'uid': '1-5', 'source': '1', 'target': '5', 'weight': 1}, {'uid': '1-11', 'source': '1', 'target': '11', 'weight': 1}, {'uid': '1-7', 'source': '1', 'target': '7', 'weight': 1}, {'uid': '2-6', 'source': '2', 'target': '6', 'weight': 1}, {'uid': '2-12', 'source': '2', 'target': '12', 'weight': 1}, {'uid': '2-10', 'source': '2', 'target': '10', 'weight': 1}, {'uid': '2-13', 'source': '2', 'target': '13', 'weight': 1}, {'uid': '3-8', 'source': '3', 'target': '8', 'weight': 1}, {'uid': '3-14', 'source': '3', 'target': '14', 'weight': 1}, {'uid': '4-17', 'source': '4', 'target': '17', 'weight': 1}, {'uid': '4-19', 'source': '4', 'target': '19', 'weight': 1}, {'uid': '4-11', 'source': '4', 'target': '11', 'weight': 1}, {'uid': '5-8', 'source': '5', 'target': '8', 'weight': 1}, {'uid': '5-19', 'source': '5', 'target': '19', 'weight': 1}, {'uid': '5-1', 'source': '5', 'target': '1', 'weight': 1}, {'uid': '5-14', 'source': '5', 'target': '14', 'weight': 1}, {'uid': '5-18', 'source': '5', 'target': '18', 'weight': 1}, {'uid': '5-17', 'source': '5', 'target': '17', 'weight': 1}, {'uid': '5-15', 'source': '5', 'target': '15', 'weight': 1}, {'uid': '6-11', 'source': '6', 'target': '11', 'weight': 1}, {'uid': '6-15', 'source': '6', 'target': '15', 'weight': 1}, {'uid': '6-13', 'source': '6', 'target': '13', 'weight': 1}, {'uid': '6-2', 'source': '6', 'target': '2', 'weight': 1}, {'uid': '6-12', 'source': '6', 'target': '12', 'weight': 1}, {'uid': '6-14', 'source': '6', 'target': '14', 'weight': 1}, {'uid': '7-19', 'source': '7', 'target': '19', 'weight': 1}, {'uid': '7-8', 'source': '7', 'target': '8', 'weight': 1}, {'uid': '7-1', 'source': '7', 'target': '1', 'weight': 1}, {'uid': '7-17', 'source': '7', 'target': '17', 'weight': 1}, {'uid': '7-12', 'source': '7', 'target': '12', 'weight': 1}, {'uid': '7-15', 'source': '7', 'target': '15', 'weight': 1}, {'uid': '8-5', 'source': '8', 'target': '5', 'weight': 1}, {'uid': '8-7', 'source': '8', 'target': '7', 'weight': 1}, {'uid': '8-9', 'source': '8', 'target': '9', 'weight': 1}, {'uid': '8-3', 'source': '8', 'target': '3', 'weight': 1}, {'uid': '9-8', 'source': '9', 'target': '8', 'weight': 1}, {'uid': '10-17', 'source': '10', 'target': '17', 'weight': 1}, {'uid': '10-18', 'source': '10', 'target': '18', 'weight': 1}, {'uid': '10-2', 'source': '10', 'target': '2', 'weight': 1}, {'uid': '10-11', 'source': '10', 'target': '11', 'weight': 1}, {'uid': '11-1', 'source': '11', 'target': '1', 'weight': 1}, {'uid': '11-13', 'source': '11', 'target': '13', 'weight': 1}, {'uid': '11-4', 'source': '11', 'target': '4', 'weight': 1}, {'uid': '11-10', 'source': '11', 'target': '10', 'weight': 1}, {'uid': '11-6', 'source': '11', 'target': '6', 'weight': 1}, {'uid': '12-16', 'source': '12', 'target': '16', 'weight': 1}, {'uid': '12-2', 'source': '12', 'target': '2', 'weight': 1}, {'uid': '12-1', 'source': '12', 'target': '1', 'weight': 1}, {'uid': '12-7', 'source': '12', 'target': '7', 'weight': 1}, {'uid': '12-6', 'source': '12', 'target': '6', 'weight': 1}, {'uid': '12-0', 'source': '12', 'target': '0', 'weight': 1}, {'uid': '12-13', 'source': '12', 'target': '13', 'weight': 1}, {'uid': '13-16', 'source': '13', 'target': '16', 'weight': 1}, {'uid': '13-6', 'source': '13', 'target': '6', 'weight': 1}, {'uid': '13-11', 'source': '13', 'target': '11', 'weight': 1}, {'uid': '13-12', 'source': '13', 'target': '12', 'weight': 1}, {'uid': '13-2', 'source': '13', 'target': '2', 'weight': 1}, {'uid': '14-3', 'source': '14', 'target': '3', 'weight': 1}, {'uid': '14-1', 'source': '14', 'target': '1', 'weight': 1}, {'uid': '14-6', 'source': '14', 'target': '6', 'weight': 1}, {'uid': '14-5', 'source': '14', 'target': '5', 'weight': 1}, {'uid': '15-6', 'source': '15', 'target': '6', 'weight': 1}, {'uid': '15-5', 'source': '15', 'target': '5', 'weight': 1}, {'uid': '15-16', 'source': '15', 'target': '16', 'weight': 1}, {'uid': '15-7', 'source': '15', 'target': '7', 'weight': 1}, {'uid': '16-12', 'source': '16', 'target': '12', 'weight': 1}, {'uid': '16-15', 'source': '16', 'target': '15', 'weight': 1}, {'uid': '16-13', 'source': '16', 'target': '13', 'weight': 1}, {'uid': '17-1', 'source': '17', 'target': '1', 'weight': 1}, {'uid': '17-7', 'source': '17', 'target': '7', 'weight': 1}, {'uid': '17-5', 'source': '17', 'target': '5', 'weight': 1}, {'uid': '17-10', 'source': '17', 'target': '10', 'weight': 1}, {'uid': '17-4', 'source': '17', 'target': '4', 'weight': 1}, {'uid': '18-10', 'source': '18', 'target': '10', 'weight': 1}, {'uid': '18-5', 'source': '18', 'target': '5', 'weight': 1}, {'uid': '19-5', 'source': '19', 'target': '5', 'weight': 1}, {'uid': '19-4', 'source': '19', 'target': '4', 'weight': 1}, {'uid': '19-7', 'source': '19', 'target': '7', 'weight': 1}], 'nodes': [{'uid': '0'}, {'uid': '1'}, {'uid': '2'}, {'uid': '3'}, {'uid': '4'}, {'uid': '5'}, {'uid': '6'}, {'uid': '7'}, {'uid': '8'}, {'uid': '9'}, {'uid': '10'}, {'uid': '11'}, {'uid': '12'}, {'uid': '13'}, {'uid': '14'}, {'uid': '15'}, {'uid': '16'}, {'uid': '17'}, {'uid': '18'}, {'uid': '19'}]}

By default, no self-loops are added. If we want self-loops to be generated with probability $p$ we can do this as follows (note that self-loops are currently not plotted):

In [10]:

g = pp.algorithms.generative_models.erdos_renyi_gnp(n=20, p=0.2, self_loops=True)
pp.plot(g);

g = pp.algorithms.generative_models.erdos_renyi_gnp(n=20, p=0.2, self_loops=True) pp.plot(g);

{'edges': [{'uid': '0-8', 'source': '0', 'target': '8', 'weight': 1}, {'uid': '0-17', 'source': '0', 'target': '17', 'weight': 1}, {'uid': '0-4', 'source': '0', 'target': '4', 'weight': 1}, {'uid': '1-1', 'source': '1', 'target': '1', 'weight': 1}, {'uid': '1-17', 'source': '1', 'target': '17', 'weight': 1}, {'uid': '1-9', 'source': '1', 'target': '9', 'weight': 1}, {'uid': '1-14', 'source': '1', 'target': '14', 'weight': 1}, {'uid': '2-14', 'source': '2', 'target': '14', 'weight': 1}, {'uid': '2-3', 'source': '2', 'target': '3', 'weight': 1}, {'uid': '2-8', 'source': '2', 'target': '8', 'weight': 1}, {'uid': '2-7', 'source': '2', 'target': '7', 'weight': 1}, {'uid': '3-9', 'source': '3', 'target': '9', 'weight': 1}, {'uid': '3-18', 'source': '3', 'target': '18', 'weight': 1}, {'uid': '3-8', 'source': '3', 'target': '8', 'weight': 1}, {'uid': '3-11', 'source': '3', 'target': '11', 'weight': 1}, {'uid': '3-2', 'source': '3', 'target': '2', 'weight': 1}, {'uid': '3-19', 'source': '3', 'target': '19', 'weight': 1}, {'uid': '3-16', 'source': '3', 'target': '16', 'weight': 1}, {'uid': '4-0', 'source': '4', 'target': '0', 'weight': 1}, {'uid': '4-7', 'source': '4', 'target': '7', 'weight': 1}, {'uid': '5-17', 'source': '5', 'target': '17', 'weight': 1}, {'uid': '5-7', 'source': '5', 'target': '7', 'weight': 1}, {'uid': '5-18', 'source': '5', 'target': '18', 'weight': 1}, {'uid': '6-16', 'source': '6', 'target': '16', 'weight': 1}, {'uid': '7-5', 'source': '7', 'target': '5', 'weight': 1}, {'uid': '7-16', 'source': '7', 'target': '16', 'weight': 1}, {'uid': '7-4', 'source': '7', 'target': '4', 'weight': 1}, {'uid': '7-2', 'source': '7', 'target': '2', 'weight': 1}, {'uid': '8-2', 'source': '8', 'target': '2', 'weight': 1}, {'uid': '8-14', 'source': '8', 'target': '14', 'weight': 1}, {'uid': '8-19', 'source': '8', 'target': '19', 'weight': 1}, {'uid': '8-0', 'source': '8', 'target': '0', 'weight': 1}, {'uid': '8-3', 'source': '8', 'target': '3', 'weight': 1}, {'uid': '9-17', 'source': '9', 'target': '17', 'weight': 1}, {'uid': '9-3', 'source': '9', 'target': '3', 'weight': 1}, {'uid': '9-19', 'source': '9', 'target': '19', 'weight': 1}, {'uid': '9-1', 'source': '9', 'target': '1', 'weight': 1}, {'uid': '9-15', 'source': '9', 'target': '15', 'weight': 1}, {'uid': '10-13', 'source': '10', 'target': '13', 'weight': 1}, {'uid': '10-10', 'source': '10', 'target': '10', 'weight': 1}, {'uid': '11-13', 'source': '11', 'target': '13', 'weight': 1}, {'uid': '11-12', 'source': '11', 'target': '12', 'weight': 1}, {'uid': '11-3', 'source': '11', 'target': '3', 'weight': 1}, {'uid': '12-11', 'source': '12', 'target': '11', 'weight': 1}, {'uid': '12-15', 'source': '12', 'target': '15', 'weight': 1}, {'uid': '12-17', 'source': '12', 'target': '17', 'weight': 1}, {'uid': '13-11', 'source': '13', 'target': '11', 'weight': 1}, {'uid': '13-18', 'source': '13', 'target': '18', 'weight': 1}, {'uid': '13-16', 'source': '13', 'target': '16', 'weight': 1}, {'uid': '13-15', 'source': '13', 'target': '15', 'weight': 1}, {'uid': '13-19', 'source': '13', 'target': '19', 'weight': 1}, {'uid': '13-10', 'source': '13', 'target': '10', 'weight': 1}, {'uid': '14-1', 'source': '14', 'target': '1', 'weight': 1}, {'uid': '14-2', 'source': '14', 'target': '2', 'weight': 1}, {'uid': '14-8', 'source': '14', 'target': '8', 'weight': 1}, {'uid': '15-13', 'source': '15', 'target': '13', 'weight': 1}, {'uid': '15-9', 'source': '15', 'target': '9', 'weight': 1}, {'uid': '15-19', 'source': '15', 'target': '19', 'weight': 1}, {'uid': '15-12', 'source': '15', 'target': '12', 'weight': 1}, {'uid': '16-7', 'source': '16', 'target': '7', 'weight': 1}, {'uid': '16-6', 'source': '16', 'target': '6', 'weight': 1}, {'uid': '16-3', 'source': '16', 'target': '3', 'weight': 1}, {'uid': '16-16', 'source': '16', 'target': '16', 'weight': 1}, {'uid': '16-13', 'source': '16', 'target': '13', 'weight': 1}, {'uid': '17-12', 'source': '17', 'target': '12', 'weight': 1}, {'uid': '17-5', 'source': '17', 'target': '5', 'weight': 1}, {'uid': '17-9', 'source': '17', 'target': '9', 'weight': 1}, {'uid': '17-1', 'source': '17', 'target': '1', 'weight': 1}, {'uid': '17-0', 'source': '17', 'target': '0', 'weight': 1}, {'uid': '18-5', 'source': '18', 'target': '5', 'weight': 1}, {'uid': '18-13', 'source': '18', 'target': '13', 'weight': 1}, {'uid': '18-3', 'source': '18', 'target': '3', 'weight': 1}, {'uid': '19-13', 'source': '19', 'target': '13', 'weight': 1}, {'uid': '19-3', 'source': '19', 'target': '3', 'weight': 1}, {'uid': '19-15', 'source': '19', 'target': '15', 'weight': 1}, {'uid': '19-9', 'source': '19', 'target': '9', 'weight': 1}, {'uid': '19-8', 'source': '19', 'target': '8', 'weight': 1}], 'nodes': [{'uid': '0'}, {'uid': '1'}, {'uid': '2'}, {'uid': '3'}, {'uid': '4'}, {'uid': '5'}, {'uid': '6'}, {'uid': '7'}, {'uid': '8'}, {'uid': '9'}, {'uid': '10'}, {'uid': '11'}, {'uid': '12'}, {'uid': '13'}, {'uid': '14'}, {'uid': '15'}, {'uid': '16'}, {'uid': '17'}, {'uid': '18'}, {'uid': '19'}]}

This also works for directed networks and we can specify a given node ID mapping:

In [18]:

g = pp.algorithms.generative_models.erdos_renyi_gnp(n=20, 
                                                    p=0.2, directed=True, mapping=pp.IndexMap([x for x in string.ascii_lowercase]))
pp.plot(g, node_label = g.nodes);

g = pp.algorithms.generative_models.erdos_renyi_gnp(n=20, p=0.2, directed=True, mapping=pp.IndexMap([x for x in string.ascii_lowercase])) pp.plot(g, node_label = g.nodes);

{'edges': [{'uid': 'a-d', 'source': 'a', 'target': 'd', 'weight': 1}, {'uid': 'a-n', 'source': 'a', 'target': 'n', 'weight': 1}, {'uid': 'a-e', 'source': 'a', 'target': 'e', 'weight': 1}, {'uid': 'b-g', 'source': 'b', 'target': 'g', 'weight': 1}, {'uid': 'b-n', 'source': 'b', 'target': 'n', 'weight': 1}, {'uid': 'c-n', 'source': 'c', 'target': 'n', 'weight': 1}, {'uid': 'c-o', 'source': 'c', 'target': 'o', 'weight': 1}, {'uid': 'c-t', 'source': 'c', 'target': 't', 'weight': 1}, {'uid': 'c-j', 'source': 'c', 'target': 'j', 'weight': 1}, {'uid': 'c-l', 'source': 'c', 'target': 'l', 'weight': 1}, {'uid': 'c-q', 'source': 'c', 'target': 'q', 'weight': 1}, {'uid': 'c-s', 'source': 'c', 'target': 's', 'weight': 1}, {'uid': 'c-m', 'source': 'c', 'target': 'm', 'weight': 1}, {'uid': 'd-b', 'source': 'd', 'target': 'b', 'weight': 1}, {'uid': 'd-j', 'source': 'd', 'target': 'j', 'weight': 1}, {'uid': 'd-l', 'source': 'd', 'target': 'l', 'weight': 1}, {'uid': 'd-t', 'source': 'd', 'target': 't', 'weight': 1}, {'uid': 'e-h', 'source': 'e', 'target': 'h', 'weight': 1}, {'uid': 'e-s', 'source': 'e', 'target': 's', 'weight': 1}, {'uid': 'e-l', 'source': 'e', 'target': 'l', 'weight': 1}, {'uid': 'e-i', 'source': 'e', 'target': 'i', 'weight': 1}, {'uid': 'e-m', 'source': 'e', 'target': 'm', 'weight': 1}, {'uid': 'e-q', 'source': 'e', 'target': 'q', 'weight': 1}, {'uid': 'f-t', 'source': 'f', 'target': 't', 'weight': 1}, {'uid': 'f-o', 'source': 'f', 'target': 'o', 'weight': 1}, {'uid': 'g-l', 'source': 'g', 'target': 'l', 'weight': 1}, {'uid': 'g-m', 'source': 'g', 'target': 'm', 'weight': 1}, {'uid': 'g-c', 'source': 'g', 'target': 'c', 'weight': 1}, {'uid': 'g-a', 'source': 'g', 'target': 'a', 'weight': 1}, {'uid': 'h-e', 'source': 'h', 'target': 'e', 'weight': 1}, {'uid': 'h-n', 'source': 'h', 'target': 'n', 'weight': 1}, {'uid': 'h-m', 'source': 'h', 'target': 'm', 'weight': 1}, {'uid': 'i-f', 'source': 'i', 'target': 'f', 'weight': 1}, {'uid': 'i-k', 'source': 'i', 'target': 'k', 'weight': 1}, {'uid': 'i-j', 'source': 'i', 'target': 'j', 'weight': 1}, {'uid': 'j-s', 'source': 'j', 'target': 's', 'weight': 1}, {'uid': 'j-r', 'source': 'j', 'target': 'r', 'weight': 1}, {'uid': 'j-l', 'source': 'j', 'target': 'l', 'weight': 1}, {'uid': 'k-r', 'source': 'k', 'target': 'r', 'weight': 1}, {'uid': 'k-l', 'source': 'k', 'target': 'l', 'weight': 1}, {'uid': 'k-h', 'source': 'k', 'target': 'h', 'weight': 1}, {'uid': 'k-c', 'source': 'k', 'target': 'c', 'weight': 1}, {'uid': 'k-n', 'source': 'k', 'target': 'n', 'weight': 1}, {'uid': 'k-t', 'source': 'k', 'target': 't', 'weight': 1}, {'uid': 'k-e', 'source': 'k', 'target': 'e', 'weight': 1}, {'uid': 'l-d', 'source': 'l', 'target': 'd', 'weight': 1}, {'uid': 'l-b', 'source': 'l', 'target': 'b', 'weight': 1}, {'uid': 'l-o', 'source': 'l', 'target': 'o', 'weight': 1}, {'uid': 'l-c', 'source': 'l', 'target': 'c', 'weight': 1}, {'uid': 'm-e', 'source': 'm', 'target': 'e', 'weight': 1}, {'uid': 'm-s', 'source': 'm', 'target': 's', 'weight': 1}, {'uid': 'm-a', 'source': 'm', 'target': 'a', 'weight': 1}, {'uid': 'm-i', 'source': 'm', 'target': 'i', 'weight': 1}, {'uid': 'n-e', 'source': 'n', 'target': 'e', 'weight': 1}, {'uid': 'n-i', 'source': 'n', 'target': 'i', 'weight': 1}, {'uid': 'o-a', 'source': 'o', 'target': 'a', 'weight': 1}, {'uid': 'o-p', 'source': 'o', 'target': 'p', 'weight': 1}, {'uid': 'p-r', 'source': 'p', 'target': 'r', 'weight': 1}, {'uid': 'p-q', 'source': 'p', 'target': 'q', 'weight': 1}, {'uid': 'p-h', 'source': 'p', 'target': 'h', 'weight': 1}, {'uid': 'p-d', 'source': 'p', 'target': 'd', 'weight': 1}, {'uid': 'p-s', 'source': 'p', 'target': 's', 'weight': 1}, {'uid': 'p-a', 'source': 'p', 'target': 'a', 'weight': 1}, {'uid': 'q-b', 'source': 'q', 'target': 'b', 'weight': 1}, {'uid': 'q-m', 'source': 'q', 'target': 'm', 'weight': 1}, {'uid': 'q-j', 'source': 'q', 'target': 'j', 'weight': 1}, {'uid': 'q-h', 'source': 'q', 'target': 'h', 'weight': 1}, {'uid': 'q-e', 'source': 'q', 'target': 'e', 'weight': 1}, {'uid': 'q-l', 'source': 'q', 'target': 'l', 'weight': 1}, {'uid': 'r-e', 'source': 'r', 'target': 'e', 'weight': 1}, {'uid': 'r-l', 'source': 'r', 'target': 'l', 'weight': 1}, {'uid': 's-m', 'source': 's', 'target': 'm', 'weight': 1}, {'uid': 's-o', 'source': 's', 'target': 'o', 'weight': 1}, {'uid': 's-f', 'source': 's', 'target': 'f', 'weight': 1}, {'uid': 's-h', 'source': 's', 'target': 'h', 'weight': 1}, {'uid': 't-l', 'source': 't', 'target': 'l', 'weight': 1}, {'uid': 't-b', 'source': 't', 'target': 'b', 'weight': 1}, {'uid': 't-i', 'source': 't', 'target': 'i', 'weight': 1}, {'uid': 't-g', 'source': 't', 'target': 'g', 'weight': 1}], 'nodes': [{'uid': 'a', 'label': 'a'}, {'uid': 'b', 'label': 'b'}, {'uid': 'c', 'label': 'c'}, {'uid': 'd', 'label': 'd'}, {'uid': 'e', 'label': 'e'}, {'uid': 'f', 'label': 'f'}, {'uid': 'g', 'label': 'g'}, {'uid': 'h', 'label': 'h'}, {'uid': 'i', 'label': 'i'}, {'uid': 'j', 'label': 'j'}, {'uid': 'k', 'label': 'k'}, {'uid': 'l', 'label': 'l'}, {'uid': 'm', 'label': 'm'}, {'uid': 'n', 'label': 'n'}, {'uid': 'o', 'label': 'o'}, {'uid': 'p', 'label': 'p'}, {'uid': 'q', 'label': 'q'}, {'uid': 'r', 'label': 'r'}, {'uid': 's', 'label': 's'}, {'uid': 't', 'label': 't'}]}

For the random realizations generated by the $G(n,p)$ model with connection probability $p$, we have an expected number of $p \cdot \binom{n}{2}$ edges, i.e. the number of edges in each realization varies.

We can use the alternative $G(n,m)$ formulation of the Erdös-Renyi model, which generates a fixed number of $m$ edges chosen uniformly at random:

In [20]:

g = pp.algorithms.generative_models.erdos_renyi_gnm(n=20, 
                                                    m=40, mapping=pp.IndexMap([x for x in string.ascii_lowercase]))
print(g)
pp.plot(g, node_label = g.nodes);

g = pp.algorithms.generative_models.erdos_renyi_gnm(n=20, m=40, mapping=pp.IndexMap([x for x in string.ascii_lowercase])) print(g) pp.plot(g, node_label = g.nodes);

Undirected graph with 20 nodes and 80 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
{'edges': [{'uid': 'a-f', 'source': 'a', 'target': 'f', 'weight': 1}, {'uid': 'a-h', 'source': 'a', 'target': 'h', 'weight': 1}, {'uid': 'a-k', 'source': 'a', 'target': 'k', 'weight': 1}, {'uid': 'b-q', 'source': 'b', 'target': 'q', 'weight': 1}, {'uid': 'b-j', 'source': 'b', 'target': 'j', 'weight': 1}, {'uid': 'b-r', 'source': 'b', 'target': 'r', 'weight': 1}, {'uid': 'c-q', 'source': 'c', 'target': 'q', 'weight': 1}, {'uid': 'd-s', 'source': 'd', 'target': 's', 'weight': 1}, {'uid': 'd-j', 'source': 'd', 'target': 'j', 'weight': 1}, {'uid': 'd-k', 'source': 'd', 'target': 'k', 'weight': 1}, {'uid': 'd-q', 'source': 'd', 'target': 'q', 'weight': 1}, {'uid': 'd-n', 'source': 'd', 'target': 'n', 'weight': 1}, {'uid': 'd-i', 'source': 'd', 'target': 'i', 'weight': 1}, {'uid': 'd-e', 'source': 'd', 'target': 'e', 'weight': 1}, {'uid': 'e-m', 'source': 'e', 'target': 'm', 'weight': 1}, {'uid': 'e-t', 'source': 'e', 'target': 't', 'weight': 1}, {'uid': 'e-d', 'source': 'e', 'target': 'd', 'weight': 1}, {'uid': 'e-l', 'source': 'e', 'target': 'l', 'weight': 1}, {'uid': 'f-s', 'source': 'f', 'target': 's', 'weight': 1}, {'uid': 'f-g', 'source': 'f', 'target': 'g', 'weight': 1}, {'uid': 'f-r', 'source': 'f', 'target': 'r', 'weight': 1}, {'uid': 'f-a', 'source': 'f', 'target': 'a', 'weight': 1}, {'uid': 'g-s', 'source': 'g', 'target': 's', 'weight': 1}, {'uid': 'g-j', 'source': 'g', 'target': 'j', 'weight': 1}, {'uid': 'g-r', 'source': 'g', 'target': 'r', 'weight': 1}, {'uid': 'g-n', 'source': 'g', 'target': 'n', 'weight': 1}, {'uid': 'g-f', 'source': 'g', 'target': 'f', 'weight': 1}, {'uid': 'h-n', 'source': 'h', 'target': 'n', 'weight': 1}, {'uid': 'h-a', 'source': 'h', 'target': 'a', 'weight': 1}, {'uid': 'h-r', 'source': 'h', 'target': 'r', 'weight': 1}, {'uid': 'i-p', 'source': 'i', 'target': 'p', 'weight': 1}, {'uid': 'i-k', 'source': 'i', 'target': 'k', 'weight': 1}, {'uid': 'i-n', 'source': 'i', 'target': 'n', 'weight': 1}, {'uid': 'i-d', 'source': 'i', 'target': 'd', 'weight': 1}, {'uid': 'i-l', 'source': 'i', 'target': 'l', 'weight': 1}, {'uid': 'j-g', 'source': 'j', 'target': 'g', 'weight': 1}, {'uid': 'j-d', 'source': 'j', 'target': 'd', 'weight': 1}, {'uid': 'j-b', 'source': 'j', 'target': 'b', 'weight': 1}, {'uid': 'j-o', 'source': 'j', 'target': 'o', 'weight': 1}, {'uid': 'k-t', 'source': 'k', 'target': 't', 'weight': 1}, {'uid': 'k-r', 'source': 'k', 'target': 'r', 'weight': 1}, {'uid': 'k-a', 'source': 'k', 'target': 'a', 'weight': 1}, {'uid': 'k-i', 'source': 'k', 'target': 'i', 'weight': 1}, {'uid': 'k-d', 'source': 'k', 'target': 'd', 'weight': 1}, {'uid': 'l-e', 'source': 'l', 'target': 'e', 'weight': 1}, {'uid': 'l-o', 'source': 'l', 'target': 'o', 'weight': 1}, {'uid': 'l-n', 'source': 'l', 'target': 'n', 'weight': 1}, {'uid': 'l-i', 'source': 'l', 'target': 'i', 'weight': 1}, {'uid': 'l-p', 'source': 'l', 'target': 'p', 'weight': 1}, {'uid': 'm-o', 'source': 'm', 'target': 'o', 'weight': 1}, {'uid': 'm-e', 'source': 'm', 'target': 'e', 'weight': 1}, {'uid': 'm-p', 'source': 'm', 'target': 'p', 'weight': 1}, {'uid': 'n-r', 'source': 'n', 'target': 'r', 'weight': 1}, {'uid': 'n-i', 'source': 'n', 'target': 'i', 'weight': 1}, {'uid': 'n-d', 'source': 'n', 'target': 'd', 'weight': 1}, {'uid': 'n-g', 'source': 'n', 'target': 'g', 'weight': 1}, {'uid': 'n-l', 'source': 'n', 'target': 'l', 'weight': 1}, {'uid': 'n-h', 'source': 'n', 'target': 'h', 'weight': 1}, {'uid': 'o-j', 'source': 'o', 'target': 'j', 'weight': 1}, {'uid': 'o-m', 'source': 'o', 'target': 'm', 'weight': 1}, {'uid': 'o-l', 'source': 'o', 'target': 'l', 'weight': 1}, {'uid': 'p-l', 'source': 'p', 'target': 'l', 'weight': 1}, {'uid': 'p-i', 'source': 'p', 'target': 'i', 'weight': 1}, {'uid': 'p-m', 'source': 'p', 'target': 'm', 'weight': 1}, {'uid': 'q-r', 'source': 'q', 'target': 'r', 'weight': 1}, {'uid': 'q-c', 'source': 'q', 'target': 'c', 'weight': 1}, {'uid': 'q-d', 'source': 'q', 'target': 'd', 'weight': 1}, {'uid': 'q-b', 'source': 'q', 'target': 'b', 'weight': 1}, {'uid': 'r-f', 'source': 'r', 'target': 'f', 'weight': 1}, {'uid': 'r-h', 'source': 'r', 'target': 'h', 'weight': 1}, {'uid': 'r-g', 'source': 'r', 'target': 'g', 'weight': 1}, {'uid': 'r-q', 'source': 'r', 'target': 'q', 'weight': 1}, {'uid': 'r-n', 'source': 'r', 'target': 'n', 'weight': 1}, {'uid': 'r-k', 'source': 'r', 'target': 'k', 'weight': 1}, {'uid': 'r-b', 'source': 'r', 'target': 'b', 'weight': 1}, {'uid': 's-d', 'source': 's', 'target': 'd', 'weight': 1}, {'uid': 's-g', 'source': 's', 'target': 'g', 'weight': 1}, {'uid': 's-f', 'source': 's', 'target': 'f', 'weight': 1}, {'uid': 't-k', 'source': 't', 'target': 'k', 'weight': 1}, {'uid': 't-e', 'source': 't', 'target': 'e', 'weight': 1}], 'nodes': [{'uid': 'a', 'label': 'a'}, {'uid': 'b', 'label': 'b'}, {'uid': 'c', 'label': 'c'}, {'uid': 'd', 'label': 'd'}, {'uid': 'e', 'label': 'e'}, {'uid': 'f', 'label': 'f'}, {'uid': 'g', 'label': 'g'}, {'uid': 'h', 'label': 'h'}, {'uid': 'i', 'label': 'i'}, {'uid': 'j', 'label': 'j'}, {'uid': 'k', 'label': 'k'}, {'uid': 'l', 'label': 'l'}, {'uid': 'm', 'label': 'm'}, {'uid': 'n', 'label': 'n'}, {'uid': 'o', 'label': 'o'}, {'uid': 'p', 'label': 'p'}, {'uid': 'q', 'label': 'q'}, {'uid': 'r', 'label': 'r'}, {'uid': 's', 'label': 's'}, {'uid': 't', 'label': 't'}]}

Naturally, the maximum number of edges that we can create depends on the size of the graph (and whether edges are directed and whether we allow for self-loops). The following fails:

In [24]:

g = pp.algorithms.generative_models.erdos_renyi_gnm(n=20, 
                                                    m=195, mapping=pp.IndexMap([x for x in string.ascii_lowercase]))
print(g)
pp.plot(g, node_label = g.nodes);

g = pp.algorithms.generative_models.erdos_renyi_gnm(n=20, m=195, mapping=pp.IndexMap([x for x in string.ascii_lowercase])) print(g) pp.plot(g, node_label = g.nodes);

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[24], line 1
----> 1 g = pp.algorithms.generative_models.erdos_renyi_gnm(n=20, 
      2                                                     m=195, mapping=pp.IndexMap([x for x in string.ascii_lowercase]))
      3 print(g)
      4 pp.plot(g, node_label = g.nodes)

File /workspaces/pathpyG/src/pathpyG/algorithms/generative_models.py:85, in erdos_renyi_gnm(n, m, mapping, self_loops, multi_edges, directed)
     69 def erdos_renyi_gnm(n: int, m: int, mapping: IndexMap | None = None,
     70                     self_loops: bool = False, multi_edges: bool = False,
     71                     directed: bool = False) -> Graph:
     72     """Generate a random graph with n nodes and m edges based on the G(n,m) model by Pal Eröds and Alfred Renyi.
     73 
     74     Args:
   (...)
     83         Graph: graph object
     84     """
---> 85     assert m <= max_edges(n, directed=directed, self_loops=self_loops, multi_edges=multi_edges)
     87     edges = set()
     88     edges_added: int = 0

AssertionError: 

To check how many edges a directed/undirected graph with/without self-loop can possibly have, you can use the max_edges function:

In [25]:

pp.algorithms.generative_models.max_edges(n=20, directed=False, self_loops=False)

pp.algorithms.generative_models.max_edges(n=20, directed=False, self_loops=False)

Out[25]:

190

We often use random graph models to generate randomized versions of empirical networks. For this prupose, pathpyG provides _randomize variants for random graph models, which can be used to automatically fit the model parameters to an empirical graph, thus generating a randomized version that preserves the corresponding aggregate characteristics defined by the model.

Let's try this for randomized versions of the Karate club network, which we can load from the netzschleuder database:

In [11]:

g_karate = pp.io.read_netzschleuder_graph('karate', '77')
print(g_karate)

g_karate = pp.io.read_netzschleuder_graph('karate', '77') print(g_karate)

Mapping node attributes based on node indices in column `index`
Undirected graph with 34 nodes and 154 (directed) edges
{   'Edge Attributes': {},
    'Graph Attributes': {   'analyses_average_degree': "<class 'float'>",
                            'analyses_degree_assortativity': "<class 'float'>",
                            'analyses_degree_std_dev': "<class 'float'>",
                            'analyses_diameter': "<class 'int'>",
                            'analyses_edge_properties': "<class 'list'>",
                            'analyses_edge_reciprocity': "<class 'float'>",
                            'analyses_global_clustering': "<class 'float'>",
                            'analyses_hashimoto_radius': "<class 'float'>",
                            'analyses_is_bipartite': "<class 'bool'>",
                            'analyses_is_directed': "<class 'bool'>",
                            'analyses_knn_proj_1': "<class 'float'>",
                            'analyses_knn_proj_2': "<class 'float'>",
                            'analyses_largest_component_fraction': "<class 'float'>",
                            'analyses_mixing_time': "<class 'float'>",
                            'analyses_num_edges': "<class 'int'>",
                            'analyses_num_vertices': "<class 'int'>",
                            'analyses_transition_gap': "<class 'float'>",
                            'analyses_vertex_properties': "<class 'list'>",
                            'num_nodes': "<class 'int'>"},
    'Node Attributes': {   'node__pos': "<class 'numpy.ndarray'>",
                           'node_groups': "<class 'torch.Tensor'> -> torch.Size([34])",
                           'node_name': "<class 'torch.Tensor'> -> torch.Size([34])"}}

Using erdos_renyi_gnm_randomize, we obtain a random graph with the same number of nodes and edges.

In [29]:

r_karate = pp.algorithms.generative_models.erdos_renyi_gnm_randomize(g_karate)
print(r_karate)

r_karate = pp.algorithms.generative_models.erdos_renyi_gnm_randomize(g_karate) print(r_karate)

Undirected graph with 34 nodes and 154 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

Note that node, edge, and graph attributes are not preserved, but it is easy to add back those manually that you want to reassign.

In [31]:

r_karate.data.node_groups = g_karate.data.node_groups
print(r_karate)

r_karate.data.node_groups = g_karate.data.node_groups print(r_karate)

Undirected graph with 34 nodes and 154 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {'node_groups': "<class 'torch.Tensor'> -> torch.Size([34])"}}

Using erdos_renyi_gnp_randomize, we obtain a random graph with the same number of nodes and where the expected number of edges matches the original graph, i.e. in each random realization the actual number of edges varies:

In [33]:

r_karate_1 = pp.algorithms.generative_models.erdos_renyi_gnp_randomize(g_karate)
r_karate_2 = pp.algorithms.generative_models.erdos_renyi_gnp_randomize(g_karate)
print(r_karate_1)
print(r_karate_2)

r_karate_1 = pp.algorithms.generative_models.erdos_renyi_gnp_randomize(g_karate) r_karate_2 = pp.algorithms.generative_models.erdos_renyi_gnp_randomize(g_karate) print(r_karate_1) print(r_karate_2)

Undirected graph with 34 nodes and 154 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Undirected graph with 34 nodes and 196 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

Plotting the distribution of edges in the random realization confirms that we get a distribution that is centered around the edge count of our empirical graph.

In [45]:

from matplotlib import pyplot as plt

edge_counts = []
for i in range(200):
    r_karate = pp.algorithms.generative_models.erdos_renyi_gnp_randomize(g_karate)
    edge_counts.append(r_karate.m)
ax = plt.hist(edge_counts)
plt.axvline(x=g_karate.m, color='red')

from matplotlib import pyplot as plt edge_counts = [] for i in range(200): r_karate = pp.algorithms.generative_models.erdos_renyi_gnp_randomize(g_karate) edge_counts.append(r_karate.m) ax = plt.hist(edge_counts) plt.axvline(x=g_karate.m, color='red')

Out[45]:

<matplotlib.lines.Line2D at 0x7f638bcf9ea0>

We can finally use the Molloy-Reed configuration model to generate random graphs with a given degree sequence:

In [ ]:

g = pp.algorithms.generative_models.molloy_reed([2,2,3,2,3])
print(pp.statistics.degree_sequence(g))
print(g)
pp.plot(g)

g = pp.algorithms.generative_models.molloy_reed([2,2,3,2,3]) print(pp.statistics.degree_sequence(g)) print(g) pp.plot(g)

[2. 2. 3. 2. 3.]
Undirected graph with 5 nodes and 12 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
{'edges': [{'uid': '0-2', 'source': '0', 'target': '2', 'weight': 1}, {'uid': '0-3', 'source': '0', 'target': '3', 'weight': 1}, {'uid': '1-2', 'source': '1', 'target': '2', 'weight': 1}, {'uid': '1-4', 'source': '1', 'target': '4', 'weight': 1}, {'uid': '2-0', 'source': '2', 'target': '0', 'weight': 1}, {'uid': '2-1', 'source': '2', 'target': '1', 'weight': 1}, {'uid': '2-4', 'source': '2', 'target': '4', 'weight': 1}, {'uid': '3-0', 'source': '3', 'target': '0', 'weight': 1}, {'uid': '3-4', 'source': '3', 'target': '4', 'weight': 1}, {'uid': '4-1', 'source': '4', 'target': '1', 'weight': 1}, {'uid': '4-2', 'source': '4', 'target': '2', 'weight': 1}, {'uid': '4-3', 'source': '4', 'target': '3', 'weight': 1}], 'nodes': [{'uid': '0'}, {'uid': '1'}, {'uid': '2'}, {'uid': '3'}, {'uid': '4'}]}

Out[ ]:

<pathpyG.visualisations.network_plots.StaticNetworkPlot at 0x7f0be060c460>

Not every sequence of integers is the degree sequence of a corresponding graph, the following thus fails:

In [8]:

g = pp.algorithms.generative_models.molloy_reed([2,2,6,2,3])

g = pp.algorithms.generative_models.molloy_reed([2,2,6,2,3])

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[8], line 1
----> 1 g = pp.algorithms.generative_models.molloy_reed([2,2,6,2,3])

File /workspaces/pathpyG/src/pathpyG/algorithms/generative_models.py:437, in molloy_reed(degree_sequence, multiedge, relax, node_ids)
    435 # assume that we are given a graphical degree sequence
    436 if not is_graphic_erdos_gallai(degree_sequence):
--> 437     raise AttributeError('degree sequence is not graphic')
    439 # create empty network with n nodes
    440 n = len(degree_sequence)

AttributeError: degree sequence is not graphic

We can test whether a sequence of integers is graphic, i.e. whether we can use it to generate a Molloy-Reed random graph:

In [10]:

pp.algorithms.generative_models.is_graphic_erdos_gallai([2,2,6,2,3])

pp.algorithms.generative_models.is_graphic_erdos_gallai([2,2,6,2,3])

Out[10]:

False

We can use the Molloy-Reed model to randomize empirical networks, generating a random graph with the same degree sequence but a randomized topology:

In [16]:

r_karate = pp.algorithms.generative_models.molloy_reed_randomize(g_karate)
print(r_karate)
print(pp.statistics.degree_sequence(g_karate))
print(pp.statistics.degree_sequence(r_karate))

r_karate = pp.algorithms.generative_models.molloy_reed_randomize(g_karate) print(r_karate) print(pp.statistics.degree_sequence(g_karate)) print(pp.statistics.degree_sequence(r_karate))

Undirected graph with 34 nodes and 154 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
[16.  9. 10.  6.  3.  4.  4.  4.  5.  2.  3.  1.  2.  5.  2.  2.  2.  2.
  2.  3.  2.  2.  1.  5.  3.  3.  2.  4.  3.  4.  4.  6. 12. 16.]
[16.  9. 10.  6.  3.  4.  4.  4.  5.  2.  3.  1.  2.  5.  2.  2.  2.  2.
  2.  3.  2.  2.  1.  5.  3.  3.  2.  4.  3.  4.  4.  6. 12. 16.]

Finally, the generative_models module also contains implementations of the Watts-Strogatz model as well as the stochastic block model. Different from the models above, those models cannot be used to randomize a graph though.

In [18]:

g = pp.algorithms.generative_models.watts_strogatz(n=100, s=2, p=0.1)
pp.plot(g);

g = pp.algorithms.generative_models.watts_strogatz(n=100, s=2, p=0.1) pp.plot(g);

{'edges': [{'uid': '0-2', 'source': '0', 'target': '2', 'weight': 1}, {'uid': '0-1', 'source': '0', 'target': '1', 'weight': 1}, {'uid': '0-99', 'source': '0', 'target': '99', 'weight': 1}, {'uid': '0-98', 'source': '0', 'target': '98', 'weight': 1}, {'uid': '1-0', 'source': '1', 'target': '0', 'weight': 1}, {'uid': '1-2', 'source': '1', 'target': '2', 'weight': 1}, {'uid': '1-3', 'source': '1', 'target': '3', 'weight': 1}, {'uid': '1-99', 'source': '1', 'target': '99', 'weight': 1}, {'uid': '2-0', 'source': '2', 'target': '0', 'weight': 1}, {'uid': '2-1', 'source': '2', 'target': '1', 'weight': 1}, {'uid': '2-3', 'source': '2', 'target': '3', 'weight': 1}, {'uid': '2-4', 'source': '2', 'target': '4', 'weight': 1}, {'uid': '3-5', 'source': '3', 'target': '5', 'weight': 1}, {'uid': '3-18', 'source': '3', 'target': '18', 'weight': 1}, {'uid': '3-4', 'source': '3', 'target': '4', 'weight': 1}, {'uid': '3-2', 'source': '3', 'target': '2', 'weight': 1}, {'uid': '3-1', 'source': '3', 'target': '1', 'weight': 1}, {'uid': '4-2', 'source': '4', 'target': '2', 'weight': 1}, {'uid': '4-3', 'source': '4', 'target': '3', 'weight': 1}, {'uid': '4-5', 'source': '4', 'target': '5', 'weight': 1}, {'uid': '4-6', 'source': '4', 'target': '6', 'weight': 1}, {'uid': '4-79', 'source': '4', 'target': '79', 'weight': 1}, {'uid': '5-3', 'source': '5', 'target': '3', 'weight': 1}, {'uid': '5-4', 'source': '5', 'target': '4', 'weight': 1}, {'uid': '5-6', 'source': '5', 'target': '6', 'weight': 1}, {'uid': '5-7', 'source': '5', 'target': '7', 'weight': 1}, {'uid': '6-7', 'source': '6', 'target': '7', 'weight': 1}, {'uid': '6-8', 'source': '6', 'target': '8', 'weight': 1}, {'uid': '6-5', 'source': '6', 'target': '5', 'weight': 1}, {'uid': '6-4', 'source': '6', 'target': '4', 'weight': 1}, {'uid': '7-5', 'source': '7', 'target': '5', 'weight': 1}, {'uid': '7-6', 'source': '7', 'target': '6', 'weight': 1}, {'uid': '7-9', 'source': '7', 'target': '9', 'weight': 1}, {'uid': '7-76', 'source': '7', 'target': '76', 'weight': 1}, {'uid': '8-6', 'source': '8', 'target': '6', 'weight': 1}, {'uid': '8-10', 'source': '8', 'target': '10', 'weight': 1}, {'uid': '8-96', 'source': '8', 'target': '96', 'weight': 1}, {'uid': '9-7', 'source': '9', 'target': '7', 'weight': 1}, {'uid': '9-10', 'source': '9', 'target': '10', 'weight': 1}, {'uid': '9-11', 'source': '9', 'target': '11', 'weight': 1}, {'uid': '10-9', 'source': '10', 'target': '9', 'weight': 1}, {'uid': '10-12', 'source': '10', 'target': '12', 'weight': 1}, {'uid': '10-11', 'source': '10', 'target': '11', 'weight': 1}, {'uid': '10-8', 'source': '10', 'target': '8', 'weight': 1}, {'uid': '11-9', 'source': '11', 'target': '9', 'weight': 1}, {'uid': '11-10', 'source': '11', 'target': '10', 'weight': 1}, {'uid': '11-12', 'source': '11', 'target': '12', 'weight': 1}, {'uid': '11-13', 'source': '11', 'target': '13', 'weight': 1}, {'uid': '12-10', 'source': '12', 'target': '10', 'weight': 1}, {'uid': '12-11', 'source': '12', 'target': '11', 'weight': 1}, {'uid': '12-13', 'source': '12', 'target': '13', 'weight': 1}, {'uid': '12-14', 'source': '12', 'target': '14', 'weight': 1}, {'uid': '13-12', 'source': '13', 'target': '12', 'weight': 1}, {'uid': '13-15', 'source': '13', 'target': '15', 'weight': 1}, {'uid': '13-14', 'source': '13', 'target': '14', 'weight': 1}, {'uid': '13-11', 'source': '13', 'target': '11', 'weight': 1}, {'uid': '14-13', 'source': '14', 'target': '13', 'weight': 1}, {'uid': '14-15', 'source': '14', 'target': '15', 'weight': 1}, {'uid': '14-16', 'source': '14', 'target': '16', 'weight': 1}, {'uid': '14-12', 'source': '14', 'target': '12', 'weight': 1}, {'uid': '15-13', 'source': '15', 'target': '13', 'weight': 1}, {'uid': '15-14', 'source': '15', 'target': '14', 'weight': 1}, {'uid': '15-16', 'source': '15', 'target': '16', 'weight': 1}, {'uid': '15-17', 'source': '15', 'target': '17', 'weight': 1}, {'uid': '16-18', 'source': '16', 'target': '18', 'weight': 1}, {'uid': '16-17', 'source': '16', 'target': '17', 'weight': 1}, {'uid': '16-15', 'source': '16', 'target': '15', 'weight': 1}, {'uid': '16-14', 'source': '16', 'target': '14', 'weight': 1}, {'uid': '17-15', 'source': '17', 'target': '15', 'weight': 1}, {'uid': '17-16', 'source': '17', 'target': '16', 'weight': 1}, {'uid': '17-18', 'source': '17', 'target': '18', 'weight': 1}, {'uid': '17-19', 'source': '17', 'target': '19', 'weight': 1}, {'uid': '18-3', 'source': '18', 'target': '3', 'weight': 1}, {'uid': '18-16', 'source': '18', 'target': '16', 'weight': 1}, {'uid': '18-17', 'source': '18', 'target': '17', 'weight': 1}, {'uid': '18-19', 'source': '18', 'target': '19', 'weight': 1}, {'uid': '19-53', 'source': '19', 'target': '53', 'weight': 1}, {'uid': '19-20', 'source': '19', 'target': '20', 'weight': 1}, {'uid': '19-17', 'source': '19', 'target': '17', 'weight': 1}, {'uid': '19-18', 'source': '19', 'target': '18', 'weight': 1}, {'uid': '20-19', 'source': '20', 'target': '19', 'weight': 1}, {'uid': '20-31', 'source': '20', 'target': '31', 'weight': 1}, {'uid': '20-70', 'source': '20', 'target': '70', 'weight': 1}, {'uid': '21-22', 'source': '21', 'target': '22', 'weight': 1}, {'uid': '21-23', 'source': '21', 'target': '23', 'weight': 1}, {'uid': '22-21', 'source': '22', 'target': '21', 'weight': 1}, {'uid': '22-23', 'source': '22', 'target': '23', 'weight': 1}, {'uid': '22-24', 'source': '22', 'target': '24', 'weight': 1}, {'uid': '22-77', 'source': '22', 'target': '77', 'weight': 1}, {'uid': '23-22', 'source': '23', 'target': '22', 'weight': 1}, {'uid': '23-25', 'source': '23', 'target': '25', 'weight': 1}, {'uid': '23-24', 'source': '23', 'target': '24', 'weight': 1}, {'uid': '23-21', 'source': '23', 'target': '21', 'weight': 1}, {'uid': '24-22', 'source': '24', 'target': '22', 'weight': 1}, {'uid': '24-23', 'source': '24', 'target': '23', 'weight': 1}, {'uid': '24-25', 'source': '24', 'target': '25', 'weight': 1}, {'uid': '24-26', 'source': '24', 'target': '26', 'weight': 1}, {'uid': '25-23', 'source': '25', 'target': '23', 'weight': 1}, {'uid': '25-24', 'source': '25', 'target': '24', 'weight': 1}, {'uid': '25-26', 'source': '25', 'target': '26', 'weight': 1}, {'uid': '25-27', 'source': '25', 'target': '27', 'weight': 1}, {'uid': '26-28', 'source': '26', 'target': '28', 'weight': 1}, {'uid': '26-24', 'source': '26', 'target': '24', 'weight': 1}, {'uid': '26-25', 'source': '26', 'target': '25', 'weight': 1}, {'uid': '26-27', 'source': '26', 'target': '27', 'weight': 1}, {'uid': '27-25', 'source': '27', 'target': '25', 'weight': 1}, {'uid': '27-26', 'source': '27', 'target': '26', 'weight': 1}, {'uid': '27-28', 'source': '27', 'target': '28', 'weight': 1}, {'uid': '27-29', 'source': '27', 'target': '29', 'weight': 1}, {'uid': '28-26', 'source': '28', 'target': '26', 'weight': 1}, {'uid': '28-27', 'source': '28', 'target': '27', 'weight': 1}, {'uid': '28-29', 'source': '28', 'target': '29', 'weight': 1}, {'uid': '28-45', 'source': '28', 'target': '45', 'weight': 1}, {'uid': '29-30', 'source': '29', 'target': '30', 'weight': 1}, {'uid': '29-31', 'source': '29', 'target': '31', 'weight': 1}, {'uid': '29-28', 'source': '29', 'target': '28', 'weight': 1}, {'uid': '29-27', 'source': '29', 'target': '27', 'weight': 1}, {'uid': '30-29', 'source': '30', 'target': '29', 'weight': 1}, {'uid': '30-31', 'source': '30', 'target': '31', 'weight': 1}, {'uid': '30-32', 'source': '30', 'target': '32', 'weight': 1}, {'uid': '31-20', 'source': '31', 'target': '20', 'weight': 1}, {'uid': '31-29', 'source': '31', 'target': '29', 'weight': 1}, {'uid': '31-30', 'source': '31', 'target': '30', 'weight': 1}, {'uid': '31-32', 'source': '31', 'target': '32', 'weight': 1}, {'uid': '31-33', 'source': '31', 'target': '33', 'weight': 1}, {'uid': '32-31', 'source': '32', 'target': '31', 'weight': 1}, {'uid': '32-34', 'source': '32', 'target': '34', 'weight': 1}, {'uid': '32-33', 'source': '32', 'target': '33', 'weight': 1}, {'uid': '32-30', 'source': '32', 'target': '30', 'weight': 1}, {'uid': '33-32', 'source': '33', 'target': '32', 'weight': 1}, {'uid': '33-34', 'source': '33', 'target': '34', 'weight': 1}, {'uid': '33-35', 'source': '33', 'target': '35', 'weight': 1}, {'uid': '33-31', 'source': '33', 'target': '31', 'weight': 1}, {'uid': '34-32', 'source': '34', 'target': '32', 'weight': 1}, {'uid': '34-33', 'source': '34', 'target': '33', 'weight': 1}, {'uid': '34-35', 'source': '34', 'target': '35', 'weight': 1}, {'uid': '34-71', 'source': '34', 'target': '71', 'weight': 1}, {'uid': '35-36', 'source': '35', 'target': '36', 'weight': 1}, {'uid': '35-37', 'source': '35', 'target': '37', 'weight': 1}, {'uid': '35-34', 'source': '35', 'target': '34', 'weight': 1}, {'uid': '35-33', 'source': '35', 'target': '33', 'weight': 1}, {'uid': '36-35', 'source': '36', 'target': '35', 'weight': 1}, {'uid': '36-37', 'source': '36', 'target': '37', 'weight': 1}, {'uid': '36-38', 'source': '36', 'target': '38', 'weight': 1}, {'uid': '37-35', 'source': '37', 'target': '35', 'weight': 1}, {'uid': '37-36', 'source': '37', 'target': '36', 'weight': 1}, {'uid': '37-38', 'source': '37', 'target': '38', 'weight': 1}, {'uid': '37-39', 'source': '37', 'target': '39', 'weight': 1}, {'uid': '38-39', 'source': '38', 'target': '39', 'weight': 1}, {'uid': '38-89', 'source': '38', 'target': '89', 'weight': 1}, {'uid': '38-36', 'source': '38', 'target': '36', 'weight': 1}, {'uid': '38-37', 'source': '38', 'target': '37', 'weight': 1}, {'uid': '39-38', 'source': '39', 'target': '38', 'weight': 1}, {'uid': '39-40', 'source': '39', 'target': '40', 'weight': 1}, {'uid': '39-41', 'source': '39', 'target': '41', 'weight': 1}, {'uid': '39-37', 'source': '39', 'target': '37', 'weight': 1}, {'uid': '40-39', 'source': '40', 'target': '39', 'weight': 1}, {'uid': '40-41', 'source': '40', 'target': '41', 'weight': 1}, {'uid': '40-42', 'source': '40', 'target': '42', 'weight': 1}, {'uid': '41-48', 'source': '41', 'target': '48', 'weight': 1}, {'uid': '41-43', 'source': '41', 'target': '43', 'weight': 1}, {'uid': '41-42', 'source': '41', 'target': '42', 'weight': 1}, {'uid': '41-40', 'source': '41', 'target': '40', 'weight': 1}, {'uid': '41-39', 'source': '41', 'target': '39', 'weight': 1}, {'uid': '42-40', 'source': '42', 'target': '40', 'weight': 1}, {'uid': '42-41', 'source': '42', 'target': '41', 'weight': 1}, {'uid': '42-44', 'source': '42', 'target': '44', 'weight': 1}, {'uid': '42-70', 'source': '42', 'target': '70', 'weight': 1}, {'uid': '43-41', 'source': '43', 'target': '41', 'weight': 1}, {'uid': '43-44', 'source': '43', 'target': '44', 'weight': 1}, {'uid': '43-45', 'source': '43', 'target': '45', 'weight': 1}, {'uid': '43-72', 'source': '43', 'target': '72', 'weight': 1}, {'uid': '44-46', 'source': '44', 'target': '46', 'weight': 1}, {'uid': '44-45', 'source': '44', 'target': '45', 'weight': 1}, {'uid': '44-42', 'source': '44', 'target': '42', 'weight': 1}, {'uid': '44-43', 'source': '44', 'target': '43', 'weight': 1}, {'uid': '45-28', 'source': '45', 'target': '28', 'weight': 1}, {'uid': '45-43', 'source': '45', 'target': '43', 'weight': 1}, {'uid': '45-44', 'source': '45', 'target': '44', 'weight': 1}, {'uid': '45-46', 'source': '45', 'target': '46', 'weight': 1}, {'uid': '45-47', 'source': '45', 'target': '47', 'weight': 1}, {'uid': '46-44', 'source': '46', 'target': '44', 'weight': 1}, {'uid': '46-45', 'source': '46', 'target': '45', 'weight': 1}, {'uid': '46-47', 'source': '46', 'target': '47', 'weight': 1}, {'uid': '46-48', 'source': '46', 'target': '48', 'weight': 1}, {'uid': '47-46', 'source': '47', 'target': '46', 'weight': 1}, {'uid': '47-49', 'source': '47', 'target': '49', 'weight': 1}, {'uid': '47-48', 'source': '47', 'target': '48', 'weight': 1}, {'uid': '47-45', 'source': '47', 'target': '45', 'weight': 1}, {'uid': '48-41', 'source': '48', 'target': '41', 'weight': 1}, {'uid': '48-46', 'source': '48', 'target': '46', 'weight': 1}, {'uid': '48-47', 'source': '48', 'target': '47', 'weight': 1}, {'uid': '48-49', 'source': '48', 'target': '49', 'weight': 1}, {'uid': '49-47', 'source': '49', 'target': '47', 'weight': 1}, {'uid': '49-48', 'source': '49', 'target': '48', 'weight': 1}, {'uid': '49-50', 'source': '49', 'target': '50', 'weight': 1}, {'uid': '49-51', 'source': '49', 'target': '51', 'weight': 1}, {'uid': '50-58', 'source': '50', 'target': '58', 'weight': 1}, {'uid': '50-52', 'source': '50', 'target': '52', 'weight': 1}, {'uid': '50-49', 'source': '50', 'target': '49', 'weight': 1}, {'uid': '50-51', 'source': '50', 'target': '51', 'weight': 1}, {'uid': '51-50', 'source': '51', 'target': '50', 'weight': 1}, {'uid': '51-52', 'source': '51', 'target': '52', 'weight': 1}, {'uid': '51-53', 'source': '51', 'target': '53', 'weight': 1}, {'uid': '51-49', 'source': '51', 'target': '49', 'weight': 1}, {'uid': '52-50', 'source': '52', 'target': '50', 'weight': 1}, {'uid': '52-51', 'source': '52', 'target': '51', 'weight': 1}, {'uid': '52-53', 'source': '52', 'target': '53', 'weight': 1}, {'uid': '52-54', 'source': '52', 'target': '54', 'weight': 1}, {'uid': '53-19', 'source': '53', 'target': '19', 'weight': 1}, {'uid': '53-51', 'source': '53', 'target': '51', 'weight': 1}, {'uid': '53-52', 'source': '53', 'target': '52', 'weight': 1}, {'uid': '53-54', 'source': '53', 'target': '54', 'weight': 1}, {'uid': '53-55', 'source': '53', 'target': '55', 'weight': 1}, {'uid': '54-52', 'source': '54', 'target': '52', 'weight': 1}, {'uid': '54-56', 'source': '54', 'target': '56', 'weight': 1}, {'uid': '54-55', 'source': '54', 'target': '55', 'weight': 1}, {'uid': '54-53', 'source': '54', 'target': '53', 'weight': 1}, {'uid': '55-53', 'source': '55', 'target': '53', 'weight': 1}, {'uid': '55-54', 'source': '55', 'target': '54', 'weight': 1}, {'uid': '55-56', 'source': '55', 'target': '56', 'weight': 1}, {'uid': '55-57', 'source': '55', 'target': '57', 'weight': 1}, {'uid': '56-54', 'source': '56', 'target': '54', 'weight': 1}, {'uid': '56-55', 'source': '56', 'target': '55', 'weight': 1}, {'uid': '56-57', 'source': '56', 'target': '57', 'weight': 1}, {'uid': '56-58', 'source': '56', 'target': '58', 'weight': 1}, {'uid': '57-55', 'source': '57', 'target': '55', 'weight': 1}, {'uid': '57-88', 'source': '57', 'target': '88', 'weight': 1}, {'uid': '57-56', 'source': '57', 'target': '56', 'weight': 1}, {'uid': '57-58', 'source': '57', 'target': '58', 'weight': 1}, {'uid': '58-50', 'source': '58', 'target': '50', 'weight': 1}, {'uid': '58-56', 'source': '58', 'target': '56', 'weight': 1}, {'uid': '58-57', 'source': '58', 'target': '57', 'weight': 1}, {'uid': '58-60', 'source': '58', 'target': '60', 'weight': 1}, {'uid': '59-60', 'source': '59', 'target': '60', 'weight': 1}, {'uid': '59-61', 'source': '59', 'target': '61', 'weight': 1}, {'uid': '60-62', 'source': '60', 'target': '62', 'weight': 1}, {'uid': '60-61', 'source': '60', 'target': '61', 'weight': 1}, {'uid': '60-59', 'source': '60', 'target': '59', 'weight': 1}, {'uid': '60-58', 'source': '60', 'target': '58', 'weight': 1}, {'uid': '61-59', 'source': '61', 'target': '59', 'weight': 1}, {'uid': '61-60', 'source': '61', 'target': '60', 'weight': 1}, {'uid': '61-62', 'source': '61', 'target': '62', 'weight': 1}, {'uid': '61-63', 'source': '61', 'target': '63', 'weight': 1}, {'uid': '61-73', 'source': '61', 'target': '73', 'weight': 1}, {'uid': '62-60', 'source': '62', 'target': '60', 'weight': 1}, {'uid': '62-61', 'source': '62', 'target': '61', 'weight': 1}, {'uid': '62-63', 'source': '62', 'target': '63', 'weight': 1}, {'uid': '62-64', 'source': '62', 'target': '64', 'weight': 1}, {'uid': '63-61', 'source': '63', 'target': '61', 'weight': 1}, {'uid': '63-65', 'source': '63', 'target': '65', 'weight': 1}, {'uid': '63-62', 'source': '63', 'target': '62', 'weight': 1}, {'uid': '63-64', 'source': '63', 'target': '64', 'weight': 1}, {'uid': '64-63', 'source': '64', 'target': '63', 'weight': 1}, {'uid': '64-65', 'source': '64', 'target': '65', 'weight': 1}, {'uid': '64-66', 'source': '64', 'target': '66', 'weight': 1}, {'uid': '64-62', 'source': '64', 'target': '62', 'weight': 1}, {'uid': '65-63', 'source': '65', 'target': '63', 'weight': 1}, {'uid': '65-64', 'source': '65', 'target': '64', 'weight': 1}, {'uid': '65-66', 'source': '65', 'target': '66', 'weight': 1}, {'uid': '65-67', 'source': '65', 'target': '67', 'weight': 1}, {'uid': '66-68', 'source': '66', 'target': '68', 'weight': 1}, {'uid': '66-67', 'source': '66', 'target': '67', 'weight': 1}, {'uid': '66-65', 'source': '66', 'target': '65', 'weight': 1}, {'uid': '66-64', 'source': '66', 'target': '64', 'weight': 1}, {'uid': '67-65', 'source': '67', 'target': '65', 'weight': 1}, {'uid': '67-66', 'source': '67', 'target': '66', 'weight': 1}, {'uid': '67-68', 'source': '67', 'target': '68', 'weight': 1}, {'uid': '67-69', 'source': '67', 'target': '69', 'weight': 1}, {'uid': '68-66', 'source': '68', 'target': '66', 'weight': 1}, {'uid': '68-67', 'source': '68', 'target': '67', 'weight': 1}, {'uid': '68-70', 'source': '68', 'target': '70', 'weight': 1}, {'uid': '68-97', 'source': '68', 'target': '97', 'weight': 1}, {'uid': '69-71', 'source': '69', 'target': '71', 'weight': 1}, {'uid': '69-70', 'source': '69', 'target': '70', 'weight': 1}, {'uid': '69-67', 'source': '69', 'target': '67', 'weight': 1}, {'uid': '70-20', 'source': '70', 'target': '20', 'weight': 1}, {'uid': '70-42', 'source': '70', 'target': '42', 'weight': 1}, {'uid': '70-68', 'source': '70', 'target': '68', 'weight': 1}, {'uid': '70-69', 'source': '70', 'target': '69', 'weight': 1}, {'uid': '70-71', 'source': '70', 'target': '71', 'weight': 1}, {'uid': '70-72', 'source': '70', 'target': '72', 'weight': 1}, {'uid': '71-73', 'source': '71', 'target': '73', 'weight': 1}, {'uid': '71-72', 'source': '71', 'target': '72', 'weight': 1}, {'uid': '71-70', 'source': '71', 'target': '70', 'weight': 1}, {'uid': '71-69', 'source': '71', 'target': '69', 'weight': 1}, {'uid': '71-34', 'source': '71', 'target': '34', 'weight': 1}, {'uid': '72-43', 'source': '72', 'target': '43', 'weight': 1}, {'uid': '72-70', 'source': '72', 'target': '70', 'weight': 1}, {'uid': '72-71', 'source': '72', 'target': '71', 'weight': 1}, {'uid': '72-73', 'source': '72', 'target': '73', 'weight': 1}, {'uid': '72-95', 'source': '72', 'target': '95', 'weight': 1}, {'uid': '73-61', 'source': '73', 'target': '61', 'weight': 1}, {'uid': '73-71', 'source': '73', 'target': '71', 'weight': 1}, {'uid': '73-72', 'source': '73', 'target': '72', 'weight': 1}, {'uid': '73-74', 'source': '73', 'target': '74', 'weight': 1}, {'uid': '74-76', 'source': '74', 'target': '76', 'weight': 1}, {'uid': '74-73', 'source': '74', 'target': '73', 'weight': 1}, {'uid': '74-75', 'source': '74', 'target': '75', 'weight': 1}, {'uid': '75-76', 'source': '75', 'target': '76', 'weight': 1}, {'uid': '75-74', 'source': '75', 'target': '74', 'weight': 1}, {'uid': '75-77', 'source': '75', 'target': '77', 'weight': 1}, {'uid': '76-7', 'source': '76', 'target': '7', 'weight': 1}, {'uid': '76-74', 'source': '76', 'target': '74', 'weight': 1}, {'uid': '76-75', 'source': '76', 'target': '75', 'weight': 1}, {'uid': '76-77', 'source': '76', 'target': '77', 'weight': 1}, {'uid': '76-78', 'source': '76', 'target': '78', 'weight': 1}, {'uid': '77-22', 'source': '77', 'target': '22', 'weight': 1}, {'uid': '77-75', 'source': '77', 'target': '75', 'weight': 1}, {'uid': '77-76', 'source': '77', 'target': '76', 'weight': 1}, {'uid': '77-78', 'source': '77', 'target': '78', 'weight': 1}, {'uid': '78-77', 'source': '78', 'target': '77', 'weight': 1}, {'uid': '78-80', 'source': '78', 'target': '80', 'weight': 1}, {'uid': '78-79', 'source': '78', 'target': '79', 'weight': 1}, {'uid': '78-76', 'source': '78', 'target': '76', 'weight': 1}, {'uid': '79-4', 'source': '79', 'target': '4', 'weight': 1}, {'uid': '79-78', 'source': '79', 'target': '78', 'weight': 1}, {'uid': '79-81', 'source': '79', 'target': '81', 'weight': 1}, {'uid': '80-78', 'source': '80', 'target': '78', 'weight': 1}, {'uid': '80-81', 'source': '80', 'target': '81', 'weight': 1}, {'uid': '80-82', 'source': '80', 'target': '82', 'weight': 1}, {'uid': '81-83', 'source': '81', 'target': '83', 'weight': 1}, {'uid': '81-82', 'source': '81', 'target': '82', 'weight': 1}, {'uid': '81-79', 'source': '81', 'target': '79', 'weight': 1}, {'uid': '81-80', 'source': '81', 'target': '80', 'weight': 1}, {'uid': '82-80', 'source': '82', 'target': '80', 'weight': 1}, {'uid': '82-81', 'source': '82', 'target': '81', 'weight': 1}, {'uid': '82-83', 'source': '82', 'target': '83', 'weight': 1}, {'uid': '82-84', 'source': '82', 'target': '84', 'weight': 1}, {'uid': '83-81', 'source': '83', 'target': '81', 'weight': 1}, {'uid': '83-82', 'source': '83', 'target': '82', 'weight': 1}, {'uid': '83-84', 'source': '83', 'target': '84', 'weight': 1}, {'uid': '83-85', 'source': '83', 'target': '85', 'weight': 1}, {'uid': '84-85', 'source': '84', 'target': '85', 'weight': 1}, {'uid': '84-86', 'source': '84', 'target': '86', 'weight': 1}, {'uid': '84-83', 'source': '84', 'target': '83', 'weight': 1}, {'uid': '84-82', 'source': '84', 'target': '82', 'weight': 1}, {'uid': '85-83', 'source': '85', 'target': '83', 'weight': 1}, {'uid': '85-84', 'source': '85', 'target': '84', 'weight': 1}, {'uid': '85-86', 'source': '85', 'target': '86', 'weight': 1}, {'uid': '85-87', 'source': '85', 'target': '87', 'weight': 1}, {'uid': '86-84', 'source': '86', 'target': '84', 'weight': 1}, {'uid': '86-85', 'source': '86', 'target': '85', 'weight': 1}, {'uid': '86-87', 'source': '86', 'target': '87', 'weight': 1}, {'uid': '86-88', 'source': '86', 'target': '88', 'weight': 1}, {'uid': '87-89', 'source': '87', 'target': '89', 'weight': 1}, {'uid': '87-88', 'source': '87', 'target': '88', 'weight': 1}, {'uid': '87-85', 'source': '87', 'target': '85', 'weight': 1}, {'uid': '87-86', 'source': '87', 'target': '86', 'weight': 1}, {'uid': '88-86', 'source': '88', 'target': '86', 'weight': 1}, {'uid': '88-87', 'source': '88', 'target': '87', 'weight': 1}, {'uid': '88-89', 'source': '88', 'target': '89', 'weight': 1}, {'uid': '88-90', 'source': '88', 'target': '90', 'weight': 1}, {'uid': '88-57', 'source': '88', 'target': '57', 'weight': 1}, {'uid': '89-38', 'source': '89', 'target': '38', 'weight': 1}, {'uid': '89-87', 'source': '89', 'target': '87', 'weight': 1}, {'uid': '89-88', 'source': '89', 'target': '88', 'weight': 1}, {'uid': '89-90', 'source': '89', 'target': '90', 'weight': 1}, {'uid': '89-91', 'source': '89', 'target': '91', 'weight': 1}, {'uid': '90-91', 'source': '90', 'target': '91', 'weight': 1}, {'uid': '90-92', 'source': '90', 'target': '92', 'weight': 1}, {'uid': '90-89', 'source': '90', 'target': '89', 'weight': 1}, {'uid': '90-88', 'source': '90', 'target': '88', 'weight': 1}, {'uid': '91-89', 'source': '91', 'target': '89', 'weight': 1}, {'uid': '91-90', 'source': '91', 'target': '90', 'weight': 1}, {'uid': '91-92', 'source': '91', 'target': '92', 'weight': 1}, {'uid': '91-93', 'source': '91', 'target': '93', 'weight': 1}, {'uid': '92-90', 'source': '92', 'target': '90', 'weight': 1}, {'uid': '92-91', 'source': '92', 'target': '91', 'weight': 1}, {'uid': '92-93', 'source': '92', 'target': '93', 'weight': 1}, {'uid': '92-94', 'source': '92', 'target': '94', 'weight': 1}, {'uid': '93-95', 'source': '93', 'target': '95', 'weight': 1}, {'uid': '93-92', 'source': '93', 'target': '92', 'weight': 1}, {'uid': '93-91', 'source': '93', 'target': '91', 'weight': 1}, {'uid': '93-94', 'source': '93', 'target': '94', 'weight': 1}, {'uid': '94-92', 'source': '94', 'target': '92', 'weight': 1}, {'uid': '94-93', 'source': '94', 'target': '93', 'weight': 1}, {'uid': '94-96', 'source': '94', 'target': '96', 'weight': 1}, {'uid': '95-72', 'source': '95', 'target': '72', 'weight': 1}, {'uid': '95-93', 'source': '95', 'target': '93', 'weight': 1}, {'uid': '95-97', 'source': '95', 'target': '97', 'weight': 1}, {'uid': '96-8', 'source': '96', 'target': '8', 'weight': 1}, {'uid': '96-94', 'source': '96', 'target': '94', 'weight': 1}, {'uid': '96-97', 'source': '96', 'target': '97', 'weight': 1}, {'uid': '96-98', 'source': '96', 'target': '98', 'weight': 1}, {'uid': '97-68', 'source': '97', 'target': '68', 'weight': 1}, {'uid': '97-99', 'source': '97', 'target': '99', 'weight': 1}, {'uid': '97-98', 'source': '97', 'target': '98', 'weight': 1}, {'uid': '97-96', 'source': '97', 'target': '96', 'weight': 1}, {'uid': '97-95', 'source': '97', 'target': '95', 'weight': 1}, {'uid': '98-0', 'source': '98', 'target': '0', 'weight': 1}, {'uid': '98-96', 'source': '98', 'target': '96', 'weight': 1}, {'uid': '98-97', 'source': '98', 'target': '97', 'weight': 1}, {'uid': '98-99', 'source': '98', 'target': '99', 'weight': 1}, {'uid': '99-0', 'source': '99', 'target': '0', 'weight': 1}, {'uid': '99-1', 'source': '99', 'target': '1', 'weight': 1}, {'uid': '99-97', 'source': '99', 'target': '97', 'weight': 1}, {'uid': '99-98', 'source': '99', 'target': '98', 'weight': 1}], 'nodes': [{'uid': '0'}, {'uid': '1'}, {'uid': '2'}, {'uid': '3'}, {'uid': '4'}, {'uid': '5'}, {'uid': '6'}, {'uid': '7'}, {'uid': '8'}, {'uid': '9'}, {'uid': '10'}, {'uid': '11'}, {'uid': '12'}, {'uid': '13'}, {'uid': '14'}, {'uid': '15'}, {'uid': '16'}, {'uid': '17'}, {'uid': '18'}, {'uid': '19'}, {'uid': '20'}, {'uid': '21'}, {'uid': '22'}, {'uid': '23'}, {'uid': '24'}, {'uid': '25'}, {'uid': '26'}, {'uid': '27'}, {'uid': '28'}, {'uid': '29'}, {'uid': '30'}, {'uid': '31'}, {'uid': '32'}, {'uid': '33'}, {'uid': '34'}, {'uid': '35'}, {'uid': '36'}, {'uid': '37'}, {'uid': '38'}, {'uid': '39'}, {'uid': '40'}, {'uid': '41'}, {'uid': '42'}, {'uid': '43'}, {'uid': '44'}, {'uid': '45'}, {'uid': '46'}, {'uid': '47'}, {'uid': '48'}, {'uid': '49'}, {'uid': '50'}, {'uid': '51'}, {'uid': '52'}, {'uid': '53'}, {'uid': '54'}, {'uid': '55'}, {'uid': '56'}, {'uid': '57'}, {'uid': '58'}, {'uid': '59'}, {'uid': '60'}, {'uid': '61'}, {'uid': '62'}, {'uid': '63'}, {'uid': '64'}, {'uid': '65'}, {'uid': '66'}, {'uid': '67'}, {'uid': '68'}, {'uid': '69'}, {'uid': '70'}, {'uid': '71'}, {'uid': '72'}, {'uid': '73'}, {'uid': '74'}, {'uid': '75'}, {'uid': '76'}, {'uid': '77'}, {'uid': '78'}, {'uid': '79'}, {'uid': '80'}, {'uid': '81'}, {'uid': '82'}, {'uid': '83'}, {'uid': '84'}, {'uid': '85'}, {'uid': '86'}, {'uid': '87'}, {'uid': '88'}, {'uid': '89'}, {'uid': '90'}, {'uid': '91'}, {'uid': '92'}, {'uid': '93'}, {'uid': '94'}, {'uid': '95'}, {'uid': '96'}, {'uid': '97'}, {'uid': '98'}, {'uid': '99'}]}

To generate an undirected random graph based on the stochastic block model, we must minimally specify two parameters:

The stochastic block matrix $M$ contains edge probabilities for all pairs of nodes where the source and target belong to different blocks.

The block assignment vector $z$ assigns nodes to blocks (based on their index). The length of this vector implicitly determined the number of nodes.

In the example below, we generate a random graph with eight nodes, where the first four nodes a - d are assigned to block 0 and the last four nodes e - h are assigned to block 1. Edges between node pairs where both nodes are in block 0 are generated with probability $0.95$. If both nodes are in block 1 edges are generated with probability $0.85$. If the nodes are in different blocks, edges are generated with probability $0.1$.

In [40]:

M = np.matrix('0.95 0.15; 0.15 0.85')
print(M)
z = np.array([0, 0, 0, 0, 1, 1, 1, 1])

g = pp.algorithms.generative_models.stochastic_block_model(M, z, pp.IndexMap(list('abcdefgh')))
pp.plot(g, node_label=g.nodes, node_color=z.tolist());

M = np.matrix('0.95 0.15; 0.15 0.85') print(M) z = np.array([0, 0, 0, 0, 1, 1, 1, 1]) g = pp.algorithms.generative_models.stochastic_block_model(M, z, pp.IndexMap(list('abcdefgh'))) pp.plot(g, node_label=g.nodes, node_color=z.tolist());

[[0.95 0.15]
 [0.15 0.85]]
{'edges': [{'uid': 'a-c', 'source': 'a', 'target': 'c', 'weight': 1}, {'uid': 'a-d', 'source': 'a', 'target': 'd', 'weight': 1}, {'uid': 'a-b', 'source': 'a', 'target': 'b', 'weight': 1}, {'uid': 'b-a', 'source': 'b', 'target': 'a', 'weight': 1}, {'uid': 'b-c', 'source': 'b', 'target': 'c', 'weight': 1}, {'uid': 'b-d', 'source': 'b', 'target': 'd', 'weight': 1}, {'uid': 'c-a', 'source': 'c', 'target': 'a', 'weight': 1}, {'uid': 'c-b', 'source': 'c', 'target': 'b', 'weight': 1}, {'uid': 'c-d', 'source': 'c', 'target': 'd', 'weight': 1}, {'uid': 'c-f', 'source': 'c', 'target': 'f', 'weight': 1}, {'uid': 'd-c', 'source': 'd', 'target': 'c', 'weight': 1}, {'uid': 'd-b', 'source': 'd', 'target': 'b', 'weight': 1}, {'uid': 'd-a', 'source': 'd', 'target': 'a', 'weight': 1}, {'uid': 'e-f', 'source': 'e', 'target': 'f', 'weight': 1}, {'uid': 'e-g', 'source': 'e', 'target': 'g', 'weight': 1}, {'uid': 'f-c', 'source': 'f', 'target': 'c', 'weight': 1}, {'uid': 'f-e', 'source': 'f', 'target': 'e', 'weight': 1}, {'uid': 'f-g', 'source': 'f', 'target': 'g', 'weight': 1}, {'uid': 'f-h', 'source': 'f', 'target': 'h', 'weight': 1}, {'uid': 'g-e', 'source': 'g', 'target': 'e', 'weight': 1}, {'uid': 'g-f', 'source': 'g', 'target': 'f', 'weight': 1}, {'uid': 'g-h', 'source': 'g', 'target': 'h', 'weight': 1}, {'uid': 'h-f', 'source': 'h', 'target': 'f', 'weight': 1}, {'uid': 'h-g', 'source': 'h', 'target': 'g', 'weight': 1}], 'nodes': [{'uid': 'a', 'label': 'a', 'color': '#00ff00'}, {'uid': 'b', 'label': 'b', 'color': '#00ff00'}, {'uid': 'c', 'label': 'c', 'color': '#00ff00'}, {'uid': 'd', 'label': 'd', 'color': '#00ff00'}, {'uid': 'e', 'label': 'e', 'color': '#ff0000'}, {'uid': 'f', 'label': 'f', 'color': '#ff0000'}, {'uid': 'g', 'label': 'g', 'color': '#ff0000'}, {'uid': 'h', 'label': 'h', 'color': '#ff0000'}]}

To generate a graph with three fully connected cliques, we can specify the parameters as follows:

In [49]:

M = np.matrix('1 0 0;0 1 0;0 0 1')
print(M)
z = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2])
g = pp.algorithms.generative_models.stochastic_block_model(M, z, pp.IndexMap(list('abcdefghi')))
print(g)
pp.plot(g, node_label=g.nodes, node_color=z.tolist());

M = np.matrix('1 0 0;0 1 0;0 0 1') print(M) z = np.array([0, 0, 0, 1, 1, 1, 2, 2, 2]) g = pp.algorithms.generative_models.stochastic_block_model(M, z, pp.IndexMap(list('abcdefghi'))) print(g) pp.plot(g, node_label=g.nodes, node_color=z.tolist());

[[1 0 0]
 [0 1 0]
 [0 0 1]]
Undirected graph with 9 nodes and 18 (directed) edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
{'edges': [{'uid': 'a-c', 'source': 'a', 'target': 'c', 'weight': 1}, {'uid': 'a-b', 'source': 'a', 'target': 'b', 'weight': 1}, {'uid': 'b-a', 'source': 'b', 'target': 'a', 'weight': 1}, {'uid': 'b-c', 'source': 'b', 'target': 'c', 'weight': 1}, {'uid': 'c-a', 'source': 'c', 'target': 'a', 'weight': 1}, {'uid': 'c-b', 'source': 'c', 'target': 'b', 'weight': 1}, {'uid': 'd-e', 'source': 'd', 'target': 'e', 'weight': 1}, {'uid': 'd-f', 'source': 'd', 'target': 'f', 'weight': 1}, {'uid': 'e-f', 'source': 'e', 'target': 'f', 'weight': 1}, {'uid': 'e-d', 'source': 'e', 'target': 'd', 'weight': 1}, {'uid': 'f-d', 'source': 'f', 'target': 'd', 'weight': 1}, {'uid': 'f-e', 'source': 'f', 'target': 'e', 'weight': 1}, {'uid': 'g-h', 'source': 'g', 'target': 'h', 'weight': 1}, {'uid': 'g-i', 'source': 'g', 'target': 'i', 'weight': 1}, {'uid': 'h-g', 'source': 'h', 'target': 'g', 'weight': 1}, {'uid': 'h-i', 'source': 'h', 'target': 'i', 'weight': 1}, {'uid': 'i-g', 'source': 'i', 'target': 'g', 'weight': 1}, {'uid': 'i-h', 'source': 'i', 'target': 'h', 'weight': 1}], 'nodes': [{'uid': 'a', 'label': 'a', 'color': '#00ff00'}, {'uid': 'b', 'label': 'b', 'color': '#00ff00'}, {'uid': 'c', 'label': 'c', 'color': '#00ff00'}, {'uid': 'd', 'label': 'd', 'color': '#7f7f00'}, {'uid': 'e', 'label': 'e', 'color': '#7f7f00'}, {'uid': 'f', 'label': 'f', 'color': '#7f7f00'}, {'uid': 'g', 'label': 'g', 'color': '#ff0000'}, {'uid': 'h', 'label': 'h', 'color': '#ff0000'}, {'uid': 'i', 'label': 'i', 'color': '#ff0000'}]}

In [55]:

from pathpyG.algorithms import connected_components

from pathpyG.algorithms import connected_components

In [56]:

connected_components(g)

connected_components(g)

Out[56]:

(3, array([0, 0, 0, 1, 1, 1, 2, 2, 2], dtype=int32))