File randgraph.hpp

FileList > epiworld > randgraph.hpp

Go to the source code of this file

Public Static Attributes

Type	Name
constexpr long long	BB_FPU_THRESHOLD = 200

Public Functions

Type	Name
void	rewire_degseq (TDat * agents, Model< TSeq > * model, epiworld_double proportion)
void	rewire_degseq (std::vector< Agent< TSeq > > * agents, Model< TSeq > * model, epiworld_double proportion)
void	rewire_degseq (AdjList * agents, Model< TSeq > * model, epiworld_double proportion)
AdjList	rgraph_bernoulli (epiworld_fast_uint n, epiworld_double p, bool directed, Model< TSeq > & model) Generates an Erdős–Rényi random graph G(n, p) using the Batagelj-Brandes algorithm.
AdjList	rgraph_bernoulli2 (epiworld_fast_uint n, epiworld_double p, bool directed, Model< TSeq > & model)
AdjList	rgraph_blocked (epiworld_fast_uint n, epiworld_fast_uint blocksize, epiworld_fast_uint ncons, Model< TSeq > &) Generates a blocked network.
AdjList	rgraph_ring_lattice (epiworld_fast_uint n, epiworld_fast_uint k, bool directed=false)
AdjList	rgraph_sbm (const std::vector< size_t > & block_sizes, const std::vector< double > & mixing_matrix, bool row_major, Model< TSeq > & model) Generates a network using a Stochastic Block Model (SBM).
AdjList	rgraph_smallworld (epiworld_fast_uint n, epiworld_fast_uint k, epiworld_double p, bool directed, Model< TSeq > & model) Smallworld network (Watts-Strogatz)

Public Static Attributes Documentation

variable BB_FPU_THRESHOLD

constexpr long long BB_FPU_THRESHOLD;

Threshold for the hybrid row-advance in Batagelj-Brandes.

When a geometric skip lands past the current row of the lower-triangle enumeration, the flat index must be mapped back to (i, j). For small excess (j - i <= threshold) the integer while-loop is fastest; for large excess the O(1) inverse-triangular-number formula avoids O(sqrt(excess)) iterations. 200 keeps the loop body to at most ~20 iterations (sqrt(2 * 200) ~ 20) before switching to FPU math.

---

Public Functions Documentation

function rewire_degseq

template<typename TSeq, typename TDat>
inline void rewire_degseq (
    TDat * agents,
    Model < TSeq > * model,
    epiworld_double proportion
) 

---

function rewire_degseq

template<typename TSeq>
inline void rewire_degseq (
    std::vector< Agent < TSeq > > * agents,
    Model < TSeq > * model,
    epiworld_double proportion
) 

---

function rewire_degseq

template<typename TSeq>
inline void rewire_degseq (
    AdjList * agents,
    Model < TSeq > * model,
    epiworld_double proportion
) 

---

function rgraph_bernoulli

Generates an Erdős–Rényi random graph G(n, p) using the Batagelj-Brandes algorithm.

template<typename TSeq>
inline AdjList rgraph_bernoulli (
    epiworld_fast_uint n,
    epiworld_double p,
    bool directed,
    Model < TSeq > & model
) 

Uses geometric skipping to advance through the space of possible edges, generating each edge independently with probability p. This produces unbiased edge counts in O(n + m) expected time, where m is the number of edges generated.

Reference: V. Batagelj and U. Brandes, "Efficient generation of large random networks," Physical Review E, vol. 71, no. 3, 2005.

Template parameters:

• TSeq Type of the sequence (template parameter of the model).

Parameters:

• n Number of nodes.
• p Edge probability.
• directed Whether the graph is directed.
• model A reference to the Model, used for random number generation.

Returns:

An AdjList representing the generated network.

---

function rgraph_bernoulli2

template<typename TSeq>
inline AdjList rgraph_bernoulli2 (
    epiworld_fast_uint n,
    epiworld_double p,
    bool directed,
    Model < TSeq > & model
) 

---

function rgraph_blocked

Generates a blocked network.

template<typename TSeq>
inline AdjList rgraph_blocked (
    epiworld_fast_uint n,
    epiworld_fast_uint blocksize,
    epiworld_fast_uint ncons,
    Model < TSeq > &
) 

Since block sizes and number of connections between blocks are fixed, this routine is fully deterministic.

Template parameters:

• TSeq

Parameters:

• n Size of the network
• blocksize Size of the block.
• ncons Number of connections between blocks
• model A model

Returns:

AdjList

---

function rgraph_ring_lattice

inline AdjList rgraph_ring_lattice (
    epiworld_fast_uint n,
    epiworld_fast_uint k,
    bool directed=false
) 

---

function rgraph_sbm

Generates a network using a Stochastic Block Model (SBM).

template<typename TSeq>
inline AdjList rgraph_sbm (
    const std::vector< size_t > & block_sizes,
    const std::vector< double > & mixing_matrix,
    bool row_major,
    Model < TSeq > & model
) 

This function creates a random undirected network where connections between agents are determined by a mixing matrix and block (group) membership. Each potential edge between agents in blocks \(g\) and \(h\) is included independently with probability \(M(g, h) / n_h\), where \(M(g, h)\) is the entry of the mixing matrix and \(n_h\) is the number of agents in block \(h\).

The mixing matrix is not row-stochastic. For undirected networks, its row sums should be interpreted as the average expected degree for agents in that group only when the balance condition \(M(g, h) \times n_g = M(h, g) \times n_h\) holds for all pairs \((g, h)\). In that balanced case, \(\[ \mathbb{E}[\text{degree of agent in group } g] = \sum_{h} M(g, h) \]\)

For undirected networks, the implementation samples between-block edges only once for each unordered pair of blocks (with \(g \le h\)) using \(M(g, h) / n_h\). Therefore, if the balance condition is violated, the row sums generally do not match the expected degree from every group's perspective.

Unbiased generation. Edge generation uses the Batagelj-Brandes algorithm (geometric skipping) independently for each block pair. Each possible edge is included with exactly the correct probability, with no duplicate edge collisions. The expected number of edges for a block pair is exactly: * Within-block: [\binom{n_g}{2} \times p_{gg}]

• Between-block: [n_g \times n_h \times p_{gh}]

Balance condition warning. If the balance condition is violated for any pair of blocks and the model's verbose mode is on, a warning is printed indicating which entries are being silently ignored.

Reference: V. Batagelj and U. Brandes, "Efficient generation of large random networks," Physical Review E, vol. 71, no. 3, 2005.

Template parameters:

• TSeq Type of the sequence (template parameter of the model).

Parameters:

• block_sizes A vector of size \(K\) indicating the number of agents per block. The total number of agents is \(\sum_k \text{block\_sizes}[k]\).
• mixing_matrix A vector of size \(K \times K\) representing the mixing matrix. The entry \(M(g, h)\) controls the expected number of connections agents in group \(g\) make with agents in group \(h\).
• row_major If true, the mixing matrix is stored in row-major order (C-style), i.e., \(M(g, h) = \text{mixing\_matrix}[g \times K + h]\). If false, column-major order (Fortran-style) is assumed, i.e., \(M(g, h) = \text{mixing\_matrix}[h \times K + g]\).
• model A reference to the Model, used for random number generation.

Returns:

An AdjList representing the generated undirected network.

Exception:

• std::length_error If block_sizes is empty, mixing_matrix size does not equal \(K^2\), or any block size is zero.
• std::range_error If any mixing matrix entry is negative or if \(M(g, h) / n_h > 1\) for any pair of blocks.

---

function rgraph_smallworld

Smallworld network (Watts-Strogatz)

template<typename TSeq>
inline AdjList rgraph_smallworld (
    epiworld_fast_uint n,
    epiworld_fast_uint k,
    epiworld_double p,
    bool directed,
    Model < TSeq > & model
) 

Template parameters:

• TSeq

Parameters:

• n
• k
• p
• directed
• model

Returns:

AdjList

---

---

The documentation for this class was generated from the following file include/epiworld/randgraph.hpp