For using the igraph C library
Graph generators create graphs.
Almost all functions which create graph objects are documented
here. The exceptions are igraph_induced_subgraph()
and alike, these
create graphs based on another graph.
igraph_create
— Creates a graph with the specified edges.igraph_small
— Shorthand to create a small graph, giving the edges as arguments.igraph_adjacency
— Creates a graph from an adjacency matrix.igraph_weighted_adjacency
— Creates a graph from a weighted adjacency matrix.igraph_sparse_adjacency
— Creates a graph from a sparse adjacency matrix.igraph_sparse_weighted_adjacency
— Creates a graph from a weighted sparse adjacency matrix.igraph_adjlist
— Creates a graph from an adjacency list.igraph_star
— Creates a star graph, every vertex connects only to the center.igraph_wheel
— Creates a wheel graph, a union of a star and a cycle graph.igraph_hypercube
— The ndimensional hypercube graph.igraph_square_lattice
— Arbitrary dimensional square lattices.igraph_triangular_lattice
— A triangular lattice with the given shape.igraph_hexagonal_lattice
— A hexagonal lattice with the given shape.igraph_ring
— Creates a cycle graph or a path graph.igraph_kary_tree
— Creates a kary tree in which almost all vertices have k children.igraph_symmetric_tree
— Creates a symmetric tree with the specified number of branches at each level.igraph_regular_tree
— Creates a regular tree.igraph_tree_from_parent_vector
— Constructs a tree or forest from a vector encoding the parent of each vertex.igraph_full
— Creates a full graph (complete graph).igraph_full_citation
— Creates a full citation graph (a complete directed acyclic graph).igraph_full_multipartite
— Creates a full multipartite graph.igraph_turan
— Creates a Turán graph.igraph_realize_degree_sequence
— Generates a graph with the given degree sequence.igraph_realize_bipartite_degree_sequence
— Generates a bipartite graph with the given bidegree sequence.igraph_famous
— Create a famous graph by simply providing its name.igraph_lcf
— Creates a graph from LCF notation.igraph_lcf_vector
— Creates a graph from LCF notation.igraph_from_prufer
— Generates a tree from a Prüfer sequence.igraph_atlas
— Create a small graph from the “Graph Atlas”.igraph_de_bruijn
— Generate a de Bruijn graph.igraph_kautz
— Generate a Kautz graph.igraph_circulant
— Creates a circulant graph.igraph_generalized_petersen
— Creates a Generalized Petersen graph.igraph_extended_chordal_ring
— Create an extended chordal ring.
igraph_error_t igraph_create(igraph_t *graph, const igraph_vector_int_t *edges, igraph_integer_t n, igraph_bool_t directed);
Arguments:

An uninitialized graph object. 

The edges to add, the first two elements are the first edge, etc. 

The number of vertices in the graph, if smaller or equal
to the highest vertex ID in the 

Boolean, whether to create a directed graph or
not. If yes, then the first edge points from the first
vertex ID in 
Returns:
Error code:

Time complexity: O(V+E), V is the number of vertices, E the number of edges in the graph.
Example 9.1. File examples/simple/igraph_create.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_t v1, v2; /* simple use */ igraph_vector_int_init(&v1, 8); VECTOR(v1)[0] = 0; VECTOR(v1)[1] = 1; VECTOR(v1)[2] = 1; VECTOR(v1)[3] = 2; VECTOR(v1)[4] = 2; VECTOR(v1)[5] = 3; VECTOR(v1)[6] = 2; VECTOR(v1)[7] = 2; igraph_create(&g, &v1, 0, 0); if (igraph_vcount(&g) != 4) { return 1; } igraph_vector_int_init(&v2, 0); igraph_get_edgelist(&g, &v2, 0); igraph_vector_int_sort(&v1); igraph_vector_int_sort(&v2); if (!igraph_vector_int_all_e(&v1, &v2)) { return 2; } igraph_destroy(&g); /* higher number of vertices */ igraph_create(&g, &v1, 10, 0); if (igraph_vcount(&g) != 10) { return 1; } igraph_get_edgelist(&g, &v2, 0); igraph_vector_int_sort(&v1); igraph_vector_int_sort(&v2); if (!igraph_vector_int_all_e(&v1, &v2)) { return 3; } igraph_destroy(&g); igraph_vector_int_destroy(&v1); igraph_vector_int_destroy(&v2); return 0; }
igraph_error_t igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, int first, ...);
This function is handy when a relatively small graph needs to be created.
Instead of giving the edges as a vector, they are given simply as
arguments and a 1
needs to be given after the last meaningful
edge argument.
This function is intended to be used with vertex IDs that are entered as literal integers. If you use a variable instead of a literal, make sure that it is of type int, as this is the type that this function assumes for all variadic arguments. Using a different integer type is undefined behaviour and likely to cause platformspecific issues.
Arguments:

Pointer to an uninitialized graph object. The result will be stored here. 


The number of vertices in the graph; a nonnegative integer. 


Logical constant; gives whether the graph should be directed. Supported values are:



The additional arguments giving the edges of the graph,
and must be of type int. Don't forget to supply an
additional 
Returns:
Error code. 
Time complexity: O(V+E), the number of vertices plus the number of edges in the graph to create.
Example 9.2. File examples/simple/igraph_small.c
#include <igraph.h> int main(void) { igraph_t g; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, 6, 1, 1); igraph_write_graph_edgelist(&g, stdout); igraph_destroy(&g); return 0; }
igraph_error_t igraph_adjacency( igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode, igraph_loops_t loops );
The order of the vertices in the matrix is preserved, i.e. the vertex corresponding to the first row/column will be vertex with id 0, the next row is for vertex 1, etc. No guarantees are given about the ordering of edges.
Arguments:

Pointer to an uninitialized graph object. 


The adjacency matrix. How it is interpreted
depends on the 


Constant to specify how the given matrix is interpreted
as an adjacency matrix. Possible values (A(i,j) is the element in
row i and column j in the adjacency matrix



Constant to specify how the diagonal of the matrix should be treated when creating loop edges.

Returns:
Error code,

Time complexity: O(VV), V is the number of vertices in the graph.
Example 9.3. File examples/simple/igraph_adjacency.c
#include <igraph.h> int main(void) { return 0; }
igraph_error_t igraph_weighted_adjacency( igraph_t *graph, const igraph_matrix_t *adjmatrix, igraph_adjacency_t mode, igraph_vector_t *weights, igraph_loops_t loops );
The order of the vertices in the matrix is preserved, i.e. the vertex corresponding to the first row/column will be vertex with id 0, the next row is for vertex 1, etc. No guarantees are given for the ordering of edges.
Arguments:

Pointer to an uninitialized graph object. 


The weighted adjacency matrix. How it is interpreted
depends on the 


Constant to specify how the given matrix is interpreted
as an adjacency matrix. Possible values
(A(i,j)
is the element in row i and column
j in the adjacency matrix



Pointer to an initialized vector, the weights will be stored here. 


Constant to specify how the diagonal of the matrix should be treated when creating loop edges.

Returns:
Error code,

Time complexity: O(VV), V is the number of vertices in the graph.
Example 9.4. File examples/simple/igraph_weighted_adjacency.c
#include <igraph.h> int main(void) { igraph_t graph; igraph_real_t data[4][4] = { { 0, 1.2, 2.3, 0 }, { 2.0, 0, 0, 1.0 }, { 0, 0, 1.5, 0 }, { 0, 1.0, 0, 0 } }; igraph_matrix_t mat; igraph_vector_t weights; igraph_vector_int_t edges; igraph_integer_t n; /* C arryas use rowmajor storage, while igraph's matrix uses columnmajor. * The matrix 'mat' will be the transpose of 'data'. */ igraph_matrix_view(&mat, *data, sizeof(data[0]) / sizeof(data[0][0]), sizeof(data) / sizeof(data[0])); /* Initialize vector into which weights will be written. */ igraph_vector_init(&weights, 0); igraph_weighted_adjacency(&graph, &mat, IGRAPH_ADJ_DIRECTED, &weights, IGRAPH_LOOPS_ONCE); /* When igraph_weighted_adjacency() returns, 'weights' will typically have * more capacity allocated than what it uses. We may optionally free any * unused capacity to save memory, although in most applications this * is not necessary. */ igraph_vector_resize_min(&weights); /* Get the edge list of the graph and output it, along with the weights. */ igraph_vector_int_init(&edges, 0); igraph_get_edgelist(&graph, &edges, 0); n = igraph_ecount(&graph); for (igraph_integer_t i = 0; i < n; i++) { printf("%" IGRAPH_PRId " > %" IGRAPH_PRId ": %g\n", VECTOR(edges)[2*i], VECTOR(edges)[2*i + 1], VECTOR(weights)[i]); } /* Free all allocated storage. */ igraph_vector_int_destroy(&edges); igraph_destroy(&graph); igraph_vector_destroy(&weights); return 0; }
igraph_error_t igraph_sparse_adjacency(igraph_t *graph, igraph_sparsemat_t *adjmatrix, igraph_adjacency_t mode, igraph_loops_t loops);
This has the same functionality as igraph_adjacency()
, but uses
a columncompressed adjacency matrix.
Time complexity: O(E),
where E is the number of edges in the graph.
igraph_error_t igraph_sparse_weighted_adjacency( igraph_t *graph, igraph_sparsemat_t *adjmatrix, igraph_adjacency_t mode, igraph_vector_t *weights, igraph_loops_t loops );
This has the same functionality as igraph_weighted_adjacency()
, but uses
a columncompressed adjacency matrix.
Time complexity: O(E),
where E is the number of edges in the graph.
igraph_error_t igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist, igraph_neimode_t mode, igraph_bool_t duplicate);
An adjacency list is a list of vectors, containing the neighbors
of all vertices. For operations that involve many changes to the
graph structure, it is recommended that you convert the graph into
an adjacency list via igraph_adjlist_init()
, perform the
modifications (these are cheap for an adjacency list) and then
recreate the igraph graph via this function.
Arguments:

Pointer to an uninitialized graph object. 

The adjacency list. 

Whether or not to create a directed graph. 

Logical, for undirected graphs this specified
whether each edge is included twice, in the vectors of
both adjacent vertices. If this is 
Returns:
Error code. 
See also:

Time complexity: O(V+E).
igraph_error_t igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode, igraph_integer_t center);
Arguments:

Pointer to an uninitialized graph object, this will be the result. 


Integer constant, the number of vertices in the graph. 


Constant, gives the type of the star graph to create. Possible values:



Id of the vertex which will be the center of the graph. 
Returns:
Error code:

Time complexity: O(V), the number of vertices in the graph.
See also:

Example 9.5. File examples/simple/igraph_star.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t graph; /* Create an undirected 6star, with the 0th node as the centre. */ igraph_star(&graph, 7, IGRAPH_STAR_UNDIRECTED, 0); /* Output the edge list of the graph. */ igraph_write_graph_edgelist(&graph, stdout); /* Destroy the graph when we are done using it. */ igraph_destroy(&graph); return 0; }
igraph_error_t igraph_wheel(igraph_t *graph, igraph_integer_t n, igraph_wheel_mode_t mode, igraph_integer_t center);
A wheel graph on n
vertices can be thought of as a wheel with
n  1
spokes. The cycle graph part makes up the rim,
while the star graph part adds the spokes.
Note that the two and threevertex wheel graphs are nonsimple: The twovertex wheel graph contains a selfloop, while the threevertex wheel graph contains parallel edges (a 1cycle and a 2cycle, respectively).
Arguments:

Pointer to an uninitialized graph object, this will be the result. 


Integer constant, the number of vertices in the graph. 


Constant, gives the type of the star graph to create. Possible values:



Id of the vertex which will be the center of the graph. 
Returns:
Error code:

Time complexity: O(V), the number of vertices in the graph.
See also:

igraph_error_t igraph_hypercube(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed);
The hypercube graph Q_n
has 2^n
vertices and
2^(n1) n
edges. Two vertices are connected when the binary
representations of their zerobased vertex IDs differs in precisely one bit.
Arguments:

An uninitialized graph object. 

The dimension of the hypercube graph. 

Whether the graph should be directed. Edges will point from lower index vertices towards higher index ones. 
Returns:
Error code. 
See also:
Time complexity: O(2^n)
igraph_error_t igraph_square_lattice( igraph_t *graph, const igraph_vector_int_t *dimvector, igraph_integer_t nei, igraph_bool_t directed, igraph_bool_t mutual, const igraph_vector_bool_t *periodic );
Creates ddimensional square lattices of the given size. Optionally, the lattice can be made periodic, and the neighbors within a given graph distance can be connected.
In the zerodimensional case, the singleton graph is returned.
The vertices of the resulting graph are ordered such that the
index of the vertex at position (i_1, i_2, i_3, ..., i_d)
in a lattice of size (n_1, n_2, ..., n_d)
will be
i_1 + n_1 * i_2 + n_1 * n_2 * i_3 + ...
.
Arguments:

An uninitialized graph object. 

Vector giving the sizes of the lattice in each of its dimensions. The dimension of the lattice will be the same as the length of this vector. 

Integer value giving the distance (number of steps) within which two vertices will be connected. 

Boolean, whether to create a directed graph.
If the 

Boolean, if the graph is directed this gives whether to create all connections as mutual. 

Boolean vector, defines whether the generated lattice is
periodic along each dimension. The length of this vector must match
the length of 
Returns:
Error code:

Time complexity: If nei
is less than two then it is O(V+E) (as
far as I remember), V and E are the number of vertices
and edges in the generated graph. Otherwise it is O(V*d^k+E), d
is the average degree of the graph, k is the nei
argument.
igraph_error_t igraph_triangular_lattice( igraph_t *graph, const igraph_vector_int_t *dims, igraph_bool_t directed, igraph_bool_t mutual);
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
Creates a triangular lattice whose vertices have the form (i, j) for nonnegative integers i and j
and (i, j) is generally connected with (i + 1, j), (i, j + 1), and (i  1, j + 1).
The function constructs a planar dual of the graph constructed by igraph_hexagonal_lattice()
.
In particular, there a onetoone correspondence between the vertices in the constructed graph
and the cycles of length 6 in the graph constructed by igraph_hexagonal_lattice()
with the same dims
parameter.
The vertices of the resulting graph are ordered lexicographically with the 2nd coordinate being more significant, e.g., (i, j) < (i + 1, j) and (i + 1, j) < (i, j + 1)
Arguments:

An uninitialized graph object. 

Integer vector, defines the shape of the lattice. (Below the "edge length"s are in terms of graph theoretical path lengths.)
If 

Boolean, whether to create a directed graph.
If the 

Boolean, if the graph is directed this gives whether to create all connections as mutual. 
Returns:
Error code:

See also:

Time complexity: O(V), where V is the number of vertices in the generated graph.
igraph_error_t igraph_hexagonal_lattice( igraph_t *graph, const igraph_vector_int_t *dims, igraph_bool_t directed, igraph_bool_t mutual );
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
Creates a hexagonal lattice whose vertices have the form (i, j) for nonnegative integers i and j
and (i, j) is generally connected with (i + 1, j), and if i is odd also with (i  1, j + 1).
The function constructs a planar dual of the graph constructed by igraph_triangular_lattice()
.
In particular, there a onetoone correspondence between the cycles of length 6 in the constructed graph
and the vertices of the graph constructed by igraph_triangular_lattice()
function
with the same dims
parameter.
The vertices of the resulting graph are ordered lexicographically with the 2nd coordinate being more significant, e.g., (i, j) < (i + 1, j) and (i + 1, j) < (i, j + 1)
Arguments:

An uninitialized graph object. 

Integer vector, defines the shape of the lattice. (Below the "edge length"s are in terms of graph theoretical path lengths.)
If 

Boolean, whether to create a directed graph.
If the 

Boolean, if the graph is directed this gives whether to create all connections as mutual. 
Returns:
Error code:

See also:

Time complexity: O(V), where V is the number of vertices in the generated graph.
igraph_error_t igraph_ring(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t mutual, igraph_bool_t circular);
A circular ring on n
vertices is commonly known in graph
theory as the cycle graph, and often denoted by C_n
.
Removing a single edge from the cycle graph C_n
results
in the path graph P_n
. This function can generate both.
When n
is 1 or 2, the result may not be a simple graph:
the onecycle contains a selfloop and the undirected or reciprocally
connected directed twocycle contains parallel edges.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

Logical, whether to create a directed graph. All edges will be oriented in the same direction along the cycle or path. 

Logical, whether to create mutual edges in directed graphs. It is ignored for undirected graphs. 

Logical, whether to create a closed ring (a cycle) or an open path. 
Returns:
Error code:

Time complexity: O(V), the number of vertices in the graph.
See also:

Example 9.6. File examples/simple/igraph_ring.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t graph; /* Create a directed path graph on 10 vertices. */ igraph_ring(&graph, 10, IGRAPH_DIRECTED, /* mutual= */ 0, /* circular= */ 0); /* Output the edge list of the graph. */ printf("10path graph:\n"); igraph_write_graph_edgelist(&graph, stdout); /* Destroy the graph. */ igraph_destroy(&graph); /* Create a 4cycle graph. */ igraph_ring(&graph, 4, IGRAPH_UNDIRECTED, /* mutual= */ 0, /* circular= */ 1); /* Output the edge list of the graph. */ printf("\n4cycle graph:\n"); igraph_write_graph_edgelist(&graph, stdout); /* Destroy the graph. */ igraph_destroy(&graph); return 0; }
igraph_error_t igraph_kary_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children, igraph_tree_mode_t type);
To obtain a completely symmetric tree with l
layers, where each
vertex has precisely children
descendants, use
n = (children^(l+1)  1) / (children  1)
.
Such trees are often called k
ary trees, where k
refers
to the number of children.
Note that for n=0
, the null graph is returned,
which is not considered to be a tree by igraph_is_tree()
.
Arguments:

Pointer to an uninitialized graph object. 


Integer, the number of vertices in the graph. 


Integer, the number of children of a vertex in the tree. 


Constant, gives whether to create a directed tree, and if this is the case, also its orientation. Possible values:

Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:

Example 9.7. File examples/simple/igraph_kary_tree.c
#include <igraph.h> int main(void) { igraph_t graph; igraph_bool_t res; /* Create a directed binary tree on 15 nodes, with edges pointing towards the root. */ igraph_kary_tree(&graph, 15, 2, IGRAPH_TREE_IN); igraph_is_tree(&graph, &res, NULL, IGRAPH_IN); printf("Is it an intree? %s\n", res ? "Yes" : "No"); igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT); printf("Is it an outtree? %s\n", res ? "Yes" : "No"); igraph_destroy(&graph); return 0; }
igraph_error_t igraph_symmetric_tree(igraph_t *graph, const igraph_vector_int_t *branches, igraph_tree_mode_t type);
This function creates a tree in which all vertices at distance d
from the
root have branching_counts
[d] children.
Arguments:

Pointer to an uninitialized graph object. 


Vector detailing the number of branches at each level. 


Constant, gives whether to create a directed tree, and if this is the case, also its orientation. Possible values:

Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:

Example 9.8. File examples/simple/igraph_symmetric_tree.c
#include <igraph.h> int main(void) { igraph_t graph; igraph_bool_t res; igraph_vector_int_t v; igraph_vector_int_init_int(&v, 3, 3, 4, 5); /* Create a directed symmetric tree with 2 levels  3 children in first and 4 children in second level, 5 children in third level with edges pointing towards the root. */ igraph_symmetric_tree(&graph, &v, IGRAPH_TREE_IN); igraph_is_tree(&graph, &res, NULL, IGRAPH_IN); printf("Is it an intree? %s\n", res ? "Yes" : "No"); igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT); printf("Is it an outtree? %s\n", res ? "Yes" : "No"); igraph_destroy(&graph); igraph_vector_int_destroy(&v); return 0; }
igraph_error_t igraph_regular_tree(igraph_t *graph, igraph_integer_t h, igraph_integer_t k, igraph_tree_mode_t type);
All vertices of a regular tree, except its leaves, have the same total degree k
.
This is different from a kary tree (igraph_kary_tree()
), where all
vertices have the same number of children, thus the degre of the root is
one less than the degree of the other internal vertices. Regular trees
are also referred to as Bethe lattices.
Arguments:

Pointer to an uninitialized graph object. 


The height of the tree, i.e. the distance between the root and the leaves. 


The degree of the regular tree. 


Constant, gives whether to create a directed tree, and if this is the case, also its orientation. Possible values:

Returns:
Error code. 
Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:

Example 9.9. File examples/simple/igraph_regular_tree.c
#include <igraph.h> int main(void) { igraph_t tree; igraph_vector_t eccentricity; igraph_bool_t is_tree; /* Create a Bethe lattice with 5 levels, i.e. height 4. */ igraph_regular_tree(&tree, 4, 3, IGRAPH_TREE_UNDIRECTED); /* Bethe lattices are trees. */ igraph_is_tree(&tree, &is_tree, NULL, IGRAPH_ALL); printf("Is it a tree? %s\n", is_tree ? "Yes." : "No."); /* Compute and print eccentricities. The root is the most central. */ igraph_vector_init(&eccentricity, 0); igraph_eccentricity(&tree, &eccentricity, igraph_vss_all(), IGRAPH_ALL); printf("Vertex eccentricities:\n"); igraph_vector_print(&eccentricity); igraph_vector_destroy(&eccentricity); /* Clean up. */ igraph_destroy(&tree); return 0; }
igraph_error_t igraph_tree_from_parent_vector( igraph_t *graph, const igraph_vector_int_t *parents, igraph_tree_mode_t type);
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
Rooted trees and forests are conveniently represented using a parents
vector where the ID of the parent of vertex v
is stored in parents[v]
.
This function serves to construct an igraph graph from a parent vector representation.
The result is guaranteed to be a forest or a tree. If the parents
vector
is found to encode a cycle or a selfloop, an error is raised.
Several igraph functions produce such vectors, such as graph traversal
functions (igraph_bfs()
and igraph_dfs()
), shortest path functions
that construct a shortest path tree, as well as some other specialized
functions like igraph_dominator_tree()
or igraph_cohesive_blocks()
.
Vertices which do not have parents (i.e. roots) get a negative entry in the
parents
vector.
Use igraph_bfs()
or igraph_dfs()
to convert a forest into a parent
vector representation. For trees, i.e. forests with a single root, it is
more convenient to use igraph_bfs_simple()
.
Arguments:

Pointer to an uninitialized graph object. 


The parent vector. 


Constant, gives whether to create a directed tree, and if this is the case, also its orientation. Possible values:

Returns:
Error code. 
See also:

Time complexity: O(n) where n is the length of parents
.
igraph_error_t igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_bool_t loops);
In a full graph every possible edge is present: every vertex is connected to every other vertex. igraph generalizes the usual concept of complete graphs in graph theory to graphs with selfloops as well as to directed graphs.
Arguments:

Pointer to an uninitialized graph object. 

Integer, the number of vertices in the graph. 

Logical, whether to create a directed graph. 

Logical, whether to include selfedges (loops). 
Returns:
Error code:

Time complexity: O(V^2) = O(E), where V is the number of vertices and E is the number of edges.
See also:

Example 9.10. File examples/simple/igraph_full.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t graph; igraph_integer_t n_vertices = 10; /* Create an undirected complete graph. */ /* Use IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS instead of true and false for better readability. */ igraph_full(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS); printf("The undirected complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n", igraph_vcount(&graph), igraph_ecount(&graph)); /* Remember to destroy the object at the end. */ igraph_destroy(&graph); /* Create a directed complete graph. */ igraph_full(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS); printf("The directed complete graph on %" IGRAPH_PRId " vertices has %" IGRAPH_PRId " edges.\n", igraph_vcount(&graph), igraph_ecount(&graph)); igraph_destroy(&graph); /* Create an undirected complete graph with selfloops. */ igraph_full(&graph, n_vertices, IGRAPH_UNDIRECTED, IGRAPH_LOOPS); printf("The undirected complete graph on %" IGRAPH_PRId " vertices with selfloops has %" IGRAPH_PRId " edges.\n", igraph_vcount(&graph), igraph_ecount(&graph)); igraph_destroy(&graph); /* Create a directed graph with selfloops. */ igraph_full(&graph, n_vertices, IGRAPH_DIRECTED, IGRAPH_LOOPS); printf("The directed complete graph on %" IGRAPH_PRId " vertices with selfloops has %" IGRAPH_PRId " edges.\n", igraph_vcount(&graph), igraph_ecount(&graph)); igraph_destroy(&graph); return 0; }
igraph_error_t igraph_full_citation(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed);
This is a directed graph, where every i>j
edge is
present if and only if j<i
.
If the directed
argument is false then an undirected graph is
created, and it is just a complete graph.
Arguments:

Pointer to an uninitialized graph object, the result is stored here. 

The number of vertices. 

Whether to created a directed graph. If false an undirected graph is created. 
Returns:
Error code. 
See also:
Time complexity: O(V^2) = O(E), where V is the number of vertices and E is the number of edges.
igraph_error_t igraph_full_multipartite(igraph_t *graph, igraph_vector_int_t *types, const igraph_vector_int_t *n, igraph_bool_t directed, igraph_neimode_t mode);
A multipartite graph contains two or more types of vertices and connections are only possible between two vertices of different types. This function creates a complete multipartite graph.
Arguments:

Pointer to an uninitialized graph object, the graph will be created here. 

Pointer to an integer vector. If not a null pointer, the type of each vertex will be stored here. 

Pointer to an integer vector, the number of vertices of each type. 

Boolean, whether to create a directed graph. 

A constant that gives the type of connections for
directed graphs. If 
Returns:
Error code. 
Time complexity: O(V+E), linear in the number of vertices and edges.
See also:

igraph_error_t igraph_turan(igraph_t *graph, igraph_vector_int_t *types, igraph_integer_t n, igraph_integer_t r);
Turán graphs are complete multipartite graphs with the property that the sizes of the partitions are as close to equal as possible.
The Turán graph with n
vertices and r
partitions is the densest
graph on n
vertices that does not contain a clique of size
r+1
.
This function generates undirected graphs. The null graph is returned when the number of vertices is zero. A complete graph is returned if the number of partitions is greater than the number of vertices.
Arguments:

Pointer to an igraph_t object, the graph will be created here. 

Pointer to an integer vector. If not a null pointer, the type (partition index) of each vertex will be stored here. 

Integer, the number of vertices in the graph. 

Integer, the number of partitions of the graph, must be positive. 
Returns:
Error code. 
Time complexity: O(V+E), linear in the number of vertices and edges.
See also:

igraph_error_t igraph_realize_degree_sequence( igraph_t *graph, const igraph_vector_int_t *outdeg, const igraph_vector_int_t *indeg, igraph_edge_type_sw_t allowed_edge_types, igraph_realize_degseq_t method);
This function generates an undirected graph that realizes a given degree sequence, or a directed graph that realizes a given pair of out and indegree sequences.
Simple undirected graphs are constructed using the HavelHakimi algorithm (undirected case), or the analogous KleitmanWang algorithm (directed case). These algorithms work by choosing an arbitrary vertex and connecting all its stubs to other vertices of highest degree. In the directed case, the "highest" (in, out) degree pairs are determined based on lexicographic ordering. This step is repeated until all degrees have been connected up.
Loopless multigraphs are generated using an analogous algorithm: an arbitrary vertex is chosen, and it is connected with a single connection to a highest remaining degee vertex. If selfloops are also allowed, the same algorithm is used, but if a nonzero vertex remains at the end of the procedure, the graph is completed by adding selfloops to it. Thus, the result will contain at most one vertex with selfloops.
The method
parameter controls the order in which the vertices to be
connected are chosen. In the undirected case, IGRAPH_REALIZE_DEGSEQ_SMALLEST
produces a connected graph when one exists. This makes this method suitable
for constructing trees with a given degree sequence.
References:
V. Havel: Poznámka o existenci konečných grafů (A remark on the existence of finite graphs), Časopis pro pěstování matematiky 80, 477480 (1955). http://eudml.org/doc/19050
S. L. Hakimi: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph, Journal of the SIAM 10, 3 (1962). https://www.jstor.org/stable/2098770
D. J. Kleitman and D. L. Wang: Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, Discrete Mathematics 6, 1 (1973). https://doi.org/10.1016/0012365X%2873%2990037X P. L. Erdős, I. Miklós, Z. Toroczkai: A simple HavelHakimi type algorithm to realize graphical degree sequences of directed graphs, The Electronic Journal of Combinatorics 17.1 (2010). http://eudml.org/doc/227072
Sz. Horvát and C. D. Modes: Connectedness matters: construction and exact random sampling of connected networks (2021). https://doi.org/10.1088/2632072X/abced5
Arguments:

Pointer to an uninitialized graph object. 


The degree sequence of an undirected graph (if 


The indegree sequence of a directed graph. Pass 


The types of edges to allow in the graph. For
directed graphs, only



The method to generate the graph. Possible values:

Returns:
Error code:

See also:

Example 9.11. File examples/simple/igraph_realize_degree_sequence.c
#include <igraph.h> #include <stdio.h> int main(void){ igraph_t g1, g2, g3; igraph_integer_t nodes = 500, A = 0, power = 1, m = 1; igraph_real_t assortativity; igraph_rng_seed(igraph_rng_default(), 42); printf("Demonstration of difference in assortativities of graphs with the same degree sequence but different linkages:\n\nInitial graph based on the BarabasiAlbert model with %" IGRAPH_PRId " nodes.\n", nodes); /* Graph 1 generated by a randomized graph generator */ igraph_barabasi_game(&g1, nodes, power, m, NULL, /* outpref */ 0, A, IGRAPH_UNDIRECTED, IGRAPH_BARABASI_PSUMTREE, /* start from */ NULL); igraph_vector_int_t degree; igraph_vector_int_init(°ree, nodes); igraph_degree(&g1, °ree, igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS); /* Measuring assortativity of the first graph */ igraph_assortativity_degree(&g1, &assortativity, IGRAPH_UNDIRECTED); printf("Assortativity of initial graph = %g\n\n", assortativity); igraph_destroy(&g1); /* Graph 2 (with the same degree sequence) generated by selecting vertices with the smallest degree first */ igraph_realize_degree_sequence(&g2, °ree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_SMALLEST); igraph_assortativity_degree(&g2, &assortativity, IGRAPH_UNDIRECTED); printf("Assortativity after choosing vertices with the smallest degrees first = %g\n\n", assortativity); igraph_destroy(&g2); /* Graph 3 (with the same degree sequence) generated by selecting vertices with the largest degree first */ igraph_realize_degree_sequence(&g3, °ree, NULL, IGRAPH_SIMPLE_SW, IGRAPH_REALIZE_DEGSEQ_LARGEST); igraph_assortativity_degree(&g3, &assortativity, IGRAPH_UNDIRECTED); printf("Assortativity after choosing vertices with the largest degrees first = %g\n", assortativity); igraph_destroy(&g3); igraph_vector_int_destroy(°ree); return 0; }
igraph_error_t igraph_realize_bipartite_degree_sequence( igraph_t *graph, const igraph_vector_int_t *degrees1, const igraph_vector_int_t *degrees2, const igraph_edge_type_sw_t allowed_edge_types, const igraph_realize_degseq_t method );
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
This function generates a bipartite graph with the given bidegree sequence,
using a HavelHakimilike construction algorithm. The order in which vertices
are connected up is controlled by the method
parameter. When using the
IGRAPH_REALIZE_DEGSEQ_SMALLEST
method, it is ensured that the graph will be
connected if and only if the given bidegree sequence is potentially connected.
The vertices of the graph will be ordered so that those having degrees1
come first, followed by degrees2
.
Arguments:

Pointer to an uninitialized graph object. 


The degree sequence of the first partition. 


The degree sequence of the second partition. 


The types of edges to allow in the graph.



Controls the order in which vertices are selected for connection. Possible values:

Returns:
Error code. 
See also:

igraph_error_t igraph_famous(igraph_t *graph, const char *name);
The name of the graph can be simply supplied as a string.
Note that this function creates graphs which don't take any parameters,
there are separate functions for graphs with parameters, e.g. igraph_full()
for creating a full graph.
The following graphs are supported:

The bull graph, 5 vertices, 5 edges, resembles the head of a bull if drawn properly. 

This is the smallest trianglefree graph that is both 4chromatic and 4regular. According to the Grunbaum conjecture there exists an mregular, mchromatic graph with n vertices for every m>1 and n>2. The Chvatal graph is an example for m=4 and n=12. It has 24 edges. 

A nonHamiltonian cubic symmetric graph with 28 vertices and 42 edges. 

The Platonic graph of the cube. A convex regular polyhedron with 8 vertices and 12 edges. 

A graph with 4 vertices and 5 edges, resembles a schematic diamond if drawn properly. 

Another Platonic solid with 20 vertices and 30 edges. 

The semisymmetric graph with minimum number of vertices, 20 and 40 edges. A semisymmetric graph is regular, edge transitive and not vertex transitive. 

This is a graph whose embedding to the Klein bottle can be colored with six colors, it is a counterexample to the necessity of the Heawood conjecture on a Klein bottle. It has 12 vertices and 18 edges. 

The Frucht Graph is the smallest cubical graph whose automorphism group consists only of the identity element. It has 12 vertices and 18 edges. 

The Grötzsch graph is a trianglefree graph with 11 vertices, 20 edges, and chromatic number 4. It is named after German mathematician Herbert Grötzsch, and its existence demonstrates that the assumption of planarity is necessary in Grötzsch's theorem that every trianglefree planar graph is 3colorable. 

The Heawood graph is an undirected graph with 14 vertices and 21 edges. The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6cage, the smallest cubic graph of girth 6. 

The Herschel graph is the smallest nonhamiltonian polyhedral graph. It is the unique such graph on 11 nodes, and has 18 edges. 

The house graph is a 5vertex, 6edge graph, the schematic draw of a house if drawn properly, basically a triangle on top of a square. 

The same as the house graph with an X in the square. 5 vertices and 8 edges. 

A Platonic solid with 12 vertices and 30 edges. 

A social network with 10 vertices and 18 edges. Krackhardt, D. Assessing the Political Landscape: Structure, Cognition, and Power in Organizations. Admin. Sci. Quart. 35, 342369, 1990. 

The graph is a 4arc transitive cubic graph, it has 30 vertices and 45 edges. 

The McGee graph is the unique 3regular 7cage graph, it has 24 vertices and 36 edges. 

The Meredith graph is a quartic graph on 70 nodes and 140 edges that is a counterexample to the conjecture that every 4regular 4connected graph is Hamiltonian. 

A connected graph with 16 vertices and 27 edges containing no perfect matching. A matching in a graph is a set of pairwise nonincident edges; that is, no two edges share a common vertex. A perfect matching is a matching which covers all vertices of the graph. 

A graph whose connected components are the 9 graphs whose presence as a vertexinduced subgraph in a graph makes a nonline graph. It has 50 vertices and 72 edges. 

Platonic solid with 6 vertices and 12 edges. 

A 3regular graph with 10 vertices and 15 edges. It is the smallest hypohamiltonian graph, i.e. it is nonhamiltonian but removing any single vertex from it makes it Hamiltonian. 

The unique (4,5)cage graph, i.e. a 4regular graph of girth 5. It has 19 vertices and 38 edges. 

A smallest nontrivial graph whose automorphism group is cyclic. It has 9 vertices and 15 edges. 

Platonic solid with 4 vertices and 6 edges. 

The smallest hypotraceable graph, on 34 vertices and 52 edges. A hypotracable graph does not contain a Hamiltonian path but after removing any single vertex from it the remainder always contains a Hamiltonian path. A graph containing a Hamiltonian path is called traceable. 

Tait's Hamiltonian graph conjecture states that every 3connected 3regular planar graph is Hamiltonian. This graph is a counterexample. It has 46 vertices and 69 edges. 

Returns a 12vertex, trianglefree graph with chromatic number 3 that is uniquely 3colorable. 

An identity graph with 25 vertices and 31 edges. An identity graph has a single graph automorphism, the trivial one. 

Social network of friendships between 34 members of a karate club at a US university in the 1970s. See W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452473 (1977). 
Arguments:

Pointer to an uninitialized graph object. 

Character constant, the name of the graph to be created, it is case insensitive. 
Returns:
Error code, 
See also:
Other functions for creating graph structures:

Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
igraph_error_t igraph_lcf(igraph_t *graph, igraph_integer_t n, ...);
LCF is short for LederbergCoxeterFrucht, it is a concise notation for 3regular Hamiltonian graphs. It consists of three parameters: the number of vertices in the graph, a list of shifts giving additional edges to a cycle backbone, and another integer giving how many times the shifts should be performed. See https://mathworld.wolfram.com/LCFNotation.html for details.
Arguments:

Pointer to an uninitialized graph object. 

Integer, the number of vertices in the graph. 

The shifts and the number of repeats for the shifts, plus an additional 0 to mark the end of the arguments. 
Returns:
Error code. 
See also:
See 
Time complexity: O(V+E), the number of vertices plus the number of edges.
Example 9.12. File examples/simple/igraph_lcf.c
#include <igraph.h> int main(void) { igraph_t g, g2; igraph_bool_t iso; // Franklin graph igraph_lcf(&g, 12, 5, 5, 6, 0); igraph_famous(&g2, "franklin"); igraph_isomorphic_vf2(&g, &g2, /*vertex.color1=*/ 0, /*vertex.color2=*/ 0, /*edge.color1=*/ 0, /*edge.color2=*/ 0, &iso, 0, 0, 0, 0, 0); if (!iso) { printf("Failure: Franklin\n"); return 1; } igraph_destroy(&g); igraph_destroy(&g2); // [3, 2]^4, n=8 igraph_lcf(&g, 8, 3, 2, 4, 0); if (igraph_ecount(&g) != 16) { printf("Failure: [3, 2]^4, n=8\n"); return 1; } igraph_destroy(&g); // [2, 2]^2, n=2 igraph_lcf(&g, 2, 2, 2, 2, 0); if (igraph_ecount(&g) != 1) { printf("Failure: [2, 2]^2, n=2\n"); return 1; } igraph_destroy(&g); // [2]^2, n=2 igraph_lcf(&g, 2, 2, 2, 0); if (igraph_ecount(&g) != 1) { printf("Failure: [2]^2, n=2\n"); return 1; } igraph_destroy(&g); // Regression test for bug #996 igraph_lcf(&g, 0, 0); if (igraph_vcount(&g) != 0  igraph_ecount(&g) != 0) { printf("Failure: regression test for #996\n"); return 1; } igraph_destroy(&g); return 0; }
igraph_error_t igraph_lcf_vector(igraph_t *graph, igraph_integer_t n, const igraph_vector_int_t *shifts, igraph_integer_t repeats);
This function is essentially the same as igraph_lcf()
, only
the way for giving the arguments is different. See igraph_lcf()
for details.
Arguments:

Pointer to an uninitialized graph object. 

Integer constant giving the number of vertices. 

A vector giving the shifts. 

An integer constant giving the number of repeats for the shifts. 
Returns:
Error code. 
See also:
Time complexity: O(V+E), linear in the number of vertices plus the number of edges.
igraph_error_t igraph_from_prufer(igraph_t *graph, const igraph_vector_int_t *prufer);
A Prüfer sequence is a unique sequence of integers associated
with a labelled tree. A tree on n
vertices can be represented
by a sequence of n2
integers, each between 0
and
n1
(inclusive).
The algorithm used by this function is based on
Paulius Micikevičius, Saverio Caminiti, Narsingh Deo:
Lineartime Algorithms for Encoding Trees as Sequences of Node Labels
Arguments:

Pointer to an uninitialized graph object. 

The Prüfer sequence 
Returns:
Error code:

See also:
Time complexity: O(V), where V is the number of vertices in the tree.
igraph_error_t igraph_atlas(igraph_t *graph, igraph_integer_t number);
The graph atlas contains all simple undirected unlabeled graphs on between 0 and 7 vertices. The number of the graph is given as a parameter. The graphs are listed:
in increasing order of number of vertices;
for a fixed number of vertices, in increasing order of the number of edges;
for fixed numbers of vertices and edges, in laxicographically increasing order of the degree sequence, for example 111223 < 112222;
for fixed degree sequence, in increasing number of automorphisms.
The data was converted from the NetworkX software package, see https://networkx.org/.
See An Atlas of Graphs by Ronald C. Read and Robin J. Wilson, Oxford University Press, 1998.
Arguments:

Pointer to an uninitialized graph object. 

The number of the graph to generate. Must be between 0 and 1252 (inclusive). Graphs on 07 vertices start at numbers 0, 1, 2, 4, 8, 19, 53, and 209, respectively. 
Added in version 0.2.
Time complexity: O(V+E), the number of vertices plus the number of edges.
Example 9.13. File examples/simple/igraph_atlas.c
#include <igraph.h> int main(void) { igraph_t g; igraph_atlas(&g, 45); igraph_write_graph_edgelist(&g, stdout); printf("\n"); igraph_destroy(&g); igraph_atlas(&g, 0); igraph_write_graph_edgelist(&g, stdout); printf("\n"); igraph_destroy(&g); igraph_atlas(&g, 1252); igraph_write_graph_edgelist(&g, stdout); printf("\n"); igraph_destroy(&g); return 0; }
igraph_error_t igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);
A de Bruijn graph represents relationships between strings. An alphabet
of m
letters are used and strings of length n
are considered.
A vertex corresponds to every possible string and there is a directed edge
from vertex v
to vertex w
if the string of v
can be transformed into
the string of w
by removing its first letter and appending a letter to it.
Please note that the graph will have m
to the power n
vertices and
even more edges, so probably you don't want to supply too big numbers for
m
and n
.
De Bruijn graphs have some interesting properties, please see another source, e.g. Wikipedia for details.
Arguments:

Pointer to an uninitialized graph object, the result will be stored here. 

Integer, the number of letters in the alphabet. 

Integer, the length of the strings. 
Returns:
Error code. 
See also:
Time complexity: O(V+E), the number of vertices plus the number of edges.
igraph_error_t igraph_kautz(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);
A Kautz graph is a labeled graph, vertices are labeled by strings
of length n
+1 above an alphabet with m
+1 letters, with
the restriction that every two consecutive letters in the string
must be different. There is a directed edge from a vertex v
to
another vertex w
if it is possible to transform the string of
v
into the string of w
by removing the first letter and
appending a letter to it. For string length 1 the new letter
cannot equal the old letter, so there are no loops.
Kautz graphs have some interesting properties, see e.g. Wikipedia for details.
Vincent Matossian wrote the first version of this function in R, thanks.
Arguments:

Pointer to an uninitialized graph object, the result will be stored here. 

Integer, 

Integer, 
Returns:
Error code. 
See also:
Time complexity: O(V* [(m+1)/m]^n +E), in practice it is more
like O(V+E). V is the number of vertices, E is the number
of edges and m
and n
are the corresponding arguments.
igraph_error_t igraph_circulant(igraph_t *graph, igraph_integer_t n, const igraph_vector_int_t *shifts, igraph_bool_t directed);
A circulant graph G(n, shifts)
consists of n
vertices v_0
, ...,
v_(n1)
such that for each s_i
in the list of offsets shifts
, v_j
is
connected to v_((j + s_i) mod n)
for all j.
The function can generate either directed or undirected graphs. It does not generate multiedges or selfloops.
Arguments:

Pointer to an uninitialized graph object, the result will be stored here. 

Integer, the number of vertices in the circulant graph. 

Integer vector, a list of the offsets within the circulant graph. 

Boolean, whether to create a directed graph. 
Returns:
Error code. 
See also:
Time complexity: O(Vshifts), the number of vertices in the graph times the number of shifts.
igraph_error_t igraph_generalized_petersen(igraph_t *graph, igraph_integer_t n, igraph_integer_t k);
The generalized Petersen graph G(n, k)
consists of n
vertices
v_0
, ..., v_n
forming an "outer" cycle graph, and n
additional vertices
u_0
, ..., u_n
forming an "inner" circulant graph where u_i
is connected to u_(i + k mod n)
. Additionally, all v_i
are
connected to u_i
.
G(n, k)
has 2n
vertices and 3n
edges. The Petersen graph
itself is G(5, 2)
.
Reference:
M. E. Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, Journal of Combinatorial Theory 6, 152164 (1969). https://doi.org/10.1016%2FS00219800%2869%2980116X
Arguments:

Pointer to an uninitialized graph object, the result will be stored here. 

Integer, 

Integer, 
Returns:
Error code. 
See also:

Time complexity: O(V), the number of vertices in the graph.
igraph_error_t igraph_extended_chordal_ring( igraph_t *graph, igraph_integer_t nodes, const igraph_matrix_int_t *W, igraph_bool_t directed);
An extended chordal ring is a cycle graph with additional chords
connecting its vertices.
Each row L
of the matrix W
specifies a set of chords to be
inserted, in the following way: vertex i
will connect to a vertex
L[(i mod p)]
steps ahead of it along the cycle, where
p
is the length of L
.
In other words, vertex i
will be connected to vertex
(i + L[(i mod p)]) mod nodes
. If multiple edges are
defined in this way, this will output a nonsimple graph. The result
can be simplified using igraph_simplify()
.
See also Kotsis, G: Interconnection Topologies for Parallel Processing Systems, PARS Mitteilungen 11, 16, 1993. The igraph extended chordal rings are not identical to the ones in the paper. In igraph the matrix specifies which edges to add. In the paper, a condition is specified which should simultaneously hold between two endpoints and the reverse endpoints.
Arguments:

Pointer to an uninitialized graph object, the result will be stored here. 

Integer constant, the number of vertices in the graph. It must be at least 3. 

The matrix specifying the extra edges. The number of columns should divide the number of total vertices. The elements are allowed to be negative. 

Whether the graph should be directed. 
Returns:
Error code. 
See also:
Time complexity: O(V+E), the number of vertices plus the number of edges.
igraph_grg_game
— Generates a geometric random graph.igraph_barabasi_game
— Generates a graph based on the BarabásiAlbert model.igraph_erdos_renyi_game_gnm
— Generates a random (ErdősRényi) graph with a fixed number of edges.igraph_erdos_renyi_game_gnp
— Generates a random (ErdősRényi) graph with fixed edge probabilities.igraph_watts_strogatz_game
— The WattsStrogatz smallworld model.igraph_rewire_edges
— Rewires the edges of a graph with constant probability.igraph_rewire_directed_edges
— Rewires the chosen endpoint of directed edges.igraph_degree_sequence_game
— Generates a random graph with a given degree sequence.igraph_k_regular_game
— Generates a random graph where each vertex has the same degree.igraph_static_fitness_game
— Nongrowing random graph with edge probabilities proportional to node fitness scores.igraph_static_power_law_game
— Generates a nongrowing random graph with expected powerlaw degree distributions.igraph_chung_lu_game
— Samples graphs from the ChungLu model.igraph_forest_fire_game
— Generates a network according to the “forest fire game”.igraph_rewire
— Randomly rewires a graph while preserving its degree sequence.igraph_growing_random_game
— Generates a growing random graph.igraph_callaway_traits_game
— Simulates a growing network with vertex types.igraph_establishment_game
— Generates a graph with a simple growing model with vertex types.igraph_preference_game
— Generates a graph with vertex types and connection preferences.igraph_asymmetric_preference_game
— Generates a graph with asymmetric vertex types and connection preferences.igraph_recent_degree_game
— Stochastic graph generator based on the number of incident edges a node has gained recently.igraph_barabasi_aging_game
— Preferential attachment with aging of vertices.igraph_recent_degree_aging_game
— Preferential attachment based on the number of edges gained recently, with aging of vertices.igraph_lastcit_game
— Simulates a citation network, based on time passed since the last citation.igraph_cited_type_game
— Simulates a citation based on vertex types.igraph_citing_cited_type_game
— Simulates a citation network based on vertex types.igraph_sbm_game
— Sample from a stochastic block model.igraph_hsbm_game
— Hierarchical stochastic block model.igraph_hsbm_list_game
— Hierarchical stochastic block model, more general version.igraph_dot_product_game
— Generates a random dot product graph.igraph_tree_game
— Generates a random tree with the given number of nodes.igraph_correlated_game
— Generates a random graph correlated to an existing graph.igraph_correlated_pair_game
— Generates pairs of correlated random graphs.igraph_simple_interconnected_islands_game
— Generates a random graph made of several interconnected islands, each island being a random graph.Games are random graph generators, i.e. they generate a different graph every time they are called. igraph includes many such generators. Some implement stochastic graph construction processes inspired by realworld mechanics, such as preferential attachment, while others are designed to produce graphs with certain used properties (e.g. fixed number of edges, fixed degrees, etc.)
igraph_error_t igraph_grg_game(igraph_t *graph, igraph_integer_t nodes, igraph_real_t radius, igraph_bool_t torus, igraph_vector_t *x, igraph_vector_t *y);
A geometric random graph is created by dropping points (i.e. vertices)
randomly on the unit square and then connecting all those pairs
which are strictly less than radius
apart in Euclidean distance.
Original code contributed by Keith Briggs, thanks Keith.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

The radius within which the vertices will be connected. 

Logical constant. If true, periodic boundary conditions will be used, i.e. the vertices are assumed to be on a torus instead of a square. 

An initialized vector or 

An initialized vector or 
Returns:
Error code. 
Time complexity: TODO, less than O(V^2+E).
Example 9.14. File examples/simple/igraph_grg_game.c
#include <igraph.h> #include <math.h> int main(void) { igraph_t graph; igraph_vector_t x, y; igraph_vector_t weights; igraph_eit_t eit; igraph_real_t avg_dist; /* Set random seed for reproducible results */ igraph_rng_seed(igraph_rng_default(), 42); /* Create a random geometric graph and retrieve vertex coordinates */ igraph_vector_init(&x, 0); igraph_vector_init(&y, 0); igraph_grg_game(&graph, 200, 0.1, /* torus */ 0, &x, &y); /* Compute edge weights as geometric distance */ igraph_vector_init(&weights, igraph_ecount(&graph)); igraph_eit_create(&graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &eit); for (; ! IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit)) { igraph_integer_t e = IGRAPH_EIT_GET(eit); igraph_integer_t u = IGRAPH_FROM(&graph, e); igraph_integer_t v = IGRAPH_TO(&graph, e); VECTOR(weights)[e] = hypot(VECTOR(x)[u]  VECTOR(x)[v], VECTOR(y)[u]  VECTOR(y)[v]); } igraph_eit_destroy(&eit); /* Compute average path length */ igraph_average_path_length_dijkstra(&graph, &avg_dist, NULL, &weights, IGRAPH_UNDIRECTED, /* unconn */ 1); printf("Average distance in the geometric graph: %g.\n", avg_dist); /* Destroy data structures when no longer needed */ igraph_vector_destroy(&weights); igraph_destroy(&graph); igraph_vector_destroy(&x); igraph_vector_destroy(&y); return 0; }
igraph_error_t igraph_barabasi_game(igraph_t *graph, igraph_integer_t n, igraph_real_t power, igraph_integer_t m, const igraph_vector_int_t *outseq, igraph_bool_t outpref, igraph_real_t A, igraph_bool_t directed, igraph_barabasi_algorithm_t algo, const igraph_t *start_from);
This function implements several variants of the preferential attachment
process, including linear and nonlinear varieties of the BarabásiAlbert
and Price models. The graph construction starts with a single vertex,
or an existing graph given by the start_from
parameter. Then new vertices
are added one at a time. Each new vertex connects to m
existing vertices,
choosing them with probabilities proportional to
d^power + A
,
where d
is the in or total degree of the existing vertex (controlled
by the outpref
argument), while power
and A
are given by
parameters. The constant attractiveness A
is used to ensure that vertices with zero indegree can also be
connected to with nonzero probability.
Barabási, A.L. and Albert R. 1999. Emergence of scaling in random networks, Science, 286 509512. https://doi.org/10.1126/science.286.5439.509
de Solla Price, D. J. 1965. Networks of Scientific Papers, Science, 149 510515. https://doi.org/10.1126/science.149.3683.510
Arguments:

An uninitialized graph object. 


The number of vertices in the graph. 


Power of the preferential attachment. In the classic preferential
attachment model 


The number of outgoing edges generated for each
vertex. Only used when 


Gives the (out)degrees of the vertices. If this is
constant, this can be a 


Boolean, if true not only the in but also the outdegree of a vertex increases its citation probability. I.e., the citation probability is determined by the total degree of the vertices. Ignored and assumed to be true if the graph being generated is undirected. 


The constant attractiveness of vertices. When 


Boolean, whether to generate a directed graph.
When set to 


The algorithm to use to generate the network. Possible values:



Either a 
Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges.
Example 9.15. File examples/simple/igraph_barabasi_game.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_t v; igraph_vector_int_t v2, v3; igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 0, /*A=*/ 1, 1, IGRAPH_BARABASI_BAG, /*start_from=*/ 0); if (igraph_ecount(&g) != 18) { return 1; } if (igraph_vcount(&g) != 10) { return 2; } if (!igraph_is_directed(&g)) { return 3; } igraph_vector_int_init(&v, 0); igraph_get_edgelist(&g, &v, 0); for (igraph_integer_t i = 0; i < igraph_ecount(&g); i++) { if (VECTOR(v)[2 * i] <= VECTOR(v)[2 * i + 1]) { return 4; } } igraph_vector_int_destroy(&v); igraph_destroy(&g); /* outdegree sequence */ igraph_vector_int_init_int(&v3, 10, 0, 1, 3, 3, 4, 5, 6, 7, 8, 9); igraph_barabasi_game(&g, 10, /*power=*/ 1, 0, &v3, 0, /*A=*/ 1, 1, IGRAPH_BARABASI_BAG, /*start_from=*/ 0); if (igraph_ecount(&g) != igraph_vector_int_sum(&v3)) { return 5; } igraph_vector_int_init(&v2, 0); igraph_degree(&g, &v2, igraph_vss_all(), IGRAPH_OUT, 1); for (igraph_integer_t i = 0; i < igraph_vcount(&g); i++) { if (VECTOR(v3)[i] != VECTOR(v2)[i]) { igraph_vector_int_print(&v3); printf("\n"); igraph_vector_int_print(&v2); return 6; } } igraph_vector_int_destroy(&v3); igraph_vector_int_destroy(&v2); igraph_destroy(&g); /* outpref, we cannot really test this quantitatively, would need to set random seed */ igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 1, /*A=*/ 1, 1, IGRAPH_BARABASI_BAG, /*start_from=*/ 0); igraph_vector_int_init(&v, 0); igraph_get_edgelist(&g, &v, 0); for (igraph_integer_t i = 0; i < igraph_ecount(&g); i++) { if (VECTOR(v)[2 * i] <= VECTOR(v)[2 * i + 1]) { return 7; } } if (!igraph_is_directed(&g)) { return 8; } igraph_vector_int_destroy(&v); igraph_destroy(&g); return 0; }
Example 9.16. File examples/simple/igraph_barabasi_game2.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t g; igraph_bool_t simple; igraph_barabasi_game(/* graph= */ &g, /* n= */ 100, /* power= */ 1.0, /* m= */ 2, /* outseq= */ 0, /* outpref= */ 0, /* A= */ 1.0, /* directed= */ IGRAPH_DIRECTED, /* algo= */ IGRAPH_BARABASI_PSUMTREE, /* start_from= */ 0); if (igraph_ecount(&g) != 197) { return 1; } if (igraph_vcount(&g) != 100) { return 2; } igraph_is_simple(&g, &simple); if (!simple) { return 3; } igraph_destroy(&g); /* ============================== */ igraph_barabasi_game(/* graph= */ &g, /* n= */ 100, /* power= */ 1.0, /* m= */ 2, /* outseq= */ 0, /* outpref= */ 0, /* A= */ 1.0, /* directed= */ IGRAPH_DIRECTED, /* algo= */ IGRAPH_BARABASI_PSUMTREE_MULTIPLE, /* start_from= */ 0); if (igraph_ecount(&g) != 198) { return 4; } if (igraph_vcount(&g) != 100) { return 5; } igraph_is_simple(&g, &simple); if (simple) { return 6; } igraph_destroy(&g); /* ============================== */ igraph_barabasi_game(/* graph= */ &g, /* n= */ 100, /* power= */ 1.0, /* m= */ 2, /* outseq= */ 0, /* outpref= */ 0, /* A= */ 1.0, /* directed= */ IGRAPH_DIRECTED, /* algo= */ IGRAPH_BARABASI_BAG, /* start_from= */ 0); if (igraph_ecount(&g) != 198) { return 7; } if (igraph_vcount(&g) != 100) { return 8; } igraph_is_simple(&g, &simple); if (simple) { return 9; } igraph_destroy(&g); return 0; }
igraph_error_t igraph_erdos_renyi_game_gnm( igraph_t *graph, igraph_integer_t n, igraph_integer_t m, igraph_bool_t directed, igraph_bool_t loops, igraph_bool_t multiple );
In the G(n, m)
ErdősRényi model, a graph with n
vertices
and m
edges is generated uniformly at random.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

The number of edges in the graph. 

Logical, whether to generate a directed graph. 

Logical, whether to generate selfloops. 

Logical, whether it is allowed to generate more than one edge between the same pair of vertices. 
Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:

Example 9.17. File examples/simple/igraph_erdos_renyi_game_gnm.c
#include <igraph.h> int main(void) { igraph_t graph; igraph_vector_int_t component_sizes; igraph_rng_seed(igraph_rng_default(), 42); /* make program deterministic */ /* Sample a graph from the ErdősRényi G(n,m) model */ igraph_erdos_renyi_game_gnm( &graph, /* n= */ 100, /* m= */ 100, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS, IGRAPH_NO_MULTIPLE ); /* Compute the fraction of vertices contained within the largest connected component */ igraph_vector_int_init(&component_sizes, 0); igraph_connected_components(&graph, NULL, &component_sizes, NULL, IGRAPH_STRONG); printf( "Fraction of vertices in giant component: %g\n", ((double) igraph_vector_int_max(&component_sizes)) / igraph_vcount(&graph) ); /* Clean up data structures when no longer needed */ igraph_vector_int_destroy(&component_sizes); igraph_destroy(&graph); return 0; }
igraph_error_t igraph_erdos_renyi_game_gnp( igraph_t *graph, igraph_integer_t n, igraph_real_t p, igraph_bool_t directed, igraph_bool_t loops );
In the G(n, p)
ErdősRényi model, also known as the Gilbert model,
or Bernoulli random graph, a graph with n
vertices is generated such that
every possible edge is included in the graph independently with probability
p
. This is equivalent to a maximum entropy random graph model model with
a constraint on the expected edge count. Setting p = 1/2
generates all graphs on n
vertices with the same probability.
The expected mean degree of the graph is approximately p n
;
set p = k/n
when a mean degree of approximately k
is
desired. More precisely, the expected mean degree is p(n1)
in (undirected or directed) graphs without selfloops,
p(n+1)
in undirected graphs with selfloops, and
p n
in directed graphs with selfloops.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

The probability of the existence of an edge in the graph. 

Logical, whether to generate a directed graph. 

Logical, whether to generate selfloops. 
Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:

Example 9.18. File examples/simple/igraph_erdos_renyi_game_gnp.c
#include <igraph.h> int main(void) { igraph_t graph; igraph_vector_int_t component_sizes; igraph_rng_seed(igraph_rng_default(), 42); /* make program deterministic */ /* Sample a graph from the ErdősRényi G(n,p) model */ igraph_erdos_renyi_game_gnp( &graph, /* n= */ 100, /* p= */ 0.01, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS ); /* Compute the fraction of vertices contained within the largest connected component */ igraph_vector_int_init(&component_sizes, 0); igraph_connected_components(&graph, NULL, &component_sizes, NULL, IGRAPH_STRONG); printf( "Fraction of vertices in giant component: %g\n", ((double) igraph_vector_int_max(&component_sizes)) / igraph_vcount(&graph) ); /* Clean up data structures when no longer needed */ igraph_vector_int_destroy(&component_sizes); igraph_destroy(&graph); return 0; }
igraph_error_t igraph_watts_strogatz_game(igraph_t *graph, igraph_integer_t dim, igraph_integer_t size, igraph_integer_t nei, igraph_real_t p, igraph_bool_t loops, igraph_bool_t multiple);
This function generates networks with the smallworld property
based on a variant of the WattsStrogatz model. The network is obtained
by first creating a periodic undirected lattice, then rewiring both
endpoints of each edge with probability p
, while avoiding the
creation of multiedges.
This process differs from the original model of Watts and Strogatz
(see reference) in that it rewires both endpoints of edges. Thus in
the limit of p=1
, we obtain a G(n,m) random graph with the
same number of vertices and edges as the original lattice. In comparison,
the original WattsStrogatz model only rewires a single endpoint of each edge,
thus the network does not become fully random even for p=1
.
For appropriate choices of p
, both models exhibit the property of
simultaneously having short path lengths and high clustering.
Reference:
Duncan J Watts and Steven H Strogatz: Collective dynamics of “small world” networks, Nature 393, 440442, 1998.
Arguments:

The graph to initialize. 

The dimension of the lattice. 

The size of the lattice along each dimension. 

The size of the neighborhood for each vertex. This is
the same as the 

The rewiring probability. A real number between zero and one (inclusive). 

Logical, whether to generate loop edges. 

Logical, whether to allow multiple edges in the generated graph. 
Returns:
Error code. 
See also:

Time complexity: O(V*d^o+E), V and E are the number of
vertices and edges, d is the average degree, o is the nei
argument.
igraph_error_t igraph_rewire_edges(igraph_t *graph, igraph_real_t prob, igraph_bool_t loops, igraph_bool_t multiple);
This function rewires the edges of a graph with a constant
probability. More precisely each end point of each edge is rewired
to a uniformly randomly chosen vertex with constant probability prob
.
Note that this function modifies the input graph
,
call igraph_copy()
if you want to keep it.
Arguments:

The input graph, this will be rewired, it can be directed or undirected. 

The rewiring probability a constant between zero and one (inclusive). 

Boolean, whether loop edges are allowed in the new graph, or not. 

Boolean, whether multiple edges are allowed in the new graph. 
Returns:
Error code. 
See also:

Time complexity: O(V+E).
igraph_error_t igraph_rewire_directed_edges(igraph_t *graph, igraph_real_t prob, igraph_bool_t loops, igraph_neimode_t mode);
This function rewires either the start or end of directed edges in a graph with a constant probability. Correspondingly, either the indegree sequence or the outdegree sequence of the graph will be preserved.
Note that this function modifies the input graph
,
call igraph_copy()
if you want to keep it.
This function can produce multiple edges between two vertices.
Arguments:

The input graph, this will be rewired, it can be
directed or undirected. If it is undirected or 


The rewiring probability, a constant between zero and one (inclusive). 


Boolean, whether loop edges are allowed in the new graph, or not. 


The endpoints of directed edges to rewire. It is ignored for undirected graphs. Possible values:

Returns:
Error code. 
See also:
Time complexity: O(E).
igraph_error_t igraph_degree_sequence_game(igraph_t *graph, const igraph_vector_int_t *out_deg, const igraph_vector_int_t *in_deg, igraph_degseq_t method);
This function generates random graphs with a prescribed degree sequence. Several sampling methods are available, which respect different constraints (simple graph or multigraphs, connected graphs, etc.), and provide different tradeoffs between performance and unbiased sampling. See Section 2.1 of Horvát and Modes (2021) for an overview of sampling techniques for graphs with fixed degrees.
References:
Fabien Viger, and Matthieu Latapy: Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence, Journal of Complex Networks 4, no. 1, pp. 15–37 (2015). https://doi.org/10.1093/comnet/cnv013.
Szabolcs Horvát, and Carl D Modes: Connectedness Matters: Construction and Exact Random Sampling of Connected Networks, Journal of Physics: Complexity 2, no. 1, pp. 015008 (2021). https://doi.org/10.1088/2632072x/abced5.
Arguments:

Pointer to an uninitialized graph object. 


The degree sequence for an undirected graph (if



It is either a zerolength vector or



The method to generate the graph. Possible values:

Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges
for IGRAPH_DEGSEQ_CONFIGURATION
and IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE
.
The time complexity of the other modes is not known.
See also:

Example 9.19. File examples/simple/igraph_degree_sequence_game.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_t outdeg, indeg; igraph_vector_int_t vec; igraph_bool_t is_simple; /* Set random seed for reproducibility */ igraph_rng_seed(igraph_rng_default(), 42); igraph_vector_int_init_int(&outdeg, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3); igraph_vector_int_init_int(&indeg, 10, 4, 4, 2, 2, 4, 4, 2, 2, 3, 3); igraph_vector_int_init(&vec, 0); /* checking the configuration model, undirected graphs */ igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_CONFIGURATION); if (igraph_is_directed(&g)  igraph_vcount(&g) != 10) { return 1; } if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) { return 2; } igraph_vector_int_print(&vec); igraph_destroy(&g); /* checking the VigerLatapy method, undirected graphs */ igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_VL); if (igraph_is_directed(&g)  igraph_vcount(&g) != 10) { return 3; } if (igraph_is_simple(&g, &is_simple)  !is_simple) { return 4; } if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 0)) { return 5; } igraph_vector_int_print(&vec); igraph_destroy(&g); /* checking the configuration model, directed graphs */ igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_CONFIGURATION); if (!igraph_is_directed(&g)  igraph_vcount(&g) != 10) { return 6; } if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) { return 7; } igraph_vector_int_print(&vec); if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1)) { return 8; } igraph_vector_int_print(&vec); igraph_destroy(&g); /* checking the fast heuristic method, undirected graphs */ igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE); if (igraph_is_directed(&g)  igraph_vcount(&g) != 10) { return 9; } if (igraph_is_simple(&g, &is_simple)  !is_simple) { return 10; } if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) { return 11; } igraph_vector_int_print(&vec); igraph_destroy(&g); /* checking the fast heuristic method, directed graphs */ igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE); if (!igraph_is_directed(&g)  igraph_vcount(&g) != 10) { return 12; } if (igraph_is_simple(&g, &is_simple)  !is_simple) { return 13; } if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1)) { return 14; } igraph_vector_int_print(&vec); if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1)) { return 15; } igraph_vector_int_print(&vec); igraph_destroy(&g); igraph_vector_int_destroy(&vec); igraph_vector_int_destroy(&outdeg); igraph_vector_int_destroy(&indeg); return 0; }
igraph_error_t igraph_k_regular_game(igraph_t *graph, igraph_integer_t no_of_nodes, igraph_integer_t k, igraph_bool_t directed, igraph_bool_t multiple);
This game generates a directed or undirected random graph where the degrees of vertices are equal to a predefined constant k. For undirected graphs, at least one of k and the number of vertices must be even.
Currently, this game simply uses igraph_degree_sequence_game
with
the IGRAPH_DEGSEQ_CONFIGURATION
or the IGRAPH_DEGSEQ_FAST_SIMPLE
method and appropriately constructed degree sequences.
Thefore, it does not sample uniformly: while it can generate all kregular
graphs with the given number of vertices, it does not generate each one with
the same probability.
Arguments:

Pointer to an uninitialized graph object. 

The number of nodes in the generated graph. 

The degree of each vertex in an undirected graph, or the outdegree and indegree of each vertex in a directed graph. 

Whether the generated graph will be directed. 

Whether to allow multiple edges in the generated graph. 
Returns:
Error code:

Time complexity: O(V+E) if multiple
is true, otherwise not known.
igraph_error_t igraph_static_fitness_game(igraph_t *graph, igraph_integer_t no_of_edges, const igraph_vector_t *fitness_out, const igraph_vector_t *fitness_in, igraph_bool_t loops, igraph_bool_t multiple);
This game generates a directed or undirected random graph where the
probability of an edge between vertices i
and j
depends on the fitness
scores of the two vertices involved. For undirected graphs, each vertex
has a single fitness score. For directed graphs, each vertex has an out
and an infitness, and the probability of an edge from i
to j
depends on
the outfitness of vertex i
and the infitness of vertex j
.
The generation process goes as follows. We start from N
disconnected nodes
(where N
is given by the length of the fitness vector). Then we randomly
select two vertices i
and j
, with probabilities proportional to their
fitnesses. (When the generated graph is directed, i
is selected according to
the outfitnesses and j
is selected according to the infitnesses). If the
vertices are not connected yet (or if multiple edges are allowed), we
connect them; otherwise we select a new pair. This is repeated until the
desired number of links are created.
The expected degree (though not the actual degree) of each vertex will be
proportional to its fitness. This is exactly true when selfloops and multiedges
are allowed, and approximately true otherwise. If you need to generate a graph
with an exact degree sequence, consider igraph_degree_sequence_game()
and
igraph_realize_degree_sequence()
instead.
To generate random undirected graphs with a given expected degree sequence, set
fitness_out
(and in the directed case fitness_out
) to the desired expected
degrees, and no_of_edges
to the corresponding edge count, i.e. half the sum of
expected degrees in the undirected case, and the sum of out or indegrees in the
directed case.
This model is similar to the betterknown ChungLu model, implemented in igraph
as igraph_chung_lu_game()
, but with a sharply fixed edge count.
This model is commonly used to generate static scalefree networks. To
achieve this, you have to draw the fitness scores from the desired powerlaw
distribution. Alternatively, you may use igraph_static_power_law_game()
which generates the fitnesses for you with a given exponent.
Reference:
Goh KI, Kahng B, Kim D: Universal behaviour of load distribution in scalefree networks. Phys Rev Lett 87(27):278701, 2001 https://doi.org/10.1103/PhysRevLett.87.278701.
Arguments:

Pointer to an uninitialized graph object. 

A numeric vector containing the fitness of each vertex. For directed graphs, this specifies the outfitness of each vertex. 

If 

The number of edges in the generated graph. 

Whether to allow loop edges in the generated graph. 

Whether to allow multiple edges in the generated graph. 
Returns:
Error code:

See also:
Time complexity: O(V + E log E).
igraph_error_t igraph_static_power_law_game(igraph_t *graph, igraph_integer_t no_of_nodes, igraph_integer_t no_of_edges, igraph_real_t exponent_out, igraph_real_t exponent_in, igraph_bool_t loops, igraph_bool_t multiple, igraph_bool_t finite_size_correction);
This game generates a directed or undirected random graph where the degrees of vertices follow powerlaw distributions with prescribed exponents. For directed graphs, the exponents of the in and outdegree distributions may be specified separately.
The game simply uses igraph_static_fitness_game()
with appropriately
constructed fitness vectors. In particular, the fitness of vertex i
is i^(alpha)
, where alpha = 1/(gamma1)
and gamma
is the exponent given in the arguments.
To remove correlations between in and outdegrees in case of directed
graphs, the infitness vector will be shuffled after it has been set up
and before igraph_static_fitness_game()
is called.
Note that significant finite size effects may be observed for exponents
smaller than 3 in the original formulation of the game. This function
provides an argument that lets you remove the finite size effects by
assuming that the fitness of vertex i
is
(i+i01)^(alpha)
,
where i0
is a constant chosen appropriately to ensure that the maximum
degree is less than the square root of the number of edges times the
average degree; see the paper of Chung and Lu, and Cho et al for more
details.
References:
Goh KI, Kahng B, Kim D: Universal behaviour of load distribution in scalefree networks. Phys Rev Lett 87(27):278701, 2001. https://doi.org/10.1103/PhysRevLett.87.278701
Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125145, 2002. https://doi.org/10.1007/PL00012580
Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scalefree networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009. https://doi.org/10.1103/PhysRevLett.103.135702
Arguments:

Pointer to an uninitialized graph object. 

The number of nodes in the generated graph. 

The number of edges in the generated graph. 

The power law exponent of the degree distribution.
For directed graphs, this specifies the exponent of the
outdegree distribution. It must be greater than or
equal to 2. If you pass 

If negative, the generated graph will be undirected. If greater than or equal to 2, this argument specifies the exponent of the indegree distribution. If nonnegative but less than 2, an error will be generated. 

Whether to allow loop edges in the generated graph. 

Whether to allow multiple edges in the generated graph. 

Whether to use the proposed finite size correction of Cho et al. 
Returns:
Error code:

Time complexity: O(V + E log E).
igraph_error_t igraph_chung_lu_game(igraph_t *graph, const igraph_vector_t *out_weights, const igraph_vector_t *in_weights, igraph_bool_t loops, igraph_chung_lu_t variant);
This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.
The ChungLu model is useful for generating random graphs with fixed expected degrees. This function implements both the original model of Chung and Lu, as well as some additional variants with useful properties.
In the original ChungLu model, each pair of vertices i
and j
is
connected with independent probability p_ij = w_i w_j / S
,
where w_i
is a weight associated with vertex i
and
S = sum_k w_k
is the sum of weights. In the directed variant,
vertices have both outweights, w^out
, and inweights,
w^in
, with equal sums,
S = sum_k w^out_k = sum_k w^in_k
.
The connection probability between i
and j
is
p_ij = w^out_i w^in_j / S
.
This model is commonly used to create random graphs with a fixed expected
degree sequence. The expected degree of vertex i
is approximately equal
to the weight w_i
. Specifically, if the graph is directed and selfloops
are allowed, then the expected out and indegrees are precisely
w^out
and w^in
. If selfloops are disallowed,
then the expected out and indegrees are w^out (S  w^in) / S
and w^in (S  w^out) / S
, respectively. If the graph is
undirected, then the expected degrees with and without selfloops are
w (S + w) / S
and w (S  w) / S
, respectively.
A limitation of the original ChungLu model is that when some of the
weights are large, the formula for p_ij
yields values larger than 1.
Chung and Lu's original paper exludes the use of such weights. When
p_ij > 1
, this function simply issues a warning and creates
a connection between i
and j
. However, in this case the expected degrees
will no longer relate to the weights in the manner stated above. Thus the
original ChungLu model cannot produce certain (large) expected degrees.
The overcome this limitation, this function implements additional variants of
the model, with modified expressions for the connection probability p_ij
between vertices i
and j
. Let q_ij = w_i w_j / S
, or
q_ij = w^out_i w^in_j / S
in the directed case. All model
variants become equivalent in the limit of sparse graphs where q_ij
approaches zero. In the original ChungLu model, selectable by setting
variant
to IGRAPH_CHUNG_LU_ORIGINAL
, p_ij = min(q_ij, 1)
.
The IGRAPH_CHUNG_LU_MAXENT
variant, sometiems referred to a the generalized
random graph, uses p_ij = q_ij / (1 + q_ij)
, and is equivalent
to a maximum entropy model (i.e. exponential random graph model) with
a constraint on expected degrees; see Park and Newman (2004), Section B,
setting exp(Theta_ij) = w_i w_j / S
. This model is also
discussed by Britton, Deijfen and MartinLöf (2006). By virtue of being
a degreeconstrained maximum entropy model, it graphs with the same degree
sequence are produced with the same probability.
A third variant can be requested with IGRAPH_CHUNG_LU_NR
, and uses
p_ij = 1  exp(q_ij)
. This is the underlying simple graph
of a multigraph model introduced by Norros and Reittu (2006).
For a discussion of these three model variants, see Section 16.4 of
Bollobás, Janson, Riordan (2007), as well as Van Der Hofstad (2013).
References:
Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125145 (2002). https://doi.org/10.1007/PL00012580
Miller JC and Hagberg A: Efficient Generation of Networks with Given Expected Degrees (2011). https://doi.org/10.1007/9783642212864_10
Park J and Newman MEJ: Statistical mechanics of networks. Physical Review E 70, 066117 (2004). https://doi.org/10.1103/PhysRevE.70.066117
Britton T, Deijfen M, MartinLöf A: Generating Simple Random Graphs with Prescribed Degree Distribution. J Stat Phys 124, 1377–1397 (2006). https://doi.org/10.1007/s109550069168x
Norros I and Reittu H: On a conditionally Poissonian graph process. Advances in Applied Probability 38, 59–75 (2006). https://doi.org/10.1239/aap/1143936140
Bollobás B, Janson S, Riordan O: The phase transition in inhomogeneous random graphs. Random Struct Algorithms 31, 3–122 (2007). https://doi.org/10.1002/rsa.20168
Van Der Hofstad R: Critical behavior in inhomogeneous random graphs. Random Struct Algorithms 42, 480–508 (2013). https://doi.org/10.1002/rsa.20450
Arguments:

Pointer to an uninitialized graph object. 


A vector of nonnegative vertex weights (or outweights). In sparse graphs these will be approximately equal to the expected (out)degrees. 


A vector of nonnegative inweights, approximately equal
to the expected indegrees in sparse graphs. May be set to 


Whether to allow the creation of selfloops. Since vertex pairs are connected independently, setting this to false is equivalent to simply discarding selfloops from an existing loopy ChungLu graph. 


The model variant to sample from, with different definitions
of the connection probability between vertices

Returns:
Error code. 
See also:

Time complexity: O(E + V), linear in the number of edges.
igraph_error_t igraph_forest_fire_game(igraph_t *graph, igraph_integer_t nodes, igraph_real_t fw_prob, igraph_real_t bw_factor, igraph_integer_t pambs, igraph_bool_t directed);
The forest fire model intends to reproduce the following network characteristics, observed in real networks:
Heavytailed in and outdegree distributions.
Community structure.
Densification powerlaw. The network is densifying in time, according to a powerlaw rule.
Shrinking diameter. The diameter of the network decreases in time.
The network is generated in the following way. One vertex is added at
a time. This vertex connects to (cites) ambs
vertices already
present in the network, chosen uniformly random. Now, for each cited
vertex v
we do the following procedure:
We generate two random numbers, x
and y
, that are
geometrically distributed with means p/(1p)
and
rp(1rp)
. (p
is fw_prob
, r
is
bw_factor
.) The new vertex cites x
outgoing neighbors
and y
incoming neighbors of v
, from those which are
not yet cited by the new vertex. If there are less than x
or
y
such vertices available then we cite all of them.
The same procedure is applied to all the newly cited vertices.
See also: Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. KDD '05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining , 177187, 2005.
Note however, that the version of the model in the published paper is incorrect in the sense that it cannot generate the kind of graphs the authors claim. A corrected version is available from http://cs.stanford.edu/people/jure/pubs/powergrowthtkdd.pdf , our implementation is based on this.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

The forward burning probability. 

The backward burning ratio. The backward burning
probability is calculated as 

The number of ambassador vertices. 

Whether to create a directed graph. 
Returns:
Error code. 
Time complexity: TODO.
igraph_error_t igraph_rewire(igraph_t *graph, igraph_integer_t n, igraph_rewiring_t mode);
This function generates a new graph based on the original one by randomly
"rewriting" edges while preserving the original graph's degree sequence.
The rewiring is done "in place", so no new graph will be allocated. If you
would like to keep the original graph intact, use igraph_copy()
beforehand. All graph attributes will be lost.
The rewiring is performed with degreepreserving edge switches:
Two arbitrary edges are picked uniformly at random, namely
(a, b)
and (c, d)
, then they are replaced
by (a, d)
and (b, c)
if this preserves the
constraints specified by mode
.
Arguments:

The graph object to be rewired. 


Number of rewiring trials to perform. 


The rewiring algorithm to be used. It can be one of the following flags:

Returns:
Error code:

Time complexity: TODO.
igraph_error_t igraph_growing_random_game(igraph_t *graph, igraph_integer_t n, igraph_integer_t m, igraph_bool_t directed, igraph_bool_t citation);
This function simulates a growing random graph. We start out with one vertex. In each step a new vertex is added and a number of new edges are also added. These graphs are known to be different from standard (not growing) random graphs.
Arguments:

Uninitialized graph object. 

The number of vertices in the graph. 

The number of edges to add in a time step (i.e. after adding a vertex). 

Boolean, whether to generate a directed graph. 

Boolean, if 
Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges.
igraph_error_t igraph_callaway_traits_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t types, igraph_integer_t edges_per_step, const igraph_vector_t *type_dist, const igraph_matrix_t *pref_matrix, igraph_bool_t directed, igraph_vector_int_t *node_type_vec);
The different types of vertices prefer to connect other types of vertices with a given probability.
The simulation goes like this: in each discrete time step a new
vertex is added to the graph. The type of this vertex is generated
based on type_dist
. Then two vertices are selected uniformly
randomly from the graph. The probability that they will be
connected depends on the types of these vertices and is taken from
pref_matrix
. Then another two vertices are selected and this is
repeated edges_per_step
times in each time step.
References:
D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman, and S. H. Strogatz, Are randomly grown graphs really random? Phys. Rev. E 64, 041902 (2001). https://doi.org/10.1103/PhysRevE.64.041902
Arguments:

Pointer to an uninitialized graph. 

The number of nodes in the graph. 

Number of node types. 

The number of connections tried in each time step. 

Vector giving the distribution of the vertex types.
If 

Matrix giving the connection probabilities for the vertex types. 

Logical, whether to generate a directed graph. 

An initialized vector or 
Returns:
Error code. 
Added in version 0.2.
Time complexity: O(V*k*log(V)), V is the number of vertices,
k is edges_per_step
.
igraph_error_t igraph_establishment_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t types, igraph_integer_t k, const igraph_vector_t *type_dist, const igraph_matrix_t *pref_matrix, igraph_bool_t directed, igraph_vector_int_t *node_type_vec);
The simulation goes like this: a single vertex is added at each
time step. This new vertex tries to connect to k
vertices in the
graph. The probability that such a connection is realized depends
on the types of the vertices involved.
Arguments:

Pointer to an uninitialized graph. 

The number of vertices in the graph. 

The number of vertex types. 

The number of connections tried in each time step. 

Vector giving the distribution of vertex types.
If 

Matrix giving the connection probabilities for different vertex types. 

Logical, whether to generate a directed graph. 

An initialized vector or 
Returns:
Error code. 
Added in version 0.2.
Time complexity: O(V*k*log(V)), V is the number of vertices
and k is the k
parameter.
igraph_error_t igraph_preference_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t types, const igraph_vector_t *type_dist, igraph_bool_t fixed_sizes, const igraph_matrix_t *pref_matrix, igraph_vector_int_t *node_type_vec, igraph_bool_t directed, igraph_bool_t loops);
This is practically the nongrowing variant of
igraph_establishment_game()
. A given number of vertices are
generated. Every vertex is assigned to a vertex type according to
the given type probabilities. Finally, every
vertex pair is evaluated and an edge is created between them with a
probability depending on the types of the vertices involved.
In other words, this function generates a graph according to a blockmodel. Vertices are divided into groups (or blocks), and the probability the two vertices are connected depends on their groups only.
Arguments:

Pointer to an uninitialized graph. 

The number of vertices in the graph. 

The number of vertex types. 

Vector giving the distribution of vertex types. If


Boolean. If true, then the number of vertices with a
given vertex type is fixed and the 

Matrix giving the connection probabilities for different vertex types. This should be symmetric if the requested graph is undirected. 

A vector where the individual generated vertex types
will be stored. If 

Logical, whether to generate a directed graph. If undirected graphs are requested, only the lower left triangle of the preference matrix is considered. 

Logical, whether loop edges are allowed. 
Returns:
Error code. 
Added in version 0.3.
Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:
igraph_error_t igraph_asymmetric_preference_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t no_out_types, igraph_integer_t no_in_types, const igraph_matrix_t *type_dist_matrix, const igraph_matrix_t *pref_matrix, igraph_vector_int_t *node_type_out_vec, igraph_vector_int_t *node_type_in_vec, igraph_bool_t loops);
This is the asymmetric variant of igraph_preference_game()
.
A given number of vertices are generated. Every vertex is assigned to an
"outgoing" and an "incoming " vertex type according to the given joint
type probabilities. Finally, every vertex pair is evaluated and a
directed edge is created between them with a probability depending on the
"outgoing" type of the source vertex and the "incoming" type of the target
vertex.
Arguments:

Pointer to an uninitialized graph. 

The number of vertices in the graph. 

The number of vertex outtypes. 

The number of vertex intypes. 

Matrix of size 

Matrix of size 

A vector where the individual generated "outgoing"
vertex types will be stored. If 

A vector where the individual generated "incoming"
vertex types will be stored. If 

Logical, whether loop edges are allowed. 
Returns:
Error code. 
Added in version 0.3.
Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
See also:
igraph_error_t igraph_recent_degree_game(igraph_t *graph, igraph_integer_t nodes, igraph_real_t power, igraph_integer_t time_window, igraph_integer_t m, const igraph_vector_int_t *outseq, igraph_bool_t outpref, igraph_real_t zero_appeal, igraph_bool_t directed);
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph, this is the same as the number of time steps. 

The exponent, the probability that a node gains a
new edge is proportional to the number of edges it has
gained recently (in the last 

Integer constant, the size of the time window to use to count the number of recent edges. 

Integer constant, the number of edges to add per time
step if the 

The number of edges to add in each time step. This
argument is ignored if it is a null pointer or a zero length
vector. In this case the constant 

Logical constant, if true the edges originated by a vertex also count as recent incident edges. For most applications it is reasonable to set it to false. 

Constant giving the attractiveness of the vertices which haven't gained any edge recently. 

Logical constant, whether to generate a directed graph. 
Returns:
Error code. 
Time complexity: O(V*log(V)+E), V is the number of vertices, E is the number of edges in the graph.
igraph_error_t igraph_barabasi_aging_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t m, const igraph_vector_int_t *outseq, igraph_bool_t outpref, igraph_real_t pa_exp, igraph_real_t aging_exp, igraph_integer_t aging_bins, igraph_real_t zero_deg_appeal, igraph_real_t zero_age_appeal, igraph_real_t deg_coef, igraph_real_t age_coef, igraph_bool_t directed);
This game starts with one vertex (if nodes
> 0). In each step
a new node is added, and it is connected to m
existing nodes.
Existing nodes to connect to are chosen with probability dependent
on their (in)degree (k
) and age (l
).
The degreedependent part is
deg_coef * k^pa_exp + zero_deg_appeal
,
while the agedependent part is
age_coef * l^aging_exp + zero_age_appeal
,
which are multiplied to obtain the final weight.
The age l
is based on the number of vertices in the
network and the aging_bins
argument: the age of a node
is incremented by 1 after each
floor(nodes / aging_bins) + 1
time steps.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

The number of edges to add in each time step.
Ignored if 

The number of edges to add in each time step. If it
is 

Logical constant, whether the edges initiated by a vertex contribute to the probability to gain a new edge. 

The exponent of the preferential attachment, a small positive number usually, the value 1 yields the classic linear preferential attachment. 

The exponent of the aging, this is a negative number usually. 

Integer constant, the number of age bins to use. 

The degree dependent part of the attractiveness of the zero degree vertices. 

The age dependent part of the attractiveness of the vertices of age zero. This parameter is usually zero. 

The coefficient for the degree. 

The coefficient for the age. 

Logical constant, whether to generate a directed graph. 
Returns:
Error code. 
Time complexity: O((V+V/aging_bins)*log(V)+E). V is the number of vertices, E the number of edges.
igraph_error_t igraph_recent_degree_aging_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t m, const igraph_vector_int_t *outseq, igraph_bool_t outpref, igraph_real_t pa_exp, igraph_real_t aging_exp, igraph_integer_t aging_bins, igraph_integer_t time_window, igraph_real_t zero_appeal, igraph_bool_t directed);
This game is very similar to igraph_barabasi_aging_game()
,
except that instead of the total number of incident edges the
number of edges gained in the last time_window
time steps are
counted.
The degree dependent part of the attractiveness is
given by k to the power of pa_exp
plus zero_appeal
; the age
dependent part is l to the power to aging_exp
.
k is the number of edges gained in the last time_window
time
steps, l is the age of the vertex.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the graph. 

The number of edges to add in each time step. If the 

Vector giving the number of edges to add in each time
step. If it is a null pointer or a zerolength vector then
it is ignored and the 

Logical constant, if true the edges initiated by a vertex are also counted. Normally it is false. 

The exponent for the preferential attachment. 

The exponent for the aging, normally it is negative: old vertices gain edges with less probability. 

Integer constant, the number of age bins to use. 

The time window to use to count the number of incident edges for the vertices. 

The degree dependent part of the attractiveness for zero degree vertices. 

Logical constant, whether to create a directed graph. 
Returns:
Error code. 
Time complexity: O((V+V/aging_bins)*log(V)+E). V is the number of vertices, E the number of edges.
igraph_error_t igraph_lastcit_game(igraph_t *graph, igraph_integer_t nodes, igraph_integer_t edges_per_node, igraph_integer_t agebins, const igraph_vector_t *preference, igraph_bool_t directed);
This is a quite special stochastic graph generator, it models an
evolving graph. In each time step a single vertex is added to the
network and it cites a number of other vertices (as specified by
the edges_per_step
argument). The cited vertices are selected
based on the last time they were cited. Time is measured by the
addition of vertices and it is binned into agebins
bins.
So if the current time step is t
and the last citation to a
given i
vertex was made in time step t0
, then \c
(tt0)/binwidth is calculated where binwidth is nodes
/agebins+1,
in the last expression '/' denotes integer division, so the
fraction part is omitted.
The preference
argument specifies the preferences for the
citation lags, i.e. its first elements contains the attractivity
of the very recently cited vertices, etc. The last element is
special, it contains the attractivity of the vertices which were
never cited. This element should be bigger than zero.
Note that this function generates networks with multiple edges if
edges_per_step
is bigger than one, call igraph_simplify()
on the result to get rid of these edges.
Arguments:

Pointer to an uninitialized graph object, the result will be stored here. 

The number of vertices in the network. 

The number of edges to add in each time step. 

The number of age bins to use. 

Pointer to an initialized vector of length


Logical constant, whether to create directed networks. 
Returns:
Error code. 
See also:
Time complexity: O(V*a+E*logV), V is the number of vertices,
E is the total number of edges, a is the agebins
parameter.
igraph_error_t igraph_cited_type_game(igraph_t *graph, igraph_integer_t nodes, const igraph_vector_int_t *types, const igraph_vector_t *pref, igraph_integer_t edges_per_step, igraph_bool_t directed);
Function to create a network based on some vertex categories. This
function creates a citation network: in each step a single vertex
and edges_per_step
citing edges are added. Nodes with
different categories may have different probabilities to get
cited, as given by the pref
vector.
Note that this function might generate networks with multiple edges
if edges_per_step
is greater than one. You might want to call
igraph_simplify()
on the result to remove multiple edges.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the network. 

Numeric vector giving the categories of the vertices,
so it should contain 

The attractivity of the different vertex categories in
a vector. Its length should be the maximum element in 

Integer constant, the number of edges to add in each time step. 

Logical constant, whether to create a directed network. 
Returns:
Error code. 
See also:

Time complexity: O((V+E)logV), V and E are number of vertices and edges, respectively.
igraph_error_t igraph_citing_cited_type_game(igraph_t *graph, igraph_integer_t nodes, const igraph_vector_int_t *types, const igraph_matrix_t *pref, igraph_integer_t edges_per_step, igraph_bool_t directed);
This game is similar to igraph_cited_type_game()
but here the
category of the citing vertex is also considered.
An evolving citation network is modeled here, a single vertex and
its edges_per_step
citation are added in each time step. The
odds the a given vertex is cited by the new vertex depends on the
category of both the citing and the cited vertex and is given in
the pref
matrix. The categories of the citing vertex correspond
to the rows, the categories of the cited vertex to the columns of
this matrix. I.e. the element in row i
and column j
gives the
probability that a j
vertex is cited, if the category of the
citing vertex is i
.
Note that this function might generate networks with multiple edges
if edges_per_step
is greater than one. You might want to call
igraph_simplify()
on the result to remove multiple edges.
Arguments:

Pointer to an uninitialized graph object. 

The number of vertices in the network. 

A numeric vector of length 

The preference matrix, a square matrix is required,
both the number of rows and columns should be the maximum
element in 

Integer constant, the number of edges to add in each time step. 

Logical constant, whether to create a directed network. 
Returns:
Error code. 
Time complexity: O((V+E)logV), V and E are number of vertices and edges, respectively.
igraph_error_t igraph_sbm_game(igraph_t *graph, igraph_integer_t n, const igraph_matrix_t *pref_matrix, const igraph_vector_int_t *block_sizes, igraph_bool_t directed, igraph_bool_t loops);
This function samples graphs from a stochastic block
model by (doing the equivalent of) Bernoulli
trials for each potential edge with the probabilities
given by the Bernoulli rate matrix, pref_matrix
.
See Faust, K., & Wasserman, S. (1992a). Blockmodels:
Interpretation and evaluation. Social Networks, 14, 5–61.
The order of the vertex IDs in the generated graph corresponds to
the block_sizes
argument.
Arguments:

The output graph. This should be a pointer to an uninitialized graph. 

Number of vertices. 

The matrix giving the Bernoulli rates. This is a KxK matrix, where K is the number of groups. The probability of creating an edge between vertices from groups i and j is given by element (i,j). 

An integer vector giving the number of vertices in each group. 

Boolean, whether to create a directed graph. If
this argument is false, then 

Boolean, whether to create selfloops. 
Returns:
Error code. 
Time complexity: O(V+E+K^2), where V is the number of vertices, E is the number of edges, and K is the number of groups.
See also:

igraph_error_t igraph_hsbm_game(igraph_t *graph, igraph_integer_t n, igraph_integer_t m, const igraph_vector_t *rho, const igraph_matrix_t *C, igraph_real_t p);
The function generates a random graph according to the hierarchical stochastic block model.
Arguments:

The generated graph is stored here. 

The number of vertices in the graph. 

The number of vertices per block. n/m must be integer. 

The fraction of vertices per cluster, within a block. Must sum up to 1, and rho * m must be integer for all elements of rho. 

A square, symmetric numeric matrix, the Bernoulli rates for
the clusters within a block. Its size must mach the size of the


The Bernoulli rate of connections between vertices in different blocks. 
Returns:
Error code. 
See also:

igraph_error_t igraph_hsbm_list_game(igraph_t *graph, igraph_integer_t n, const igraph_vector_int_t *mlist, const igraph_vector_list_t *rholist, const igraph_matrix_list_t *Clist, igraph_real_t p);
The function generates a random graph according to the hierarchical stochastic block model.
Arguments:

The generated graph is stored here. 

The number of vertices in the graph. 

An integer vector of block sizes. 

A list of rho vectors ( 

A list of square matrices ( 

The Bernoulli rate of connections between vertices in different blocks. 
Returns:
Error code. 
See also:

igraph_error_t igraph_dot_product_game(igraph_t *graph, const igraph_matrix_t *vecs, igraph_bool_t directed);
In this model, each vertex is represented by a latent position vector. Probability of an edge between two vertices are given by the dot product of their latent position vectors.
See also Christine Leigh Myers Nickel: Random dot product graphs, a model for social networks. Dissertation, Johns Hopkins University, Maryland, USA, 2006.
Arguments:

The output graph is stored here. 

A matrix in which each latent position vector is a column. The dot product of the latent position vectors should be in the [0,1] interval, otherwise a warning is given. For negative dot products, no edges are added; dot products that are larger than one always add an edge. 

Should the generated graph be directed? 
Returns:
Error code. 
Time complexity: O(n*n*m), where n is the number of vertices, and m is the length of the latent vectors.
See also:

igraph_error_t igraph_tree_game(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, igraph_random_tree_t method);
This function samples uniformly from the set of labelled trees, i.e. it generates each labelled tree with the same probability.
Note that for n=0
, the null graph is returned,
which is not considered to be a tree by igraph_is_tree()
.
Arguments:

Pointer to an uninitialized graph object. 


The number of nodes in the tree. 


Whether to create a directed tree. The edges are oriented away from the root. 


The algorithm to use to generate the tree. Possible values:

Returns:
Error code:

See also:
igraph_error_t igraph_correlated_game(const igraph_t *old_graph, igraph_t *new_graph, igraph_real_t corr, igraph_real_t p, const igraph_vector_int_t *permutation);
Sample a new graph by perturbing the adjacency matrix of a given simple graph and shuffling its vertices.
Arguments:

The original graph, it must be simple. 

The new graph will be stored here. 

A scalar in the unit interval [0,1], the target Pearson correlation between the adjacency matrices of the original and the generated graph (the adjacency matrix being used as a vector). 

A numeric scalar, the probability of an edge between two
vertices, it must in the open (0,1) interval. Typically,
the density of 

A permutation to apply to the vertices of the generated graph. It can also be a null pointer, in which case the vertices will not be permuted. 
Returns:
Error code 
See also:

igraph_error_t igraph_correlated_pair_game(igraph_t *graph1, igraph_t *graph2, igraph_integer_t n, igraph_real_t corr, igraph_real_t p, igraph_bool_t directed, const igraph_vector_int_t *permutation);
Sample two random graphs, with given correlation.
Arguments:

The first graph will be stored here. 

The second graph will be stored here. 

The number of vertices in both graphs. 

A scalar in the unit interval, the target Pearson correlation between the adjacency matrices of the original the generated graph (the adjacency matrix being used as a vector). 

A numeric scalar, the probability of an edge between two vertices, it must in the open (0,1) interval. 

Whether to generate directed graphs. 

A permutation to apply to the vertices of the second graph. It can also be a null pointer, in which case the vertices will not be permuted. 
Returns:
Error code 
See also:

igraph_error_t igraph_simple_interconnected_islands_game( igraph_t *graph, igraph_integer_t islands_n, igraph_integer_t islands_size, igraph_real_t islands_pin, igraph_integer_t n_inter);
All islands are of the same size. Within an island, each edge is generated with the same probability. A fixed number of additional edges are then generated for each unordered pair of islands to connect them. The generated graph is guaranteed to be simple.
Arguments:

Pointer to an uninitialized graph object. 

The number of islands in the graph. 

The size of islands in the graph. 

The probability to create each possible edge within islands. 

The number of edges to create between two islands. It may be
larger than 
Returns:
Error code:

Time complexity: O(V+E), the number of vertices plus the number of edges in the graph.
← Chapter 8. Random numbers  Chapter 10. Games on graphs → 