Network Generators

A Network Generator can be used to sample random networks for usage in one of the models. Simply define the generator and call it to sample a network, for example:

from sponet import ErdosRenyiGenerator

er_generator = ErdosRenyiGenerator(1000, 0.1)
network = er_generator()

The available generators are listed below.

ErdosRenyiGenerator(num_agents, p, max_sample_time=10, rng=default_rng(), force_no_isolates=False)

Generate Erdös-Renyi (binomial) random graphs.

The random graph may contain isolated vertices, which is not allowed. In that case, the Generator samples until a valid network is found, or until max_sample_time seconds pass, in which case a RuntimeError is raised.

Parameters:

• num_agents (int) –
• p (float) –
• max_sample_time (float, default: 10 ) –

  In seconds.

• rng (Generator, default: default_rng() ) –

  random number generator

• force_no_isolates (bool, default: False ) –

  If set to true, one random edge will be added to each isolated vertex, resulting in a network without isolates.

Source code in sponet/network_generator.py

def __init__(
    self,
    num_agents: int,
    p: float,
    max_sample_time: float = 10,
    rng: Generator = default_rng(),
    force_no_isolates: bool = False,
):
    """
    Generate Erdös-Renyi (binomial) random graphs.

    The random graph may contain isolated vertices, which is not allowed.
    In that case, the Generator samples until a valid network is found,
    or until max_sample_time seconds pass, in which case a RuntimeError is raised.

    Parameters
    ----------
    num_agents : int
    p : float
    max_sample_time : float, optional
        In seconds.
    rng : Generator, optional
        random number generator
    force_no_isolates : bool, optional
        If set to true, one random edge will be added to each isolated vertex,
        resulting in a network without isolates.
    """
    self.num_agents = num_agents
    self.p = p
    self.max_sample_time = max_sample_time
    self.rng = rng
    self.force_no_isolates = force_no_isolates

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    gnp_fun = nx.erdos_renyi_graph if self.p > 0.2 else nx.fast_gnp_random_graph
    start = time.time()
    while True:
        network = gnp_fun(self.num_agents, self.p, seed=self.rng)
        if nx.number_of_isolates(network) == 0:
            return network

        if self.force_no_isolates:
            _unisolate_vertices(network, self.rng)
            return network

        if time.time() - start > self.max_sample_time:
            raise RuntimeError(
                "Timeout. Could not generate a graph without isolated vertices."
            )

RandomRegularGenerator(num_agents, d, rng=default_rng())

Generate random regular graphs.

Parameters:

• num_agents (int) –
• d (int) –
• rng (Generator, default: default_rng() ) –

  random number generator

Source code in sponet/network_generator.py

def __init__(self, num_agents: int, d: int, rng: Generator = default_rng()):
    """
    Generate random regular graphs.

    Parameters
    ----------
    num_agents : int
    d : int
    rng : Generator, optional
        random number generator
    """
    self.num_agents = num_agents
    self.d = d
    self.rng = rng

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    return nx.random_regular_graph(self.d, self.num_agents, seed=self.rng)

BarabasiAlbertGenerator(num_agents, m, rng=default_rng())

Generate random scale-free graphs using the Barabasi-Albert model.

Parameters:

• num_agents (int) –
• m (int) –
• rng (Generator, default: default_rng() ) –

  random number generator

Source code in sponet/network_generator.py

def __init__(self, num_agents: int, m: int, rng: Generator = default_rng()):
    """
    Generate random scale-free graphs using the Barabasi-Albert model.

    Parameters
    ----------
    num_agents : int
    m : int
    rng : Generator, optional
        random number generator
    """
    self.num_agents = num_agents
    self.m = m
    self.rng = rng

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    return nx.barabasi_albert_graph(self.num_agents, self.m, seed=self.rng)

WattsStrogatzGenerator(num_agents, num_neighbors, p, rng=default_rng())

Create random small-world networks using the Watts-Strogatz model.

Parameters:

• num_agents (int) –
• num_neighbors (int) –
• p (float) –
• rng (Generator, default: default_rng() ) –

  random number generator

Source code in sponet/network_generator.py

def __init__(
    self,
    num_agents: int,
    num_neighbors: int,
    p: float,
    rng: Generator = default_rng(),
):
    """
    Create random small-world networks using the Watts-Strogatz model.

    Parameters
    ----------
    num_agents : int
    num_neighbors : int
    p : float
    rng : Generator, optional
        random number generator
    """
    self.num_agents = num_agents
    self.num_neighbors = num_neighbors
    self.p = p
    self.rng = rng

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    return nx.connected_watts_strogatz_graph(
        self.num_agents, self.num_neighbors, self.p, seed=self.rng
    )

StochasticBlockGenerator(num_agents, p_matrix, max_sample_time=10, rng=default_rng())

Creates n stochastic blocks, block i is randomly connected to block j with edge density p_matrix[i, j].

The random graph may contain isolated vertices, which is not allowed. In that case, the Generator samples until a valid network is found, or until max_sample_time seconds pass, in which case a RuntimeError is raised.

Parameters:

• num_agents (int) –
• p_matrix (ArrayLike) –

  (n x n) matrix of edge probabilities.

• max_sample_time (float, default: 10 ) –

  In seconds.

• rng (Generator, default: default_rng() ) –

  random number generator

Source code in sponet/network_generator.py

def __init__(
    self,
    num_agents: int,
    p_matrix: ArrayLike,
    max_sample_time: float = 10,
    rng: Generator = default_rng(),
):
    """
    Creates n stochastic blocks, block i is randomly connected to block j with edge density p_matrix[i, j].

    The random graph may contain isolated vertices, which is not allowed.
    In that case, the Generator samples until a valid network is found,
    or until max_sample_time seconds pass, in which case a RuntimeError is raised.

    Parameters
    ----------
    num_agents : int
    p_matrix : ArrayLike
        (n x n) matrix of edge probabilities.
    max_sample_time : float, optional
        In seconds.
    rng : Generator, optional
        random number generator
    """
    self.p_matrix = np.array(p_matrix, ndmin=2)
    self.max_sample_time = max_sample_time

    self.num_blocks = self.p_matrix.shape[0]
    self.block_size = int(num_agents / self.num_blocks)
    self.num_agents = self.block_size * self.num_blocks
    self.rng = rng

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    start = time.time()
    while True:
        adj_mat = self._sample_adj_matrix()
        network = nx.from_numpy_array(adj_mat)
        if nx.number_of_isolates(network) == 0:
            return network

        if time.time() - start > self.max_sample_time:
            raise RuntimeError(
                "Timeout. Could not generate a graph without isolated vertices."
            )

GridGenerator(num_agents, periodic=False)

Generate lattice graph in 2 dimensions.

Parameters:

• num_agents (int) –
• periodic (bool, default: False ) –

Source code in sponet/network_generator.py

def __init__(self, num_agents: int, periodic: bool = False):
    """
    Generate lattice graph in 2 dimensions.

    Parameters
    ----------
    num_agents : int
    periodic : bool, optional
    """
    self.num_agents = num_agents
    self.dim = 2  # only implemented for 2D grids for now
    self.periodic = periodic

    # find shape as square as possible
    shape0 = round(num_agents**0.5)
    while num_agents % shape0 != 0:
        shape0 += 1
    shape1 = int(num_agents / shape0)
    self.shape = shape0, shape1

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    g = nx.grid_graph(self.shape, periodic=self.periodic)

    relabel_dict = {}
    for i, val in enumerate(g.nodes):
        relabel_dict[val] = i

    return nx.relabel_nodes(g, relabel_dict)

BinomialWattsStrogatzGenerator(num_agents, num_neighbors, p_rewire, max_sample_time=10, rng=default_rng())

Creates a ring where each node is connected to the num_neighbors nearest neighbors. (num_neighbors needs to be even!) Then iterate through each edge and rip it out with probability p_rewire. Then iterate through all the possible edges that are not present and insert with such a probability, that in expectation the resulting graph has the same number of edges again. For p=1, this yields the binomial Erdös-Renyi graph G(N, K/N).

The random graph may contain isolated vertices, which is not allowed. In that case, the Generator samples until a valid network is found, or until max_sample_time seconds pass, in which case a RuntimeError is raised.

Parameters:

• num_agents (int) –
• num_neighbors (int) –
• p_rewire (float) –
• max_sample_time (float, default: 10 ) –

  In seconds.

• rng (Generator, default: default_rng() ) –

  random number generator

Source code in sponet/network_generator.py

def __init__(
    self,
    num_agents: int,
    num_neighbors: int,
    p_rewire: float,
    max_sample_time: float = 10,
    rng: Generator = default_rng(),
):
    """
    Creates a ring where each node is connected to the num_neighbors nearest neighbors.
    (num_neighbors needs to be even!)
    Then iterate through each edge and rip it out with probability p_rewire.
    Then iterate through all the possible edges that are not present and insert with such a probability,
    that in expectation the resulting graph has the same number of edges again.
    For p=1, this yields the binomial Erdös-Renyi graph G(N, K/N).

    The random graph may contain isolated vertices, which is not allowed.
    In that case, the Generator samples until a valid network is found,
    or until max_sample_time seconds pass, in which case a RuntimeError is raised.

    Parameters
    ----------
    num_agents : int
    num_neighbors : int
    p_rewire : float
    max_sample_time : float, optional
        In seconds.
    rng : Generator, optional
        random number generator
    """
    self.num_agents = num_agents
    self.num_neighbors = num_neighbors
    self.p_rewire = p_rewire
    self.max_sample_time = max_sample_time

    self.p_insert = (
        p_rewire * num_neighbors / (num_agents - 1 - (1 - p_rewire) * num_neighbors)
    )
    self.gnp_fun = (
        nx.erdos_renyi_graph if self.p_insert > 0.2 else nx.fast_gnp_random_graph
    )
    self.rng = rng

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    start = time.time()
    while True:
        network = self._sample_network()
        if nx.number_of_isolates(network) == 0:
            return network

        if time.time() - start > self.max_sample_time:
            raise RuntimeError(
                "Timeout. Could not generate a graph without isolated vertices."
            )

BianconiBarabasiGenerator(num_agents, m, lamda, rng=default_rng())

Generate random graphs using the Bianconi-Barabasi model.

Every node has a fitness eta in [0,1] that is drawn randomly from the distribution with density p(eta) = (lambda + 1) (1 - eta)^lambda. Each new node i is linked to m existing nodes. The probability for a link between the new node i and an existing node j is proportional to eta_j d_j, where d_j is the degree of node j.

For lambda > 1, the network undergoes Bose-Einstein condensation, i.e., there is one node that maintains a non-vanishing fraction of the links (winner takes it all). For lambda < 1, the fittest nodes accumulate most links, but every node has a vanishing fraction of links (fit get rich).

Parameters:

• num_agents (int) –
• m (int) –
• lamda (float) –
• rng (Generator, default: default_rng() ) –

  random number generator

Source code in sponet/network_generator.py

def __init__(
    self, num_agents: int, m: int, lamda: float, rng: Generator = default_rng()
):
    """
    Generate random graphs using the Bianconi-Barabasi model.

    Every node has a fitness eta in [0,1] that is drawn randomly from the distribution with density
    p(eta) = (lambda + 1) (1 - eta)^lambda.
    Each new node i is linked to m existing nodes.
    The probability for a link between the new node i and an existing node j is proportional to
    eta_j d_j, where d_j is the degree of node j.

    For lambda > 1, the network undergoes Bose-Einstein condensation, i.e., there is one node that
    maintains a non-vanishing fraction of the links (winner takes it all).
    For lambda < 1, the fittest nodes accumulate most links,
    but every node has a vanishing fraction of links (fit get rich).

    Parameters
    ----------
    num_agents : int
    m : int
    lamda: float
    rng : Generator, optional
        random number generator
    """
    self.num_agents = num_agents
    self.m = m
    self.lamda = lamda
    self.rng = rng

__call__()

Sample a network from the Network Generator.

Source code in sponet/network_generator.py

def __call__(self) -> nx.Graph:
    """
    Sample a network from the Network Generator.
    """
    g = nx.star_graph(self.m)
    degrees = np.array([d for _, d in g.degree()])
    degrees = np.concatenate(
        [degrees, np.ones(self.num_agents - len(degrees)) * self.m]
    )
    fitness_values = self.rng.beta(1, self.lamda + 1, self.num_agents)

    for size_g in range(len(g), self.num_agents):
        probabilities = degrees[:size_g] * fitness_values[:size_g]
        probabilities /= np.sum(probabilities)
        nodes_to_link = self.rng.choice(
            size_g, size=self.m, replace=False, p=probabilities, shuffle=False
        )
        g.add_edges_from(zip([size_g] * self.m, nodes_to_link))

        for other in nodes_to_link:
            degrees[other] += 1

    return g