OpenBI Docs Buy

Random graphs

Random graph models: uniform random graphs and block models, preferential attachment and other growth models, degree sequences and fitness, rewiring, and geometric graphs. Every model draws from Open Graph's random number generator.

35 entries: 34 functions and 1 type. Part of the Open Graph reference; All functions lists every entry on one page, with a filter. The badges say how each entry is checked.

Types

edge_type_sw_ttype#

Unit tests

Bit switches saying which non-simple edges a function may create.

typedef unsigned int og_edge_type_sw_t;
#define OG_SIMPLE_SW 0x00u
#define OG_LOOPS_SW 0x01u
#define OG_MULTI_SW 0x06u

An unsigned integer of flags combined with |: OG_SIMPLE_SW (0) allows neither self-loops nor multi-edges, OG_LOOPS_SW (0x01) allows self-loops, OG_MULTI_SW (0x06) allows multi-edges, and OG_LOOPS_SW | OG_MULTI_SW both. The values are the ones python-igraph 1.0 exposes; a value with either of the two multi bits allows multi-edges, so test with a mask: (x & OG_MULTI_SW) != 0.

The games refuse unknown bits with OG_EINVAL, rewire() with OG_EINVMODE. Declared in og/foundation/types.h, since functions of several areas (games, generators, operators, structure) take it.

Parameters
  • OG_SIMPLE_SW 0x00: neither self-loops nor multi-edges.
  • OG_LOOPS_SW 0x01: self-loops allowed.
  • OG_MULTI_SW 0x06: multi-edges allowed (either bit counts).
Checked
Values 0x00, 0x01 and 0x06 as python-igraph 1.0 exposes them; tested through the functions that take it.
C name
og_edge_type_sw_t
In notebooks
uint
igraph 1.0
igraph_edge_type_sw_t
See also
erdos_renyi_game_gnm, sbm_game, static_fitness_game, realize_degree_sequence, rewire, is_graphical

Uniform and block models

erdos_renyi_game_gnm#

Same quality

Draws a uniformly random graph with n vertices and exactly m edges, G(n, m).

og_error_t og_erdos_renyi_game_gnm(
    og_t *graph,
    og_int_t n,
    og_int_t m,
    og_bool_t directed,
    og_edge_type_sw_t allowed_edge_types,
    og_bool_t edge_labeled
);

Without multi-edges the m edges are a uniformly random set of m distinct vertex pairs (self-pairs included with OG_LOOPS_SW), so every graph with n vertices and m edges is equally likely (Erdős and Rényi 1959). With OG_MULTI_SW and edge_labeled false the result is a uniform multiset of m pairs: every multigraph with m edges is equally likely. With OG_MULTI_SW and edge_labeled true each edge is placed independently on a uniform pair, as iea_game() does.

edge_labeled false lists the edges in a fixed pair order (by second endpoint, then first; directed loop-free graphs row by row), the order python-igraph 1.0 gives; true lists them in a uniformly random order. Asking for every pair gives the complete graph. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices.
  • m The number of edges.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
  • edge_labeled OG_EDGE_UNLABELED or OG_EDGE_LABELED: whether the order of the edges is part of the random outcome (see the description).
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EINVAL n or m is negative
  • OG_EINVAL m > 0 but there is no vertex pair to connect
  • OG_EINVAL without multi-edges, m exceeds the number of vertex pairs
  • OG_EOVERFLOW the number of vertex pairs is too large
  • OG_ENOMEM there is not enough memory
Complexity
O(n + m) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 10 cases x 400 samples on summary statistics, and the whole output distribution of tiny cases (chi-square on the graphs and on the edge lists as listed). The complete graph and the listing order match exactly. Multigraphs are checked against the exact uniform-multiset law, which python-igraph cannot be asked for.
C name
og_erdos_renyi_game_gnm
In notebooks
Og.ErdosRenyiGameGnm
igraph 1.0
igraph_erdos_renyi_game_gnm
See also
erdos_renyi_game_gnp, iea_game, sbm_game, bipartite_game_gnm
og_t g;
og_rng_seed(og_rng_default(), 42);  /* same seed, same graph */
og_erdos_renyi_game_gnm(&g, 100, 250, OG_UNDIRECTED, OG_SIMPLE_SW, OG_EDGE_UNLABELED);
og_destroy(&g);

erdos_renyi_game_gnp#

Same quality

Draws a random graph in which every vertex pair is joined independently with probability p, G(n, p).

og_error_t og_erdos_renyi_game_gnp(
    og_t *graph,
    og_int_t n,
    og_real_t p,
    og_bool_t directed,
    og_edge_type_sw_t allowed_edge_types,
    og_bool_t edge_labeled
);

Every allowed pair (self-pairs too with OG_LOOPS_SW) gets an edge with probability p (Gilbert 1959). The pairs with an edge are found by geometric skipping (Batagelj and Brandes 2005), so the time grows with the edges drawn, not with n^2. Without multi-edges p = 1 gives the complete graph, listed row by row.

With OG_MULTI_SW, p is the mean number of edges per pair and may exceed 1: each pair gets a geometric number of edges, P(k) = q (1 - q)^k with q = 1 / (1 + p). With edge_labeled as well, the edge count is geometric with mean p per vertex pair and the edges fall on independent uniform pairs; edge_labeled without OG_MULTI_SW is not available. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices.
  • p The edge probability, 0..1; with OG_MULTI_SW the mean edge count per pair, any finite value >= 0.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
  • edge_labeled OG_EDGE_UNLABELED, or OG_EDGE_LABELED (with OG_MULTI_SW only).
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EINVAL n is negative
  • OG_EINVAL p is NaN, negative or infinite, or above 1 without multi-edges
  • OG_UNIMPLEMENTED edge_labeled is set without OG_MULTI_SW
  • OG_EOVERFLOW too many vertex pairs or edges
  • OG_ENOMEM there is not enough memory
Complexity
O(n + m) expected, m the edges drawn.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 9 simple and loop cases and 4 multigraph cases (through python-igraph's one-block SBM, the same model), 400 samples each, and whole output distributions of tiny cases. p = 1 matches exactly. The labeled multigraph ensemble is checked against its own law only.
C name
og_erdos_renyi_game_gnp
In notebooks
Og.ErdosRenyiGameGnp
igraph 1.0
igraph_erdos_renyi_game_gnp
See also
erdos_renyi_game_gnm, sbm_game, bipartite_game_gnp, correlated_game
og_t g;
og_rng_seed(og_rng_default(), 7);
og_erdos_renyi_game_gnp(&g, 1000, 0.005, OG_DIRECTED, OG_SIMPLE_SW, OG_EDGE_UNLABELED);
og_destroy(&g);

iea_game#

Same quality

Places m edges independently on uniformly random vertex pairs (independent edge assignment).

og_error_t og_iea_game(
    og_t *graph,
    og_int_t n,
    og_int_t m,
    og_bool_t directed,
    og_bool_t loops
);

Each of the m edges picks an ordered pair (u, v) uniformly, with u != v unless loops is set; repeated pairs give multi-edges. An undirected graph drops the order of the pair, so a pair {u, v} with u != v is twice as likely as a given self-loop. Edges are listed in the order they are drawn. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices.
  • m The number of edges.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • loops true to allow self-loops.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL n or m is negative
  • OG_EINVAL m > 0 but there is no admissible pair (n = 0, or n = 1 without loops)
  • OG_ENOMEM there is not enough memory
Complexity
O(n + m).
Checked
python-igraph does not expose it: checked against the exact law (loop, pair and ordered-pair frequencies over 3,000 samples); errors as the definition says.
C name
og_iea_game
In notebooks
Og.IeaGame
igraph 1.0
igraph_iea_game
See also
erdos_renyi_game_gnm, erdos_renyi_game_gnp

sbm_game#

Same quality

Draws a random graph with block structure: blocks of consecutive vertices and one connection probability per block pair (stochastic block model).

og_error_t og_sbm_game(
    og_t *graph,
    const og_matrix_t *pref_matrix,
    const og_vector_int_t *block_sizes,
    og_bool_t directed,
    og_edge_type_sw_t allowed_edge_types
);

Vertices are split into consecutive blocks of the given sizes. A pair (u, v) with u in block i and v in block j is joined with probability pref_matrix[i][j], independently of every other pair (Holland, Laskey and Leinhardt 1983); an undirected graph needs a symmetric matrix. Self-pairs count only with OG_LOOPS_SW. With OG_MULTI_SW the entries are mean edge counts per pair, with geometric multiplicities as in erdos_renyi_game_gnp(), and may exceed 1.

Edges are listed block pair by block pair, row by row, and inside a block pair by target, then source, as python-igraph 1.0 lists them. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • pref_matrix k x k connection probabilities (mean edge counts with OG_MULTI_SW).
  • block_sizes The k block sizes; their sum is the vertex count.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EINVAL pref_matrix is not square
  • OG_EINVAL block_sizes does not have one entry per row, or has a negative entry
  • OG_EINVAL an entry is NaN, negative or infinite, or above 1 without multi-edges
  • OG_EINVAL the graph is undirected and pref_matrix is not symmetric
  • OG_EOVERFLOW a block pair has too many vertex pairs
  • OG_ENOMEM there is not enough memory
Complexity
O(n + m + k^2) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 7 cases x 400 samples (all four edge-type settings, an empty block) and whole output distributions of 5 tiny cases. 0/1 matrices give python-igraph's exact edge order; 6 error cases match.
C name
og_sbm_game
In notebooks
Og.SbmGame
igraph 1.0
igraph_sbm_game
See also
erdos_renyi_game_gnp, hsbm_game, preference_game
og_t g;
og_matrix_t pref;
og_vector_int_t sizes;
og_matrix_init(&pref, 2, 2);
OG_MATRIX(pref, 0, 0) = OG_MATRIX(pref, 1, 1) = 0.2;   /* dense inside blocks */
OG_MATRIX(pref, 0, 1) = OG_MATRIX(pref, 1, 0) = 0.01;  /* sparse between them */
og_vector_int_init_int(&sizes, 2, 50, 50);
og_sbm_game(&g, &pref, &sizes, OG_UNDIRECTED, OG_SIMPLE_SW);
og_vector_int_destroy(&sizes);
og_matrix_destroy(&pref);
og_destroy(&g);

hsbm_game#

Same quality

Draws a hierarchical stochastic block model: equal blocks sharing one internal cluster structure.

og_error_t og_hsbm_game(
    og_t *graph,
    og_int_t n,
    og_int_t m,
    const og_vector_t *rho,
    const og_matrix_t *C,
    og_real_t p
);

The n vertices form n / m blocks of m consecutive vertices. Inside every block the vertices are split into consecutive clusters of rho[i] m vertices, and two vertices of the same block in clusters i and j are joined with probability C[i][j]. Two vertices in different blocks are joined with probability p. All pairs are independent; the graph is undirected and simple.

rho must add up to 1 and every rho[i] m must be a whole number; C must be symmetric. Edges are listed block by block, then the edges between blocks. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices, a multiple of m.
  • m The number of vertices per block.
  • rho The cluster fractions inside a block; they add up to 1.
  • C Symmetric matrix of connection probabilities between the clusters.
  • p The connection probability between vertices of different blocks.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL n is negative, m is below 1, or n is not a multiple of m
  • OG_EINVAL p is not in [0, 1]
  • OG_EINVAL rho is empty, has an entry outside [0, 1], does not add up to 1, or an entry times the block size is not a whole number
  • OG_EINVAL C is not square with one row per cluster, has an entry that is not a probability, or is not symmetric
  • OG_ENOMEM there is not enough memory
Complexity
O(n + |E| + (n/m) k^2) expected, k the number of clusters.
Checked
python-igraph does not expose it: two deterministic cases (0/1 rates) match igraph 1.0.1's C library edge by edge; pair frequencies inside clusters and between blocks checked against the model; errors as the definition says.
C name
og_hsbm_game
In notebooks
Og.HsbmGame
igraph 1.0
igraph_hsbm_game
See also
hsbm_list_game, sbm_game

hsbm_list_game#

Same quality

Draws a hierarchical stochastic block model whose blocks have their own sizes and cluster structures.

og_error_t og_hsbm_list_game(
    og_t *graph,
    og_int_t n,
    const og_vector_int_t *mlist,
    const og_vector_list_t *rholist,
    const og_matrix_list_t *Clist,
    og_real_t p
);

As hsbm_game(), but block b has mlist[b] consecutive vertices, its own cluster fractions rholist[b] and its own rate matrix Clist[b]. The block sizes must add up to n. Vertices in different blocks are joined with probability p. Undirected and simple; no blocks gives the empty graph. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices; the sum of mlist.
  • mlist The size of each block.
  • rholist The cluster fractions of each block.
  • Clist The cluster connection probabilities of each block.
  • p The connection probability between vertices of different blocks.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL n is negative
  • OG_EINVAL rholist or Clist does not have one entry per block
  • OG_EINVAL a block size is below 1, or the sizes do not add up to n
  • OG_EINVAL p is not in [0, 1]
  • OG_EINVAL rho is empty, has an entry outside [0, 1], does not add up to 1, or an entry times the block size is not a whole number
  • OG_EINVAL C is not square with one row per cluster, has an entry that is not a probability, or is not symmetric
  • OG_ENOMEM there is not enough memory
Complexity
O(n + |E| + sum of k_b^2) expected.
Checked
python-igraph does not expose it: a deterministic case matches igraph 1.0.1's C library edge by edge; errors as the definition says.
C name
og_hsbm_list_game
In notebooks
Og.HsbmListGame
igraph 1.0
igraph_hsbm_list_game
See also
hsbm_game, sbm_game

preference_game#

Same quality

Draws a graph whose vertices get random types and connect with a type-dependent probability.

og_error_t og_preference_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t types,
    const og_vector_t *type_dist,
    og_bool_t fixed_sizes,
    const og_matrix_t *pref_matrix,
    og_vector_int_t *node_type_vec,
    og_bool_t directed,
    og_bool_t loops
);

Each vertex gets one of types types, drawn from the weights type_dist (NULL for uniform), and a pair (u, v) is then joined with probability pref_matrix[type(u)][type(v)], independently; an undirected graph needs a symmetric matrix. Self-pairs count only with loops; there are no multi-edges.

With fixed_sizes the types are not random: type_dist then holds whole vertex counts that add up to nodes (NULL: sizes as equal as possible), given to consecutive vertices. node_type_vec (may be NULL) receives every vertex's type. Edges are listed type pair by type pair, row by row. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • types The number of types, at least 1.
  • type_dist NULL, or one non-negative weight per type (whole counts with fixed_sizes).
  • fixed_sizes true to assign types in fixed consecutive groups instead of drawing them.
  • pref_matrix types x types connection probabilities.
  • node_type_vec Output, may be NULL: the type of each vertex.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • loops true to allow self-loops.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL types is below 1
  • OG_EINVAL type_dist does not have one entry per type, or has a negative, infinite or NaN entry, or no positive one
  • OG_EINVAL pref_matrix is not types x types, or an entry is not a probability
  • OG_EINVAL the graph is undirected and pref_matrix is not symmetric
  • OG_EINVAL with fixed_sizes, type_dist holds a non-whole count or the counts do not add up to nodes
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes + |E| + types^2) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 5 cases x 400 samples, type shares included, and whole output distributions of 4 tiny cases; 4 error cases match. fixed_sizes cannot be reached from python-igraph and is unit-tested.
C name
og_preference_game
In notebooks
Og.PreferenceGame
igraph 1.0
igraph_preference_game
See also
asymmetric_preference_game, sbm_game, establishment_game

asymmetric_preference_game#

Same quality

Draws a directed graph in which each vertex has an out-type and an in-type.

og_error_t og_asymmetric_preference_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t no_out_types,
    og_int_t no_in_types,
    const og_matrix_t *type_dist_matrix,
    const og_matrix_t *pref_matrix,
    og_vector_int_t *node_type_out_vec,
    og_vector_int_t *node_type_in_vec,
    og_bool_t loops
);

Each vertex gets a pair (out-type, in-type) drawn from the joint weights type_dist_matrix (NULL: both uniform and independent). An edge u -> v appears with probability pref_matrix[out-type(u)][in-type(v)], independently for every ordered pair; u -> u only with loops. The graph is always directed and has no multi-edges.

node_type_out_vec and node_type_in_vec (each may be NULL) receive the types. Edges are listed by (out-type, in-type) block, in python-igraph 1.0's order. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • no_out_types The number of out-types, at least 1.
  • no_in_types The number of in-types, at least 1.
  • type_dist_matrix NULL, or no_out_types x no_in_types non-negative joint weights.
  • pref_matrix no_out_types x no_in_types connection probabilities.
  • node_type_out_vec Output, may be NULL: the out-type of each vertex.
  • node_type_in_vec Output, may be NULL: the in-type of each vertex.
  • loops true to allow self-loops.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL a type count is below 1
  • OG_EINVAL a matrix does not have no_out_types rows and no_in_types columns
  • OG_EINVAL a preference is not a probability
  • OG_EINVAL a joint weight is negative, infinite or NaN, or none is positive
  • OG_EOVERFLOW a block has too many vertex pairs
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes + |E| + out-types x in-types) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 3 cases x 400 samples with out- and in-type shares, and whole output distributions of tiny inputs (20,000 and 4,000 samples); the listing order agrees as well.
C name
og_asymmetric_preference_game
In notebooks
Og.AsymmetricPreferenceGame
igraph 1.0
igraph_asymmetric_preference_game
See also
preference_game, sbm_game

correlated_game#

Same quality

Draws a random graph correlated with a given simple graph.

og_error_t og_correlated_game(
    og_t *new_graph,
    const og_t *old_graph,
    og_real_t corr,
    og_real_t p,
    const og_vector_int_t *permutation
);

Every vertex pair is decided independently: a pair that is an edge of old_graph stays an edge with probability p + corr (1 - p), and a pair that is not becomes one with probability p (1 - corr). If old_graph is a G(n, p) graph, the result is another G(n, p) graph whose edge indicators have correlation corr with the old ones (Lyzinski, Fishkind and Priebe 2014). The result has old_graph's vertex count and directedness and no self-loops.

permutation (NULL for none) relabels the result: vertex i of the new graph stands for vertex permutation[i] of the old one. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • new_graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • old_graph The simple graph to correlate with.
  • corr The correlation, in [0, 1].
  • p The edge density of the model, strictly between 0 and 1.
  • permutation NULL, or a permutation of the vertex ids.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL corr is outside [0, 1] or p is not strictly between 0 and 1
  • OG_EINVAL permutation has the wrong length or is not a permutation
  • OG_EINVAL old_graph has self-loops or multi-edges
  • OG_ENOMEM there is not enough memory
Complexity
O(n + |E_old| + |E_new|) expected.
Checked
python-igraph does not expose it: corr = 1 with a permutation matches igraph 1.0.1's C library exactly; the keep and add probabilities are checked through correlated_pair_game()'s marginals and correlation.
C name
og_correlated_game
In notebooks
Og.CorrelatedGame
igraph 1.0
igraph_correlated_game
See also
correlated_pair_game, erdos_renyi_game_gnp, permute_vertices

correlated_pair_game#

Same quality

Draws two correlated G(n, p) graphs.

og_error_t og_correlated_pair_game(
    og_t *graph1,
    og_t *graph2,
    og_int_t n,
    og_real_t corr,
    og_real_t p,
    og_bool_t directed,
    const og_vector_int_t *permutation
);

graph1 is a simple G(n, p) graph (erdos_renyi_game_gnp()) and graph2 is drawn from it with correlated_game(), so both have edge density p and their edge indicators have correlation corr. permutation (may be NULL) relabels graph2 as in correlated_game(). Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph1 Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • graph2 Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices.
  • corr The correlation, in [0, 1].
  • p The edge density, strictly between 0 and 1.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • permutation NULL, or a permutation of the vertex ids applied to graph2.
Returns
OG_SUCCESS, or an error code. On error neither graph is initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL corr is outside [0, 1] or p is not strictly between 0 and 1
  • OG_EINVAL permutation has the wrong length or is not a permutation
  • OG_ENOMEM there is not enough memory
Complexity
O(n + |E1| + |E2|) expected.
Checked
python-igraph does not expose it: marginal densities 0.25 and correlation 0.6 recovered within tolerance over 400 pairs, directed and undirected.
C name
og_correlated_pair_game
In notebooks
Og.CorrelatedPairGame
igraph 1.0
igraph_correlated_pair_game
See also
correlated_game, erdos_renyi_game_gnp

simple_interconnected_islands_game#

Same quality

Draws a graph of equal random islands joined by a few random edges.

og_error_t og_simple_interconnected_islands_game(
    og_t *graph,
    og_int_t islands_n,
    og_int_t islands_size,
    og_real_t islands_pin,
    og_int_t n_inter
);

There are islands_n islands of islands_size consecutive vertices. Inside an island every pair is joined with probability islands_pin. Between every two islands, n_inter distinct pairs (one vertex from each) are chosen uniformly and joined; n_inter is capped at islands_size^2. The graph is undirected and simple. Edges are listed island by island: its own edges, then its links to each later island. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • islands_n The number of islands.
  • islands_size The number of vertices per island.
  • islands_pin The edge probability inside an island, in [0, 1].
  • n_inter Edges between every two islands.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL islands_n, islands_size or n_inter is negative
  • OG_EINVAL islands_pin is outside [0, 1] or NaN
  • OG_EOVERFLOW the vertex count exceeds the library's limits
  • OG_ENOMEM there is not enough memory
Complexity
O(N + |E|) expected, N = islands_n islands_size.
Checked
python-igraph does not expose it: full islands match igraph 1.0.1's exact edge order; pair frequencies inside and between islands checked against the model; errors as the definition says.
C name
og_simple_interconnected_islands_game
In notebooks
Og.SimpleInterconnectedIslandsGame
igraph 1.0
igraph_simple_interconnected_islands_game
See also
sbm_game, erdos_renyi_game_gnp

Growth and preferential attachment

barabasi_game#

Same quality

Grows a graph by preferential attachment (Barabási-Albert and its generalisations).

og_error_t og_barabasi_game(
    og_t *graph,
    og_int_t n,
    og_real_t power,
    og_int_t m,
    const og_vector_int_t *outseq,
    og_bool_t outpref,
    og_real_t A,
    og_bool_t directed,
    og_barabasi_algorithm_t algo,
    const og_t *start_from
);

Vertices are added one at a time, and each new vertex makes m edges (or its outseq entry) to earlier vertices, choosing vertex v with probability proportional to d(v)^power + A. d(v) is v's in-degree, or its total degree with outpref; undirected graphs always use the total degree. power = 1 is the linear model (Barabási and Albert 1999, Price 1965); other powers give non-linear attachment (Krapivsky, Redner and Leyvraz 2000). Edges point from the new vertex to the earlier one, and there are never self-loops.

algo: OG_BARABASI_PSUMTREE draws without replacement within a step, so there are no multi-edges (a vertex cites at most every earlier vertex); OG_BARABASI_PSUMTREE_MULTIPLE draws with replacement; OG_BARABASI_BAG draws from a list holding each vertex once plus once per counted edge, needs power = 1 and A = 1, and allows multi-edges.

start_from (may be NULL) is a graph to grow from: its vertices take the first ids and its edges are listed first; without it growth starts from one vertex. A start graph whose directedness differs from the result's is accepted with a warning (an undirected one needs outpref for a directed result). Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices in the result, start graph included.
  • power The exponent of the attachment; 1 for linear.
  • m Edges per new vertex when outseq is NULL or empty.
  • outseq NULL or empty to use m; otherwise the edges of each vertex: n entries without start_from (the first ignored), one per new vertex with it. No negative entries.
  • outpref true to count a vertex's own edges in its degree (always so for undirected graphs).
  • A Constant added to every attractiveness; finite and non-negative, and positive when only in-degrees count.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • algo OG_BARABASI_BAG, OG_BARABASI_PSUMTREE or OG_BARABASI_PSUMTREE_MULTIPLE.
  • start_from NULL, or a graph with 1..n vertices to grow from.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL start_from has no vertices or more than n
  • OG_EINVAL outseq has the wrong length or a negative entry, or m is negative
  • OG_EINVAL power is NaN, or A is negative, infinite or NaN
  • OG_EINVAL A is 0 while only in-degrees count (directed, outpref false)
  • OG_EINVAL algo is unknown, or OG_BARABASI_BAG is used with power != 1 or A != 1
  • OG_EINVAL an undirected start graph is given for a directed result without outpref
  • OG_EINVAL a vertex's attractiveness is negative or infinite (a negative power on degree 0)
  • OG_ENOMEM there is not enough memory
Complexity
OG_BARABASI_BAG O(n + |E|); the psumtree algorithms O((n + |E|) log n).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 30 cases x 400 samples (all three algorithms, outpref, power 0 to 2 and -0.5, A 0-2, out-degree sequences, start graphs) and whole output distributions of 7 tiny cases; a vertex citing every earlier one lists them in id order exactly; 20 error cases match.
C name
og_barabasi_game
In notebooks
Og.BarabasiGame
igraph 1.0
igraph_barabasi_game
See also
barabasi_aging_game, recent_degree_game, static_power_law_game, full_citation
og_t g;
og_rng_seed(og_rng_default(), 1);
/* 1000 vertices, 3 edges per new vertex, linear attachment, no multi-edges */
og_barabasi_game(&g, 1000, 1.0, 3, NULL, true, 1.0, OG_UNDIRECTED,
                 OG_BARABASI_PSUMTREE, NULL);
og_destroy(&g);

barabasi_aging_game#

Same quality

Grows a graph by preferential attachment with aging: attractiveness also depends on a vertex's age.

og_error_t og_barabasi_aging_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t m,
    const og_vector_int_t *outseq,
    og_bool_t outpref,
    og_real_t pa_exp,
    og_real_t aging_exp,
    og_int_t aging_bins,
    og_real_t zero_deg_appeal,
    og_real_t zero_age_appeal,
    og_real_t deg_coef,
    og_real_t age_coef,
    og_bool_t directed
);

Each new vertex makes m edges (or its outseq entry) to earlier vertices, drawn independently, so multi-edges can occur. Vertex v is chosen with probability proportional to (deg_coef d^pa_exp + zero_deg_appeal) (age_coef (b + 1)^aging_exp + zero_age_appeal), where d is v's in-degree (plus its own edges with outpref) and a vertex with d = 0 gets only zero_deg_appeal from the first factor. b is v's age bin: its age in steps divided by the bin width nodes / aging_bins + 1, so the youngest bin counts as age 1 (Dorogovtsev and Mendes 2000).

Edges point from the new vertex to the earlier one. When every weight is zero the target is uniform. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • m Edges per new vertex when outseq is NULL or empty.
  • outseq NULL or empty to use m for every vertex; otherwise one entry per vertex, the first ignored (vertex 0 makes no edges).
  • outpref true to count a vertex's own edges in d.
  • pa_exp The exponent on the degree.
  • aging_exp The exponent on the age bin (negative: older vertices attract less).
  • aging_bins The number of age bins, at least 1.
  • zero_deg_appeal Added to the degree term; the whole term for d = 0.
  • zero_age_appeal Added to the age term.
  • deg_coef Coefficient of the degree term.
  • age_coef Coefficient of the age term.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL outseq does not have one entry per vertex or has a negative entry after the first, or m is negative
  • OG_EINVAL aging_bins is below 1, or an exponent is NaN
  • OG_EINVAL an appeal or coefficient is negative or infinite
  • OG_EINVAL a vertex's weight comes out negative, infinite or NaN
  • OG_ENOMEM there is not enough memory
Complexity
O((|E| + nodes aging_bins) log nodes).
Checked
python-igraph does not expose it: the exact first-step citation probabilities (degree term, outpref, age bins) checked over 20,000 samples. Ages counting from 1 and the zero-degree rule are our reading of the model.
C name
og_barabasi_aging_game
In notebooks
Og.BarabasiAgingGame
igraph 1.0
igraph_barabasi_aging_game
See also
barabasi_game, recent_degree_aging_game, lastcit_game

recent_degree_game#

Same quality

Grows a graph by attachment to vertices that gained many edges recently.

og_error_t og_recent_degree_game(
    og_t *graph,
    og_int_t nodes,
    og_real_t power,
    og_int_t time_window,
    og_int_t m,
    const og_vector_int_t *outseq,
    og_bool_t outpref,
    og_real_t zero_appeal,
    og_bool_t directed
);

Each new vertex makes m edges (or its outseq entry) to earlier vertices, drawn independently, so multi-edges can occur. Vertex v is chosen with probability proportional to k^power + zero_appeal, where k counts the edges v received during the last time_window steps (a window of 0 or 1 counts none). With outpref a vertex's own edges count too, and never expire. Without outpref a new vertex starts at zero_appeal; once a count is recomputed, 0^0 is 1 and a negative power on k = 0 is refused as an infinite weight. When every weight is zero the target is uniform.

Edges point from the new vertex to the earlier one. The window rules were inferred from python-igraph 1.0's samples, which behave as zero_appeal = 0. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • power The exponent on the recent edge count.
  • time_window How many steps an edge counts for.
  • m Edges per new vertex when outseq is NULL or empty.
  • outseq NULL or empty to use m for every vertex; otherwise one entry per vertex, the first ignored (vertex 0 makes no edges).
  • outpref true to count a vertex's own edges (permanently).
  • zero_appeal Added to every weight; finite and non-negative.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL outseq does not have one entry per vertex or has a negative entry after the first, or m is negative
  • OG_EINVAL time_window is negative or power is NaN
  • OG_EINVAL zero_appeal is negative or infinite
  • OG_EINVAL a weight comes out infinite (a negative power on a zero count)
  • OG_ENOMEM there is not enough memory
Complexity
O((nodes + |E|) log nodes).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 8 cases x 400 samples with zero_appeal = 0 (python-igraph has no such argument) and whole output distributions of 2 tiny cases.
C name
og_recent_degree_game
In notebooks
Og.RecentDegreeGame
igraph 1.0
igraph_recent_degree_game
See also
recent_degree_aging_game, barabasi_game

recent_degree_aging_game#

Same quality

Grows a graph by recent-degree attachment combined with aging.

og_error_t og_recent_degree_aging_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t m,
    const og_vector_int_t *outseq,
    og_bool_t outpref,
    og_real_t pa_exp,
    og_real_t aging_exp,
    og_int_t aging_bins,
    og_int_t time_window,
    og_real_t zero_appeal,
    og_bool_t directed
);

As recent_degree_game() with power = pa_exp, multiplied by the age factor (b + 1)^aging_exp, where b is the vertex's age in steps divided by the bin width nodes / aging_bins + 1. Edges point from the new vertex to the earlier one; multi-edges can occur. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • m Edges per new vertex when outseq is NULL or empty.
  • outseq NULL or empty to use m for every vertex; otherwise one entry per vertex, the first ignored (vertex 0 makes no edges).
  • outpref true to count a vertex's own edges (permanently).
  • pa_exp The exponent on the recent edge count.
  • aging_exp The exponent on the age bin.
  • aging_bins The number of age bins, at least 1.
  • time_window How many steps an edge counts for.
  • zero_appeal Added to the degree term; finite and non-negative.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL outseq does not have one entry per vertex or has a negative entry after the first, or m is negative
  • OG_EINVAL aging_bins is below 1, time_window is negative, or an exponent is NaN
  • OG_EINVAL zero_appeal is negative or infinite
  • OG_EINVAL a weight comes out infinite
  • OG_ENOMEM there is not enough memory
Complexity
O((|E| + nodes aging_bins) log nodes).
Checked
python-igraph does not expose it: the exact first-step probability checked against the model; window rules as in recent_degree_game().
C name
og_recent_degree_aging_game
In notebooks
Og.RecentDegreeAgingGame
igraph 1.0
igraph_recent_degree_aging_game
See also
recent_degree_game, barabasi_aging_game

lastcit_game#

Same quality

Grows a citation graph in which a vertex's attractiveness depends on how long ago it was last cited.

og_error_t og_lastcit_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t edges_per_node,
    og_int_t agebins,
    const og_vector_t *preference,
    og_bool_t directed
);

Each new vertex cites edges_per_node earlier vertices, drawn independently, so multi-edges can occur. A vertex last cited in step s sits in lag bin (i - s - 1) / w during step i, with bin width w = nodes / agebins + 1, and stays in the last bin once older. Its weight is preference[bin]; a vertex never cited has preference[agebins], which must be positive. A citation counts at once: a vertex cited earlier in the same step is already back in bin 0. When every weight is zero the target is uniform.

Edges point from the citing vertex to the cited one. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • edges_per_node Citations made by each new vertex.
  • agebins The number of lag bins, at least 1.
  • preference agebins + 1 non-negative weights: one per lag bin, then the weight of vertices never cited (positive).
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL edges_per_node is negative or agebins is below 1
  • OG_EINVAL preference does not have agebins + 1 entries, or has a negative or infinite one
  • OG_EINVAL the last preference (never cited) is not positive
  • OG_ENOMEM there is not enough memory
Complexity
O((nodes agebins + |E|) log nodes).
Checked
python-igraph does not expose it: three rules the definition leaves open (when a vertex changes bin, a citation counting within its step, the all-zero fallback) were pinned on runs of igraph 1.0.1's C library and are reproduced; the exact first-step law checked over 20,000 samples.
C name
og_lastcit_game
In notebooks
Og.LastcitGame
igraph 1.0
igraph_lastcit_game
See also
barabasi_aging_game, cited_type_game

growing_random_game#

Same quality

Grows a graph by adding one vertex and m uniformly random edges per step.

og_error_t og_growing_random_game(
    og_t *graph,
    og_int_t n,
    og_int_t m,
    og_bool_t directed,
    og_bool_t citation
);

Vertex 0 comes first; each later step adds vertex i and m edges. With citation every edge goes from i to a uniformly chosen earlier vertex. Without it each edge joins a vertex drawn uniformly from 0..i to one drawn from 1..i, the ranges python-igraph 1.0's samples show. Self-loops and multi-edges can occur. Edges are listed in drawing order. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices.
  • m Edges added per step.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • citation true: edges go from the new vertex to earlier ones.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL n or m is negative
  • OG_ENOMEM there is not enough memory
Complexity
O(n + n m).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 6 cases x 400 samples and whole output distributions of 3 tiny cases. m = 0, refused by python-igraph's wrapper, gives an edgeless graph.
C name
og_growing_random_game
In notebooks
Og.GrowingRandomGame
igraph 1.0
igraph_growing_random_game
See also
barabasi_game, erdos_renyi_game_gnm

callaway_traits_game#

Same quality

Grows a graph in which random vertex pairs connect with a probability set by their types.

og_error_t og_callaway_traits_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t types,
    og_int_t edges_per_step,
    const og_vector_t *type_dist,
    const og_matrix_t *pref_matrix,
    og_bool_t directed,
    og_vector_int_t *node_type_vec
);

Vertices arrive one at a time with a type drawn from type_dist (NULL: uniform). After every arrival from the second vertex on, edges_per_step trials each pick two vertices uniformly among those present (possibly the same one) and join them with probability pref_matrix[type(u)][type(v)] (Callaway, Hopcroft, Kleinberg, Newman and Strogatz 2001). Self-loops and multi-edges can occur. node_type_vec (may be NULL) receives the types. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • types The number of types, at least 1.
  • edges_per_step Trials after each arrival.
  • type_dist NULL, or one non-negative weight per type.
  • pref_matrix types x types connection probabilities.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • node_type_vec Output, may be NULL: the type of each vertex.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL edges_per_step is negative
  • OG_EINVAL types is below 1
  • OG_EINVAL type_dist does not have one entry per type, or has a negative, infinite or NaN entry, or no positive one
  • OG_EINVAL pref_matrix is not types x types, or an entry is not a probability
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes edges_per_step + nodes log types).
Checked
python-igraph does not expose it: edge and loop counts and type shares checked against the model; (nodes - 1) edges_per_step trials with loops and multi-edges, as igraph 1.0.1's C library makes them.
C name
og_callaway_traits_game
In notebooks
Og.CallawayTraitsGame
igraph 1.0
igraph_callaway_traits_game
See also
establishment_game, preference_game

establishment_game#

Same quality

Grows a graph in which each new vertex tries k earlier vertices and links by type preference.

og_error_t og_establishment_game(
    og_t *graph,
    og_int_t nodes,
    og_int_t types,
    og_int_t k,
    const og_vector_t *type_dist,
    const og_matrix_t *pref_matrix,
    og_bool_t directed,
    og_vector_int_t *node_type_vec
);

Vertices arrive one at a time with a type drawn from type_dist (NULL: uniform). Once at least k vertices exist, each new vertex picks k distinct earlier vertices uniformly and links to each with probability pref_matrix[type(new)][type(old)]; before that it makes no links. An undirected graph needs a symmetric matrix. Edges go from the new vertex to the earlier one; there are no loops or multi-edges. node_type_vec (may be NULL) receives the types. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • types The number of types, at least 1.
  • k Earlier vertices tried by each new vertex.
  • type_dist NULL, or one non-negative weight per type.
  • pref_matrix types x types connection probabilities.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • node_type_vec Output, may be NULL: the type of each vertex.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL k is negative
  • OG_EINVAL types is below 1
  • OG_EINVAL type_dist does not have one entry per type, or has a negative, infinite or NaN entry, or no positive one
  • OG_EINVAL pref_matrix is not types x types, or an entry is not a probability
  • OG_EINVAL the graph is undirected and pref_matrix is not symmetric
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes k + nodes log types) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 5 cases x 400 samples (k larger than the vertices present, a single type) and whole output distributions of 2 tiny cases; 7 error cases match.
C name
og_establishment_game
In notebooks
Og.EstablishmentGame
igraph 1.0
igraph_establishment_game
See also
callaway_traits_game, preference_game

cited_type_game#

Same quality

Grows a citation graph in which the chance of being cited depends on the cited vertex's type.

og_error_t og_cited_type_game(
    og_t *graph,
    og_int_t nodes,
    const og_vector_int_t *types,
    const og_vector_t *pref,
    og_int_t edges_per_step,
    og_bool_t directed
);

Vertex i, of the given type types[i], cites edges_per_step earlier vertices, drawn independently (multi-edges can occur), vertex j with probability proportional to pref[types[j]]. A type is drawn first by its total weight, then a uniform vertex of that type. When no earlier vertex has positive weight, the new vertex cites itself (a self-loop), as igraph 1.0.1 does. Edges point from the citing vertex to the cited one. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • types The type of each vertex (non-negative integers), one per vertex.
  • pref The weight of each type, finite and non-negative.
  • edges_per_step Citations made by each new vertex.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL edges_per_step is negative
  • OG_EINVAL types does not have one entry per vertex, or has a negative entry
  • OG_EINVAL pref has no entry for some type, or a negative, infinite or NaN one
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes + |E| log T), T the number of types.
Checked
python-igraph does not expose it: the exact first-step law checked; the self-citation when nothing is citable matches igraph 1.0.1's C library.
C name
og_cited_type_game
In notebooks
Og.CitedTypeGame
igraph 1.0
igraph_cited_type_game
See also
citing_cited_type_game, lastcit_game

citing_cited_type_game#

Same quality

Grows a citation graph in which the chance of a citation depends on both vertices' types.

og_error_t og_citing_cited_type_game(
    og_t *graph,
    og_int_t nodes,
    const og_vector_int_t *types,
    const og_matrix_t *pref,
    og_int_t edges_per_step,
    og_bool_t directed
);

As cited_type_game(), with weight pref[types[i]][types[j]] for vertex i citing j. pref must be square with a row and a column for every type. When no earlier vertex has positive weight the target is uniform among the earlier vertices. Multi-edges can occur. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • types The type of each vertex (non-negative integers), one per vertex.
  • pref Square matrix: row = citing type, column = cited type; finite and non-negative.
  • edges_per_step Citations made by each new vertex.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL edges_per_step is negative
  • OG_EINVAL types does not have one entry per vertex, or has a negative entry
  • OG_EINVAL pref is not square, lacks a row for some type, or has a negative, infinite or NaN entry
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes T log T + |E| log T), T the number of types.
Checked
python-igraph does not expose it: the exact first-step law checked; the all-zero fallback agrees with a black-box sample of igraph 1.0.1.
C name
og_citing_cited_type_game
In notebooks
Og.CitingCitedTypeGame
igraph 1.0
igraph_citing_cited_type_game
See also
cited_type_game, preference_game

forest_fire_game#

Same quality

Grows a graph by the forest fire model.

og_error_t og_forest_fire_game(
    og_t *graph,
    og_int_t nodes,
    og_real_t fw_prob,
    og_real_t bw_factor,
    og_int_t pambs,
    og_bool_t directed
);

Each new vertex picks pambs ambassadors uniformly among the earlier vertices (a vertex picked twice counts once) and cites them. A fire then spreads breadth first from them: each burning vertex burns up to x not yet burnt vertices it cites and up to y not yet burnt vertices citing it, with x and y geometric with means fw_prob / (1 - fw_prob) and r / (1 - r), r = bw_factor fw_prob. The new vertex cites every burnt vertex (Leskovec, Kleinberg and Faloutsos 2007, the corrected model). No self-loops or multi-edges arise.

Edges are listed in burning order: the ambassadors, then the fire, forward links before backward ones at each vertex. Which neighbours burn, and how the citation lists are reordered for later fires, follow python-igraph 1.0's observed behaviour. directed false gives the same edges undirected. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • fw_prob Forward burning probability, in [0, 1).
  • bw_factor Backward burning ratio; bw_factor fw_prob must be in [0, 1).
  • pambs Ambassadors per new vertex.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL fw_prob is outside [0, 1)
  • OG_EINVAL bw_factor fw_prob is outside [0, 1)
  • OG_EINVAL pambs is negative
  • OG_ENOMEM there is not enough memory
Complexity
O(nodes + the total length of the citation lists of all burning vertices).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 8 cases x 400 samples (directed and undirected, 0-3 ambassadors, bw_factor 0-2) and whole output distributions of 14 tiny cases, edge order included; 7 error cases match.
C name
og_forest_fire_game
In notebooks
Og.ForestFireGame
igraph 1.0
igraph_forest_fire_game
See also
barabasi_game, growing_random_game

Degree sequences and fitness

degree_sequence_game#

Same quality

Draws a random graph with exactly the given degree sequence.

og_error_t og_degree_sequence_game(
    og_t *graph,
    const og_vector_int_t *out_degrees,
    const og_vector_int_t *in_degrees,
    og_degseq_t method
);

With in_degrees NULL the graph is undirected with degrees out_degrees; otherwise it is directed with these out- and in-degrees, whose sums must agree. method: OG_DEGSEQ_CONFIGURATION matches stubs uniformly at random (configuration model; loops and multi-edges can occur); OG_DEGSEQ_CONFIGURATION_SIMPLE repeats that until the result is simple, which makes every simple graph equally likely but can take very long for large degrees; OG_DEGSEQ_FAST_HEUR_SIMPLE matches stubs in rounds, keeping the admissible pairs and restarting only when stuck, which is fast and simple but not exactly uniform; OG_DEGSEQ_EDGE_SWITCHING_SIMPLE starts from a deterministic simple realization (Havel-Hakimi or Kleitman-Wang, vertices in id order) and makes 10 degree-preserving switch trials per edge; OG_DEGSEQ_VL (Viger and Latapy 2015) gives connected simple undirected graphs, approximately uniformly, by switches that keep the graph connected.

The simple methods need a sequence some simple graph has. OG_DEGSEQ_VL also needs every degree positive and enough edges to connect the vertices, and takes undirected sequences only (a zero-length in_degrees counts as none). Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • out_degrees The degrees (undirected) or out-degrees (directed).
  • in_degrees NULL for an undirected graph, else the in-degrees (same length).
  • method OG_DEGSEQ_CONFIGURATION, OG_DEGSEQ_CONFIGURATION_SIMPLE, OG_DEGSEQ_FAST_HEUR_SIMPLE, OG_DEGSEQ_EDGE_SWITCHING_SIMPLE or OG_DEGSEQ_VL.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL method is not a known value, or OG_DEGSEQ_VL is asked for a directed graph
  • OG_EINVAL the sequences differ in length, or a degree is negative
  • OG_EINVAL the out- and in-degree sums differ, or an undirected sum is odd
  • OG_EINVAL a simple method is given degrees no simple graph has
  • OG_EINVAL OG_DEGSEQ_VL: a degree is zero, or there are too few edges for a connected graph
  • OG_ENOMEM there is not enough memory
Complexity
Configuration O(n + m); fast heuristic O(n + m) per round; edge switching O(n + m) expected after the start realization; configuration_simple O(n + m) per attempt, with a number of attempts that grows fast with the degrees; VL has no fixed bound (20,000-vertex sequences take a fraction of a second, a single long cycle far more).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. All five methods: 23 cases x 400 samples and whole output distributions of tiny inputs (edge lists included for all but VL); degrees kept exactly on 60 random sequences; VL graphs connected; 16 error cases match. Known divergences, VL only: its edge listing is not reproduced, and on sequences whose connected realizations are all paths of 4 or 5 vertices python-igraph returns only half of them while Open Graph returns all of them uniformly.
C name
og_degree_sequence_game
In notebooks
Og.DegreeSequenceGame
igraph 1.0
igraph_degree_sequence_game
See also
k_regular_game, realize_degree_sequence, rewire, is_graphical, chung_lu_game
og_t g;
og_vector_int_t deg;
og_vector_int_init_int(&deg, 6, 3, 3, 2, 2, 1, 1);
og_degree_sequence_game(&g, &deg, NULL, OG_DEGSEQ_VL);  /* connected and simple */
og_vector_int_destroy(&deg);
og_destroy(&g);

k_regular_game#

Same quality

Draws a random k-regular graph.

og_error_t og_k_regular_game(
    og_t *graph,
    og_int_t no_of_nodes,
    og_int_t k,
    og_bool_t directed,
    og_bool_t multiple
);

Every vertex gets degree k (in a directed graph out- and in-degree k). With multiple the configuration model is used, so self-loops and multi-edges can occur; otherwise the graph is simple, drawn by degree_sequence_game()'s OG_DEGSEQ_FAST_HEUR_SIMPLE. An undirected k-regular graph on an odd number of vertices needs an even k. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • no_of_nodes The number of vertices.
  • k The degree of every vertex.
  • directed OG_DIRECTED or OG_UNDIRECTED.
  • multiple true to allow self-loops and multi-edges.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_EINVAL k is negative
  • OG_EINVAL undirected, with an odd number of vertices and an odd k
  • OG_EINVAL no simple k-regular graph exists (k too large) when multiple is false
  • OG_ENOMEM there is not enough memory
Complexity
O(n k) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 8 cases x 400 samples and whole output distributions of 5 tiny cases (undirected k = 2, directed k = 1, multigraph k = 1); 8 error cases match.
C name
og_k_regular_game
In notebooks
Og.KRegularGame
igraph 1.0
igraph_k_regular_game
See also
degree_sequence_game, realize_degree_sequence
og_t g;
og_k_regular_game(&g, 100, 3, OG_UNDIRECTED, false);  /* simple, 150 edges */
og_destroy(&g);

chung_lu_game#

Same quality

Draws a random graph with given expected degrees (the Chung-Lu model and two variants).

og_error_t og_chung_lu_game(
    og_t *graph,
    const og_vector_t *out_weights,
    const og_vector_t *in_weights,
    og_bool_t loops,
    og_chung_lu_t variant
);

Each pair (i, j) is joined independently with a probability built from q = w_i w_j / S, S the sum of the weights: OG_CHUNG_LU_ORIGINAL uses min(q, 1) (Chung and Lu 2002), OG_CHUNG_LU_MAXENT q / (1 + q) (maximum entropy, Park and Newman 2004), OG_CHUNG_LU_NR 1 - exp(-q) (Norros and Reittu 2006). With in_weights the graph is directed, q = out_i in_j / S, and both weight vectors must have the same sum. Self-pairs count only with loops; there are no multi-edges.

In the original variant the expected degrees are the weights when no q exceeds 1 (exactly so for directed graphs with loops); a warning is given when some q exceeds 1. Pairs are visited in order of decreasing weight with geometric skipping (Miller and Hagberg 2011). Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • out_weights The weights (undirected) or out-weights (directed); finite and non-negative.
  • in_weights NULL for an undirected graph, else the in-weights (same length and sum).
  • loops true to allow self-loops.
  • variant OG_CHUNG_LU_ORIGINAL, OG_CHUNG_LU_MAXENT or OG_CHUNG_LU_NR.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL variant is not a known value
  • OG_EINVAL the weight vectors differ in length, or their sums differ
  • OG_EINVAL a weight is negative, infinite or NaN
  • OG_ENOMEM there is not enough memory
Complexity
O(n log n + |E|) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 11 cases x 400 samples (all variants, loops, directed, q > 1) and whole output distributions of 4 tiny cases, edge order included. python-igraph truncates weights to integers, so real weights were checked against the exact expected degrees instead.
C name
og_chung_lu_game
In notebooks
Og.ChungLuGame
igraph 1.0
igraph_chung_lu_game
See also
static_fitness_game, degree_sequence_game, erdos_renyi_game_gnp

static_fitness_game#

Same quality

Draws a graph with a fixed number of edges whose endpoints are chosen in proportion to vertex fitness.

og_error_t og_static_fitness_game(
    og_t *graph,
    og_int_t no_of_edges,
    const og_vector_t *fitness_out,
    const og_vector_t *fitness_in,
    og_edge_type_sw_t allowed_edge_types
);

Each edge draws its endpoints independently with probabilities proportional to fitness_out (the second endpoint from fitness_in in a directed graph; fitness_in NULL makes the graph undirected) (Goh, Kahng and Kim 2001). A draw that would make a forbidden self-loop or, without OG_MULTI_SW, a repeated pair is drawn again, until no_of_edges edges exist. The vertex count is the length of fitness_out.

Without multi-edges the edges are listed by first endpoint, then second, a vertex's self-loop after its other edges; with multi-edges in drawing order. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • no_of_edges The number of edges.
  • fitness_out One non-negative fitness per vertex (out-fitness when directed).
  • fitness_in NULL for an undirected graph, else the in-fitness (same length).
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EINVAL no_of_edges is negative
  • OG_EINVAL fitness_in and fitness_out differ in length
  • OG_EINVAL a fitness is negative, infinite or NaN
  • OG_EINVAL edges are asked for but no admissible pair has positive fitness
  • OG_EINVAL without multi-edges, no_of_edges exceeds the admissible pairs
  • OG_ENOMEM there is not enough memory
Complexity
O(n + m log n) expected while m is well below the number of admissible pairs (draws are rejected and repeated).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 9 cases x 400 samples (all edge-type settings, directed, the complete graph) and whole output distributions of 3 tiny cases; 12 error cases match.
C name
og_static_fitness_game
In notebooks
Og.StaticFitnessGame
igraph 1.0
igraph_static_fitness_game
See also
static_power_law_game, chung_lu_game, barabasi_game

static_power_law_game#

Same quality

Draws a graph with a power-law degree distribution through the static fitness model.

og_error_t og_static_power_law_game(
    og_t *graph,
    og_int_t no_of_nodes,
    og_int_t no_of_edges,
    og_real_t exponent_out,
    og_real_t exponent_in,
    og_edge_type_sw_t allowed_edge_types,
    og_bool_t finite_size_correction
);

Vertex j gets fitness (n - j + i0 - 1)^(-a), a = 1 / (exponent - 1), so the last vertex is the fittest, and static_fitness_game() then places no_of_edges edges; the degree distribution follows a power law with the given exponent (Goh, Kahng and Kim 2001). exponent_in < 0 makes the graph undirected; otherwise it is directed and the in-fitness values are shuffled over the vertices. An infinite exponent gives every vertex the same fitness.

i0 = 1 unless finite_size_correction is set and a > 1/2 (exponent below 3); then i0 = n^(1 - 1/(2a)) (10 sqrt(2) (1 - a))^(1/a), at least 1 (Cho, Kim, Park, Kahng and Kim 2009). Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • no_of_nodes The number of vertices.
  • no_of_edges The number of edges.
  • exponent_out The out-degree (or degree) exponent, at least 2; may be infinite.
  • exponent_in Negative for an undirected graph, else the in-degree exponent, at least 2.
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
  • finite_size_correction true to apply the finite-size offset i0.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL no_of_nodes or no_of_edges is negative
  • OG_EINVAL exponent_out is below 2 or NaN
  • OG_EINVAL exponent_in is in [0, 2) or NaN
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EINVAL no_of_edges is too large for a graph without multi-edges
  • OG_ENOMEM there is not enough memory
Complexity
O(n + m log n) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 8 cases x 400 samples (correction on and off, infinite exponents, directed) and whole output distributions of 2 tiny cases. Divergence: a NaN exponent is EINVAL here; python-igraph builds a graph.
C name
og_static_power_law_game
In notebooks
Og.StaticPowerLawGame
igraph 1.0
igraph_static_power_law_game
See also
static_fitness_game, barabasi_game, chung_lu_game

Rewiring

rewire#

Same quality

Randomly rewires a graph in place while keeping every vertex's degree.

og_error_t og_rewire(
    og_t *graph,
    og_int_t n,
    og_edge_type_sw_t allowed_edge_types,
    og_rewiring_stats_t *stats
);

Makes n trials. Each picks two different edges (a, b) and (c, d) uniformly (in an undirected graph the second in a random orientation) and replaces them with (a, d) and (c, b), unless that would create a multi-edge or, without OG_LOOPS_SW, a self-loop (Maslov and Sneppen 2002). Degrees, and in directed graphs out- and in-degrees, never change. Without OG_LOOPS_SW self-loops already present stay where they are.

The graph and vertex attributes are kept; the edges are new, so edge ids and edge attributes are not. stats (may be NULL) receives the number of switches carried out. Where switched edges are listed follows python-igraph 1.0: appended below 10 trials, in place from 10 on. Modes with multi-edges are not available. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph The graph to rewire, changed in place.
  • n The number of switch trials.
  • allowed_edge_types OG_SIMPLE_SW or OG_LOOPS_SW.
  • stats Output, may be NULL: successful_swaps, the switches carried out.
Returns
OG_SUCCESS, or an error code. On error the graph is left as it was.
Errors
  • OG_EINVMODE allowed_edge_types has an unknown bit
  • OG_UNIMPLEMENTED allowed_edge_types includes OG_MULTI_SW
  • OG_ENOMEM there is not enough memory
Complexity
O(|V| + |E| + n) expected.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 15 cases x 400 samples on fixed graphs at 1 to 300 trials (so the trial semantics are compared, not only the end state), whole output distributions of tiny inputs with the edge order, and graphs that already have self-loops.
C name
og_rewire
In notebooks
Og.Rewire
igraph 1.0
igraph_rewire
See also
rewire_edges, degree_sequence_game, watts_strogatz_game
og_t g;
og_rewiring_stats_t stats;
og_famous(&g, "Zachary");
og_rewire(&g, 1000, OG_SIMPLE_SW, &stats);  /* degrees unchanged */
printf("%" OG_PRId " switches made\n", stats.successful_swaps);
og_destroy(&g);

watts_strogatz_game#

Same quality

Draws a small-world graph: a periodic lattice whose edges are rewired at random (Watts-Strogatz).

og_error_t og_watts_strogatz_game(
    og_t *graph,
    og_int_t dim,
    og_int_t size,
    og_int_t nei,
    og_real_t p,
    og_edge_type_sw_t allowed_edge_types
);

Builds a periodic square lattice of dim dimensions with size vertices along each (square_lattice()), joins every vertex to all vertices within nei steps (connect_neighborhood(); nei 0 and 1 give the plain lattice), then moves each edge endpoint with probability p to a uniformly chosen vertex, as rewire_edges() does (Watts and Strogatz 1998). allowed_edge_types says whether the rewiring may create self-loops or multi-edges. The graph is undirected; p = 0 gives the lattice itself, edge for edge as python-igraph lists it. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • dim The number of lattice dimensions, at least 1.
  • size The number of vertices along each dimension, at least 1.
  • nei Join vertices up to this many steps apart.
  • p The probability that an endpoint is moved, in [0, 1].
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL dim or size is below 1, or nei is negative
  • OG_EINVAL p is outside [0, 1]
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EOVERFLOW the lattice has too many vertices
  • OG_ENOMEM there is not enough memory
Complexity
O(|V| + |E|) expected, plus the neighbourhood search when nei >= 2.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 12 rewired cases x 400 samples (the degrees of the first and last vertex included) and whole output distributions of 2 tiny cases; p = 0 lattices match edge by edge (11 shapes, dim 1-3, nei 0-4).
C name
og_watts_strogatz_game
In notebooks
Og.WattsStrogatzGame
igraph 1.0
igraph_watts_strogatz_game
See also
square_lattice, rewire_edges, connect_neighborhood, rewire
og_t g;
/* a ring of 1000 vertices, each joined to 2 neighbours on each side,
   then 5% of the endpoints moved */
og_watts_strogatz_game(&g, 1, 1000, 2, 0.05, OG_SIMPLE_SW);
og_destroy(&g);

rewire_edges#

Same quality

Moves edge endpoints to uniformly random vertices with a given probability, in place.

og_error_t og_rewire_edges(
    og_t *graph,
    og_real_t prob,
    og_edge_type_sw_t allowed_edge_types
);

Each endpoint is moved with probability prob to a vertex chosen uniformly among those that keep the graph within allowed_edge_types; staying put is one of the choices. Degrees are not kept. Without multi-edges a pair counts as taken in either direction, so a directed graph gets no new mutual pairs, and the endpoints are visited in two sweeps, second endpoints and then first endpoints, in the order that reproduces python-igraph 1.0; with multi-edges each edge moves its first endpoint, then its second.

Without loops a self-loop already present must move an endpoint (one with nowhere to go stays). Graph and vertex attributes are kept; edge attributes are not. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph The graph to rewire, changed in place.
  • prob The probability that an endpoint is moved, in [0, 1].
  • allowed_edge_types Which non-simple edges may appear: OG_SIMPLE_SW, or OG_LOOPS_SW and/or OG_MULTI_SW combined with |.
Returns
OG_SUCCESS, or an error code. On error the graph is left as it was.
Errors
  • OG_EINVAL allowed_edge_types has bits other than OG_LOOPS_SW and OG_MULTI_SW
  • OG_EINVAL prob is outside [0, 1] or NaN
  • OG_ENOMEM there is not enough memory
Complexity
O(|V| + |E|) expected on sparse graphs.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. The whole output, every edge in edge-id order, agrees on 28 small cases (simple, loops, multi-edges; 20,000 samples each), plus 14 summary-statistics cases. Known divergence: multigraph input in a mode without multi-edges, when the parallel copies are not neighbours in edge order (python-igraph keeps slightly more parallel edges).
C name
og_rewire_edges
In notebooks
Og.RewireEdges
igraph 1.0
igraph_rewire_edges
See also
rewire_directed_edges, rewire, watts_strogatz_game

rewire_directed_edges#

Same quality

Moves one chosen endpoint of each directed edge to a random vertex with a given probability, in place.

og_error_t og_rewire_directed_edges(
    og_t *graph,
    og_real_t prob,
    og_bool_t loops,
    og_neimode_t mode
);

With OG_OUT every edge keeps its source and, with probability prob, gets a uniformly random new target, so out-degrees are kept; with OG_IN the target stays and the source moves, keeping in-degrees. The new endpoint differs from the fixed one unless loops is set; multi-edges can form. For an undirected graph, or with OG_ALL, this is rewire_edges() with multi-edges allowed (and loops if set). Graph and vertex attributes are kept. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph The graph to rewire, changed in place.
  • prob The probability that an edge is rewired, in [0, 1].
  • loops true to allow self-loops.
  • mode OG_OUT (move targets), OG_IN (move sources) or OG_ALL.
Returns
OG_SUCCESS, or an error code. On error the graph is left as it was.
Errors
  • OG_EINVAL prob is outside [0, 1] or NaN
  • OG_EINVMODE mode is not OG_OUT, OG_IN or OG_ALL
  • OG_ENOMEM there is not enough memory
Complexity
O(|V| + |E|).
Checked
python-igraph does not expose it: moved-endpoint and loop frequencies checked against the exact law; OUT keeps the out-degrees, IN the in-degrees.
C name
og_rewire_directed_edges
In notebooks
Og.RewireDirectedEdges
igraph 1.0
igraph_rewire_directed_edges
See also
rewire_edges, rewire

Geometric and other models

grg_game#

Same quality

Draws a random geometric graph: points in the unit square joined when closer than a radius.

og_error_t og_grg_game(
    og_t *graph,
    og_int_t nodes,
    og_real_t radius,
    og_bool_t torus,
    og_vector_t *x,
    og_vector_t *y
);

nodes points are placed uniformly in the unit square, and two points are joined when their Euclidean distance is below radius; with torus the square wraps around in both directions. Vertices are numbered by increasing x coordinate, and x and y (each may be NULL) receive the coordinates. The graph is undirected and simple; a radius of 0 or less gives no edges (Penrose 2003).

Below a radius of 1/3 the search runs over horizontal strips taller than the radius. Edges are listed per vertex as python-igraph 1.0 lists them: partners to the right by id, then, on the torus, partners across the x = 1 seam. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • nodes The number of vertices.
  • radius Points closer than this are joined.
  • torus true to measure distances on the torus.
  • x Output, may be NULL: the x coordinates, increasing.
  • y Output, may be NULL: the y coordinates.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL the vertex count is negative
  • OG_ENOMEM there is not enough memory
Complexity
O(n + |E|) expected for radius < 1/3, O(n^2 radius) otherwise.
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 11 cases x 400 samples with coordinate statistics, torus and radius >= 1. The listing rule applied to python-igraph's own coordinates reproduces its edge lists in all 120 fixture cases.
C name
og_grg_game
In notebooks
Og.GrgGame
igraph 1.0
igraph_grg_game
See also
dot_product_game, erdos_renyi_game_gnp

dot_product_game#

Same quality

Draws a graph in which each pair connects with the dot product of the two vertices' latent vectors as its probability.

og_error_t og_dot_product_game(
    og_t *graph,
    const og_matrix_t *vecs,
    og_bool_t directed
);

Each column of vecs is the latent vector of one vertex. A pair is joined with probability equal to the dot product of its two vectors, independently: products above 1 always connect and negative ones never (each case warns once) (Nickel 2006). A directed graph considers every ordered pair u != v, an undirected one every pair u < v; there are no self-loops. Edges are listed by u, then v. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • vecs d x n matrix: column v is the latent vector of vertex v.
  • directed OG_DIRECTED or OG_UNDIRECTED.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL vecs contains NaN
  • OG_ENOMEM there is not enough memory
Complexity
O(n^2 d).
Checked
python-igraph does not expose it: all-ones vectors give igraph 1.0.1's exact edge order, directed and undirected; pair probabilities checked against the model.
C name
og_dot_product_game
In notebooks
Og.DotProductGame
igraph 1.0
igraph_dot_product_game
See also
grg_game, sbm_game

tree_game#

Same quality

Draws a uniformly random labelled tree on n vertices.

og_error_t og_tree_game(
    og_t *graph,
    og_int_t n,
    og_bool_t directed,
    og_random_tree_t method
);

Every one of the n^(n-2) labelled trees is equally likely. OG_RANDOM_TREE_PRUFER decodes a uniformly random Prüfer sequence (from_prufer()) and makes undirected trees only. OG_RANDOM_TREE_LERW (alias OG_RANDOM_LERW) follows a random walk on the complete graph and keeps the edge of every first visit (Aldous 1990, Broder 1989; the same law as Wilson's loop-erased walks); a directed tree points away from the walk's random start. Only the first visits are drawn, from their exact law, so it runs in O(n). Edges are listed in discovery order. n < 2 gives n isolated vertices. Draws from rng_default(); seed it with rng_seed() for a repeatable result.

Parameters
  • graph Output: an uninitialised og_t. On success it holds the new graph; the caller frees it with destroy().
  • n The number of vertices.
  • directed OG_DIRECTED (LERW only) or OG_UNDIRECTED.
  • method OG_RANDOM_TREE_PRUFER or OG_RANDOM_TREE_LERW.
Returns
OG_SUCCESS, or an error code. On error the graph is not initialised and nothing is leaked.
Errors
  • OG_EINVAL n is negative or method is not a known value
  • OG_EINVAL OG_RANDOM_TREE_PRUFER is asked for a directed tree with n >= 2
  • OG_ENOMEM there is not enough memory
Complexity
O(n).
Checked
Same distribution as python-igraph 1.0, not the same graph for a given seed. 9 cases x 400 samples and whole output distributions for Prüfer and LERW, undirected and directed, listing order included. 100,000 vertices: 9 ms, python-igraph 14.5 ms.
C name
og_tree_game
In notebooks
Og.TreeGame
igraph 1.0
igraph_tree_game
See also
from_prufer, random_spanning_tree, kary_tree

Last updated · Open Graph 0.1.0 · OpenBI Studio 0.3.78