abdelrahman/agent_compositor_test
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
agent_compositor_test/references/igraph-1.0.1/doc/html/igraph-Games.html
T
Abdelrahman Said a11edf0c53 Add graph references
2026-06-28 13:49:01 +01:00

5332 lines
224 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters
This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Chapter 12. Stochastic graph generators ("games")</title>
<meta name="generator" content="DocBook XSL Stylesheets Vsnapshot">
<link rel="home" href="index.html" title="igraph Reference Manual">
<link rel="up" href="index.html" title="igraph Reference Manual">
<link rel="prev" href="igraph-Generators.html" title="Chapter 11. Deterministic graph generators">
<link rel="next" href="igraph-Bipartite.html" title="Chapter 13. Bipartite, i.e. two-mode graphs">
<script type="text/javascript" src="toggle.js"></script><link rel="stylesheet" href="style.css" type="text/css">
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css" type="text/css">
<link rel="chapter" href="igraph-Introduction.html" title="Chapter 1. Introduction">
<link rel="chapter" href="igraph-Installation.html" title="Chapter 2. Installation">
<link rel="chapter" href="igraph-Tutorial.html" title="Chapter 3. Tutorial">
<link rel="chapter" href="igraph-Basic.html" title="Chapter 4. Basic data types and interface">
<link rel="chapter" href="igraph-Error.html" title="Chapter 5. Error handling">
<link rel="chapter" href="igraph-Memory.html" title="Chapter 6. Memory (de)allocation">
<link rel="chapter" href="igraph-Data-structures.html" title="Chapter 7. Data structure library: vector, matrix, other data types">
<link rel="chapter" href="igraph-Random.html" title="Chapter 8. Random numbers">
<link rel="chapter" href="igraph-Iterators.html" title="Chapter 9. Vertex and edge selectors and sequences, iterators">
<link rel="chapter" href="igraph-Attributes.html" title="Chapter 10. Graph, vertex and edge attributes">
<link rel="chapter" href="igraph-Generators.html" title="Chapter 11. Deterministic graph generators">
<link rel="chapter" href="igraph-Games.html" title='Chapter 12. Stochastic graph generators ("games")'>
<link rel="chapter" href="igraph-Bipartite.html" title="Chapter 13. Bipartite, i.e. two-mode graphs">
<link rel="chapter" href="igraph-Spatial.html" title="Chapter 14. Spatial graphs">
<link rel="chapter" href="igraph-Operators.html" title="Chapter 15. Graph operators">
<link rel="chapter" href="igraph-Visitors.html" title="Chapter 16. Graph visitors">
<link rel="chapter" href="igraph-Structural.html" title="Chapter 17. Structural properties of graphs">
<link rel="chapter" href="igraph-Cycles.html" title="Chapter 18. Graph cycles">
<link rel="chapter" href="igraph-Cliques.html" title="Chapter 19. Cliques and independent vertex sets">
<link rel="chapter" href="igraph-Motifs.html" title="Chapter 20. Graph motifs, dyad census and triad census">
<link rel="chapter" href="igraph-Isomorphism.html" title="Chapter 21. Graph isomorphism">
<link rel="chapter" href="igraph-Coloring.html" title="Chapter 22. Graph coloring">
<link rel="chapter" href="igraph-Flows.html" title="Chapter 23. Maximum flows, minimum cuts and related measures">
<link rel="chapter" href="igraph-Separators.html" title="Chapter 24. Vertex separators">
<link rel="chapter" href="igraph-Community.html" title="Chapter 25. Detecting community structure">
<link rel="chapter" href="igraph-Graphlets.html" title="Chapter 26. Graphlets">
<link rel="chapter" href="igraph-HRG.html" title="Chapter 27. Hierarchical random graphs">
<link rel="chapter" href="igraph-Embedding.html" title="Chapter 28. Embedding of graphs">
<link rel="chapter" href="igraph-Layout.html" title="Chapter 29. Generating layouts for graph drawing">
<link rel="chapter" href="igraph-Processes.html" title="Chapter 30. Processes on graphs">
<link rel="chapter" href="igraph-Foreign.html" title="Chapter 31. Reading and writing graphs from and to files">
<link rel="chapter" href="igraph-Linalg.html" title="Chapter 32. Using BLAS, LAPACK and ARPACK for igraph matrices and graphs">
<link rel="chapter" href="igraph-Nongraph.html" title="Chapter 33. Non-graph related functions">
<link rel="chapter" href="igraph-Advanced.html" title="Chapter 34. Advanced igraph programming">
<link rel="chapter" href="igraph-Glossary.html" title="Chapter 35. Glossary">
<link rel="chapter" href="igraph-Licenses.html" title="Chapter 36. Licenses for igraph and this manual">
<link rel="index" href="ix01.html" title="Index">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<div class="navigation-header mb-4" width="100%" summary="Navigation header"><div class="btn-group">
<a accesskey="p" class="btn btn-light" href="igraph-Generators.html"><i class="fa fa-chevron-left"></i>
Previous
</a><a accesskey="h" class="btn btn-light" href="index.html"><i class="fa fa-home"></i>
Home
</a><a accesskey="n" class="btn btn-light" href="igraph-Bipartite.html"><i class="fa fa-chevron-right"></i>
Next
</a>
</div></div>
<div class="chapter">
<div class="titlepage"><div><div><h1 class="title">
<a name="igraph-Games"></a>Chapter 12. Stochastic graph generators ("games")</h1></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#erdos-renyi-games">1. The Erdős-Rényi and related models</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#preferential-attachment-games">2. Preferential attachment and related models</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#growing-random-games">3. Growing random graph models</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#degree-constrained-games">4. Degree-constrained models</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#edge-rewiring-games">5. Edge rewiring models</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#other-random-games">6. Other random graphs</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#generator-types-and-constants">7. Common types and constants</a></span></dt>
</dl></div>
<p>"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 real-world
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.)</p>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="erdos-renyi-games"></a>1. The Erdős-Rényi and related models</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#igraph_erdos_renyi_game_gnm">1.1. <code class="function">igraph_erdos_renyi_game_gnm</code> — Generates a random (Erdős-Rényi) graph with a fixed number of edges.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_erdos_renyi_game_gnp">1.2. <code class="function">igraph_erdos_renyi_game_gnp</code> — Generates a random (Erdős-Rényi) graph with fixed edge probabilities.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_iea_game">1.3. <code class="function">igraph_iea_game</code> — Generates a random multigraph through independent edge assignment.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_sbm_game">1.4. <code class="function">igraph_sbm_game</code> — Sample from a stochastic block model.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_hsbm_game">1.5. <code class="function">igraph_hsbm_game</code> — Hierarchical stochastic block model.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_hsbm_list_game">1.6. <code class="function">igraph_hsbm_list_game</code> — Hierarchical stochastic block model, more general version.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_preference_game">1.7. <code class="function">igraph_preference_game</code> — Generates a graph with vertex types and connection preferences.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_asymmetric_preference_game">1.8. <code class="function">igraph_asymmetric_preference_game</code> — Generates a graph with asymmetric vertex types and connection preferences.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_correlated_game">1.9. <code class="function">igraph_correlated_game</code> — Generates a random graph correlated to an existing graph.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_correlated_pair_game">1.10. <code class="function">igraph_correlated_pair_game</code> — Generates pairs of correlated random graphs.</a></span></dt>
</dl></div>
<p>
There are two classic random graph models referred to as the Erdős-Rényi
random graph, or sometimes simply <span class="emphasis"><em>the</em></span> random graph. Both fix the vertex
count n, but while the G(n,m) model prescribes precisely m edges, the G(n,p)
model connects all vertex pairs independently with probability p. While
these models look superficially different, when n is large they behave in
a similar manner. G(n,m) graphs have a density of exactly
<code class="literal">p = m / m_max</code>, while G(n,p) graphs have <code class="literal">m = p m_max</code>
edges on <span class="emphasis"><em>average,</em></span> where <code class="constant">m_max</code> is the number of vertex pairs. Indeed,
these two models turns out to be two sides of the same coin: both can be
understood as maximum entropy models with a constraint on the number of
edges. The G(n,m) is obtained from a sharp constraint, while G(n,p) from
an average constraint (soft constraint).
</p>
<p>
The maximum entropy framework allows for rigorous generalizations of these
models to various scenarios, of which igraph supports many, such as models
defined over directed graphs, bipartite graphs, multigraphs, or even over
edge-labelled graphs. Constraining edge counts between various subsets of
vertices yields further families of related models, such as
<a class="link" href="igraph-Games.html#igraph_sbm_game" title="1.4. igraph_sbm_game — Sample from a stochastic block model."><code class="function">igraph_sbm_game()</code></a> (given connection probabilities between categories)
or <a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game()</code></a> (given incident edge counts, i.e.
degrees, for each vertex).
</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_erdos_renyi_game_gnm"></a>1.1. <code class="function">igraph_erdos_renyi_game_gnm</code> — Generates a random (Erdős-Rényi) graph with a fixed number of edges.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.4.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_erdos_renyi_game_gnm(
igraph_t *graph,
igraph_int_t n, igraph_int_t m,
igraph_bool_t directed,
igraph_edge_type_sw_t allowed_edge_types,
igraph_bool_t edge_labeled);
</pre></div>
<p>
</p>
<p>
In the <code class="literal">G(n, m)</code> Erdős-Rényi model, a graph with <em class="parameter"><code>n</code></em> vertices
and <em class="parameter"><code>m</code></em> edges is generated uniformly at random.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of edges in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate a directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are generated. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>edge_labeled</code></em>:</span></p></td>
<td><p>
If true, the sampling is done uniformly from the set
of ordered edge lists. See <a class="link" href="igraph-Games.html#igraph_iea_game" title="1.3. igraph_iea_game — Generates a random multigraph through independent edge assignment."><code class="function">igraph_iea_game()</code></a> for more information.
Set this to <code class="constant">false</code> to select the classic Erdős-Rényi model.
The constants <code class="constant">IGRAPH_EDGE_UNLABELED</code> and <code class="constant">IGRAPH_EDGE_LABELED</code>
may be used instead of <code class="constant">false</code> and <code class="constant">true</code> for better readability.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid <em class="parameter"><code>n</code></em> or <em class="parameter"><code>m</code></em> parameter.
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges in the graph.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnp" title="1.2. igraph_erdos_renyi_game_gnp — Generates a random (Erdős-Rényi) graph with fixed edge probabilities."><code class="function">igraph_erdos_renyi_game_gnp()</code></a> to sample from the related
<code class="literal">G(n, p)</code> model, which constrains the <span class="emphasis"><em>expected</em></span> edge count;
<a class="link" href="igraph-Games.html#igraph_iea_game" title="1.3. igraph_iea_game — Generates a random multigraph through independent edge assignment."><code class="function">igraph_iea_game()</code></a> to generate multigraph by assigning edges to vertex
pairs uniformly and independently;
<a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game()</code></a> to constrain the degree sequence;
<a class="link" href="igraph-Bipartite.html#igraph_bipartite_game_gnm" title="2.3. igraph_bipartite_game_gnm — Generate a random bipartite graph with a fixed number of edges."><code class="function">igraph_bipartite_game_gnm()</code></a> for the bipartite version of this model;
<a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model."><code class="function">igraph_barabasi_game()</code></a> and <a class="link" href="igraph-Games.html#igraph_growing_random_game" title="3.1. igraph_growing_random_game — Generates a growing random graph."><code class="function">igraph_growing_random_game()</code></a> for other
commonly used random graph models.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<div class="hideshow" onClick="toggle(this, event)">
<div class="example">
<a name="id-1.13.3.4.10.1"></a><p class="title"><b>Example 12.1.  File <code class="code">examples/simple/igraph_erdos_renyi_game_gnm.c</code></b></p>
<div class="example-contents">
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> &lt;igraph.h&gt;
int <span class="strong"><strong>main</strong></span>(void) {
igraph_t graph;
igraph_vector_int_t component_sizes;
<span class="emphasis"><em>/* Initialize the library. */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_seed" title="3.3. igraph_rng_seed — Seeds a random number generator.">igraph_rng_seed</a></strong></span>(<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_default" title="2.1. igraph_rng_default — Query the default random number generator.">igraph_rng_default</a></strong></span>(), 42); <span class="emphasis"><em>/* make program deterministic */</em></span>
<span class="emphasis"><em>/* Sample a graph from the Erdős-Rényi G(n,m) model */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnm" title="1.1. igraph_erdos_renyi_game_gnm — Generates a random (Erdős-Rényi) graph with a fixed number of edges.">igraph_erdos_renyi_game_gnm</a></strong></span>(
&amp;graph, <span class="emphasis"><em>/* n= */</em></span> 100, <span class="emphasis"><em>/* m= */</em></span> 100,
IGRAPH_UNDIRECTED, IGRAPH_SIMPLE_SW, IGRAPH_EDGE_UNLABELED);
<span class="emphasis"><em>/* Compute the fraction of vertices contained within the largest connected component */</em></span>
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&amp;component_sizes, 0);
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_connected_components" title="8.2. igraph_connected_components — Calculates the (weakly or strongly) connected components in a graph.">igraph_connected_components</a></strong></span>(&amp;graph, NULL, &amp;component_sizes, NULL, IGRAPH_STRONG);
<span class="strong"><strong>printf</strong></span>(
"Fraction of vertices in giant component: %g\n",
((double) <span class="strong"><strong>igraph_vector_int_max</strong></span>(&amp;component_sizes)) / <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;graph)
);
<span class="emphasis"><em>/* Clean up data structures when no longer needed */</em></span>
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;component_sizes);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;graph);
<span class="strong"><strong>return</strong></span> 0;
}
</pre>
<p></p>
</div>
</div>
<br class="example-break">
</div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_erdos_renyi_game_gnp"></a>1.2. <code class="function">igraph_erdos_renyi_game_gnp</code> — Generates a random (Erdős-Rényi) graph with fixed edge probabilities.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.5.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_erdos_renyi_game_gnp(
igraph_t *graph,
igraph_int_t n, igraph_real_t p,
igraph_bool_t directed,
igraph_edge_type_sw_t allowed_edge_types,
igraph_bool_t edge_labeled);
</pre></div>
<p>
</p>
<p>
In the <code class="literal">G(n, p)</code> Erdős-Rényi model, also known as the Gilbert model,
or Bernoulli random graph, a graph with <em class="parameter"><code>n</code></em> vertices is generated such that
every possible edge is included in the graph independently with probability
<em class="parameter"><code>p</code></em>. This is equivalent to a maximum entropy random graph model model with
a constraint on the <span class="emphasis"><em>expected</em></span> edge count. The maximum entropy view allows
for extending the model to multigraphs, as discussed by Park and Newman (2004),
section III.D. In this case, <em class="parameter"><code>p</code></em> is interpreted as the expected number of
edges between any vertex pair.
</p>
<p>
Setting <code class="literal">p = 1/2</code> and <code class="literal">multiple = false</code> generates all
graphs without multi-edges on <em class="parameter"><code>n</code></em> vertices with the same probability.
</p>
<p>
For both simple and multigraphs, the expected mean degree of the graph is
approximately <code class="literal">p n</code>; set <code class="literal">p = k/n</code> when a mean degree
of approximately <code class="constant">k</code> is desired. More precisely, the expected mean degree is
<code class="literal">p(n-1)</code> in (undirected or directed) graphs without self-loops,
<code class="literal">p(n+1)</code> in undirected graphs with self-loops, and
<code class="literal">p n</code> in directed graphs with self-loops.
</p>
<p>
When generating multigraphs, the distribution of the edge multiplicities is
geometric, i.e. the probability of finding <code class="constant">m</code> edges between two vertices
is <code class="literal">q (1-q)^m</code>, where <code class="literal">q = 1 / (1+p)</code>.
</p>
<p>
This function uses the sequential geometric sampling technique described in
Batagelj and Brandes (2005), with a modification to handle multigraphs.
</p>
<p>
References:
</p>
<p>
J. Park and M. E. J. Newman: "Statistical Mechanics of Networks".
Phys. Rev. E 70, 066117 (2004).
<a class="ulink" href="https://doi.org/10.1103/PhysRevE.70.066117" target="_top">https://doi.org/10.1103/PhysRevE.70.066117</a>
</p>
<p>
V. Batagelj and U. Brandes: "Efficient Generation of Large Random Networks".
Phys. Rev. E 71, 036113 (2005).
<a class="ulink" href="https://doi.org/10.1103/PhysRevE.71.036113" target="_top">https://doi.org/10.1103/PhysRevE.71.036113</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>p</code></em>:</span></p></td>
<td><p>
The expected number of edges between any vertex pair.
When multi-edges are disallowed, this is equivalent to the probability
of having a connection between any two vertices.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate a directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are generated. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>edge_labeled</code></em>:</span></p></td>
<td><p>
If true, the model is defined over the set of ordered
edge lists, i.e. over the set of edge-labeled graphs. Set it to
<code class="constant">false</code> to select the classic Erdős-Rényi model.
The constants <code class="constant">IGRAPH_EDGE_UNLABELED</code> and <code class="constant">IGRAPH_EDGE_LABELED</code>
may be used instead of <code class="constant">false</code> and <code class="constant">true</code> for better readability.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid <em class="parameter"><code>n</code></em> or <em class="parameter"><code>p</code></em> parameter.
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges in the graph.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnm" title="1.1. igraph_erdos_renyi_game_gnm — Generates a random (Erdős-Rényi) graph with a fixed number of edges."><code class="function">igraph_erdos_renyi_game_gnm()</code></a> to generate random graphs with
a sharply fixed edge count; <a class="link" href="igraph-Games.html#igraph_chung_lu_game" title="4.4. igraph_chung_lu_game — Samples graphs from the Chung-Lu model."><code class="function">igraph_chung_lu_game()</code></a> and
<a class="link" href="igraph-Games.html#igraph_static_fitness_game" title="4.5. igraph_static_fitness_game — Non-growing random graph with edge probabilities proportional to node fitness scores."><code class="function">igraph_static_fitness_game()</code></a> to generate random graphs with a
fixed expected degree sequence; <a class="link" href="igraph-Bipartite.html#igraph_bipartite_game_gnm" title="2.3. igraph_bipartite_game_gnm — Generate a random bipartite graph with a fixed number of edges."><code class="function">igraph_bipartite_game_gnm()</code></a> for the
bipartite version of this model; <a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model."><code class="function">igraph_barabasi_game()</code></a> and
<a class="link" href="igraph-Games.html#igraph_growing_random_game" title="3.1. igraph_growing_random_game — Generates a growing random graph."><code class="function">igraph_growing_random_game()</code></a> for other commonly used random graph models.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<div class="hideshow" onClick="toggle(this, event)">
<div class="example">
<a name="id-1.13.3.5.17.1"></a><p class="title"><b>Example 12.2.  File <code class="code">examples/simple/igraph_erdos_renyi_game_gnp.c</code></b></p>
<div class="example-contents">
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> &lt;igraph.h&gt;
int <span class="strong"><strong>main</strong></span>(void) {
igraph_t graph;
igraph_vector_int_t component_sizes;
<span class="emphasis"><em>/* Initialize the library. */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_seed" title="3.3. igraph_rng_seed — Seeds a random number generator.">igraph_rng_seed</a></strong></span>(<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_default" title="2.1. igraph_rng_default — Query the default random number generator.">igraph_rng_default</a></strong></span>(), 42); <span class="emphasis"><em>/* make program deterministic */</em></span>
<span class="emphasis"><em>/* Sample a graph from the Erdős-Rényi G(n,p) model */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnp" title="1.2. igraph_erdos_renyi_game_gnp — Generates a random (Erdős-Rényi) graph with fixed edge probabilities.">igraph_erdos_renyi_game_gnp</a></strong></span>(
&amp;graph, <span class="emphasis"><em>/* n= */</em></span> 100, <span class="emphasis"><em>/* p= */</em></span> 0.01,
IGRAPH_UNDIRECTED, IGRAPH_SIMPLE_SW, IGRAPH_EDGE_UNLABELED);
<span class="emphasis"><em>/* Compute the fraction of vertices contained within the largest connected component */</em></span>
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&amp;component_sizes, 0);
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_connected_components" title="8.2. igraph_connected_components — Calculates the (weakly or strongly) connected components in a graph.">igraph_connected_components</a></strong></span>(&amp;graph, NULL, &amp;component_sizes, NULL, IGRAPH_STRONG);
<span class="strong"><strong>printf</strong></span>(
"Fraction of vertices in giant component: %g\n",
((double) <span class="strong"><strong>igraph_vector_int_max</strong></span>(&amp;component_sizes)) / <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;graph)
);
<span class="emphasis"><em>/* Clean up data structures when no longer needed */</em></span>
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;component_sizes);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;graph);
<span class="strong"><strong>return</strong></span> 0;
}
</pre>
<p></p>
</div>
</div>
<br class="example-break">
</div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_iea_game"></a>1.3. <code class="function">igraph_iea_game</code> — Generates a random multigraph through independent edge assignment.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.6.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_iea_game(
igraph_t *graph,
igraph_int_t n, igraph_int_t m,
igraph_bool_t directed, igraph_bool_t loops);
</pre></div>
<p>
</p>
<p>
</p>
<div class="warning" style="margin-left: 0.5in; margin-right: 0.5in;">
<h3 class="title">Warning</h3>
<p>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.</p>
</div>
<p>This model generates random multigraphs on <em class="parameter"><code>n</code></em> vertices with <em class="parameter"><code>m</code></em> edges
through independent edge assignment (IEA). Each of the <em class="parameter"><code>m</code></em> edges is assigned
uniformly at random to an <span class="emphasis"><em>ordered</em></span> vertex pair, independently of each
other.
</p>
<p>
This model does not sample multigraphs uniformly. Undirected graphs are
generated with probability proportional to
</p>
<p>
<code class="literal">(prod_(i&lt;j) A_ij ! prod_i A_ii !!)^(-1)</code>,
</p>
<p>
where <code class="constant">A</code> denotes the adjacency matrix and <code class="literal">!!</code> denotes
the double factorial. Here <code class="constant">A</code> is assumed to have twice the number of
self-loops on its diagonal. The corresponding expression for directed
graphs is
</p>
<p>
<code class="literal">(prod_(i,j) A_ij !)^(-1)</code>.
</p>
<p>
Thus the probability of all simple graphs (which only have 0s and 1s in
the adjacency matrix) is the same, while that of non-simple ones depends
on their edge and self-loop multiplicities.
</p>
<p>
An alternative way to think of this model is that it performs uniform
sampling of <span class="emphasis"><em>edge-labeled</em></span> graphs, i.e. graphs in which not only vertices,
but also edges carry unique identities and are distinguishable.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of edges in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate a directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
<td><p>
Whether to generate self-loops.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid <em class="parameter"><code>n</code></em> or <em class="parameter"><code>m</code></em> parameter.
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough
memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges in the graph.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnm" title="1.1. igraph_erdos_renyi_game_gnm — Generates a random (Erdős-Rényi) graph with a fixed number of edges."><code class="function">igraph_erdos_renyi_game_gnm()</code></a> to uniformly sample graphs with
a given number of vertices and edges.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_sbm_game"></a>1.4. <code class="function">igraph_sbm_game</code> — Sample from a stochastic block model.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.7.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_sbm_game(
igraph_t *graph,
const igraph_matrix_t *pref_matrix,
const igraph_vector_int_t *block_sizes,
igraph_bool_t directed,
igraph_edge_type_sw_t allowed_edge_types);
</pre></div>
<p>
</p>
<p>
This function samples graphs from a stochastic block model, a generalization
of the G(n,p) model where the connection probability p (or expected number
of edges for multigraphs) is specified separately between and within a given
group of vertices.
</p>
<p>
The order of the vertex IDs in the generated graph corresponds to
the <em class="parameter"><code>block_sizes</code></em> argument.
</p>
<p>
Reference:
</p>
<p>
Faust, K., &amp; Wasserman, S. (1992a).
Blockmodels: Interpretation and evaluation.
Social Networks, 14, 5-–61.
<a class="ulink" href="https://doi.org/10.1016/0378-8733(92)90013-W" target="_top">https://doi.org/10.1016/0378-8733(92)90013-W</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The output graph. This should be a pointer to an
uninitialized graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref_matrix</code></em>:</span></p></td>
<td><p>
The matrix giving the connection probabilities
(or expected edge multiplicities for multigraphs) between groups.
This is a k-by-k 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).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>block_sizes</code></em>:</span></p></td>
<td><p>
An integer vector giving the number of
vertices in each group.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean, whether to create a directed graph. If
this argument is <code class="constant">false</code>, then <em class="parameter"><code>pref_matrix</code></em> must be symmetric.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are generated. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
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.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnp" title="1.2. igraph_erdos_renyi_game_gnp — Generates a random (Erdős-Rényi) graph with fixed edge probabilities."><code class="function">igraph_erdos_renyi_game_gnp()</code></a> for a simple Bernoulli graph.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_hsbm_game"></a>1.5. <code class="function">igraph_hsbm_game</code> — Hierarchical stochastic block model.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.8.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_hsbm_game(igraph_t *graph, igraph_int_t n,
igraph_int_t m, const igraph_vector_t *rho,
const igraph_matrix_t *C, igraph_real_t p);
</pre></div>
<p>
</p>
<p>
The function generates a random graph according to the hierarchical
stochastic block model.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The generated graph is stored here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of vertices per block. n/m must be integer.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>rho</code></em>:</span></p></td>
<td><p>
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.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>C</code></em>:</span></p></td>
<td><p>
A square, symmetric numeric matrix, the Bernoulli rates for
the clusters within a block. Its size must mach the size of the
<em class="parameter"><code>rho</code></em> vector.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>p</code></em>:</span></p></td>
<td><p>
The Bernoulli rate of connections between
vertices in different blocks.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_sbm_game" title="1.4. igraph_sbm_game — Sample from a stochastic block model."><code class="function">igraph_sbm_game()</code></a> for the classic stochastic block model,
<a class="link" href="igraph-Games.html#igraph_hsbm_list_game" title="1.6. igraph_hsbm_list_game — Hierarchical stochastic block model, more general version."><code class="function">igraph_hsbm_list_game()</code></a> for a more general version.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_hsbm_list_game"></a>1.6. <code class="function">igraph_hsbm_list_game</code> — Hierarchical stochastic block model, more general version.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.9.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_hsbm_list_game(igraph_t *graph, igraph_int_t n,
const igraph_vector_int_t *mlist,
const igraph_vector_list_t *rholist,
const igraph_matrix_list_t *Clist,
igraph_real_t p);
</pre></div>
<p>
</p>
<p>
The function generates a random graph according to the hierarchical
stochastic block model.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The generated graph is stored here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>mlist</code></em>:</span></p></td>
<td><p>
An integer vector of block sizes.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>rholist</code></em>:</span></p></td>
<td><p>
A list of rho vectors (<code class="constant">igraph_vector_t</code> objects), one
for each block.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>Clist</code></em>:</span></p></td>
<td><p>
A list of square matrices (<code class="constant">igraph_matrix_t</code> objects),
one for each block, specifying the Bernoulli rates of connections
within the block.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>p</code></em>:</span></p></td>
<td><p>
The Bernoulli rate of connections between
vertices in different blocks.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_sbm_game" title="1.4. igraph_sbm_game — Sample from a stochastic block model."><code class="function">igraph_sbm_game()</code></a> for the classic stochastic block model,
<a class="link" href="igraph-Games.html#igraph_hsbm_game" title="1.5. igraph_hsbm_game — Hierarchical stochastic block model."><code class="function">igraph_hsbm_game()</code></a> for a simpler general version.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_preference_game"></a>1.7. <code class="function">igraph_preference_game</code> — Generates a graph with vertex types and connection preferences.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.10.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_preference_game(igraph_t *graph, igraph_int_t nodes,
igraph_int_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);
</pre></div>
<p>
</p>
<p>
</p>
<p>
This is practically the nongrowing variant of
<a class="link" href="igraph-Games.html#igraph_establishment_game" title="3.3. igraph_establishment_game — Generates a graph with a simple growing model with vertex types."><code class="function">igraph_establishment_game()</code></a>. 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.
</p>
<p>
In other words, this function generates a graph according to a
block-model. Vertices are divided into groups (or blocks), and
the probability the two vertices are connected depends on their
groups only.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
<td><p>
The number of vertex types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>type_dist</code></em>:</span></p></td>
<td><p>
Vector giving the distribution of vertex types. If
<code class="constant">NULL</code>, all vertex types will have equal probability. See also the
<em class="parameter"><code>fixed_sizes</code></em> argument.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>fixed_sizes</code></em>:</span></p></td>
<td><p>
Boolean. If true, then the number of vertices with a
given vertex type is fixed and the <em class="parameter"><code>type_dist</code></em> argument gives these
numbers for each vertex type. If true, and <em class="parameter"><code>type_dist</code></em> is <code class="constant">NULL</code>,
then the function tries to make vertex groups of the same size. If this
is not possible, then some groups will have an extra vertex.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref_matrix</code></em>:</span></p></td>
<td><p>
Matrix giving the connection probabilities for
different vertex types. This should be symmetric if the requested
graph is undirected.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>node_type_vec</code></em>:</span></p></td>
<td><p>
A vector where the individual generated vertex types
will be stored. If <code class="constant">NULL</code>, the vertex types won't be saved.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate a directed graph. If undirected
graphs are requested, only the lower left triangle of the preference
matrix is considered.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
<td><p>
Whether loop edges are allowed.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Added in version 0.3.</p>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges in the graph.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_asymmetric_preference_game" title="1.8. igraph_asymmetric_preference_game — Generates a graph with asymmetric vertex types and connection preferences."><code class="function">igraph_asymmetric_preference_game()</code></a>,
<a class="link" href="igraph-Games.html#igraph_establishment_game" title="3.3. igraph_establishment_game — Generates a graph with a simple growing model with vertex types."><code class="function">igraph_establishment_game()</code></a>, <a class="link" href="igraph-Games.html#igraph_callaway_traits_game" title="3.2. igraph_callaway_traits_game — Simulates a growing network with vertex types."><code class="function">igraph_callaway_traits_game()</code></a>
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_asymmetric_preference_game"></a>1.8. <code class="function">igraph_asymmetric_preference_game</code> — Generates a graph with asymmetric vertex types and connection preferences.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.11.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_asymmetric_preference_game(igraph_t *graph, igraph_int_t nodes,
igraph_int_t no_out_types,
igraph_int_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);
</pre></div>
<p>
</p>
<p>
</p>
<p>
This is the asymmetric variant of <a class="link" href="igraph-Games.html#igraph_preference_game" title="1.7. igraph_preference_game — Generates a graph with vertex types and connection preferences."><code class="function">igraph_preference_game()</code></a>.
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.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>no_out_types</code></em>:</span></p></td>
<td><p>
The number of vertex out-types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>no_in_types</code></em>:</span></p></td>
<td><p>
The number of vertex in-types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>type_dist_matrix</code></em>:</span></p></td>
<td><p>
Matrix of size <code class="literal">out_types * in_types</code>,
giving the joint distribution of vertex types.
If <code class="constant">NULL</code>, incoming and outgoing vertex types are independent and uniformly
distributed.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref_matrix</code></em>:</span></p></td>
<td><p>
Matrix of size <code class="literal">out_types * in_types</code>,
giving the connection probabilities for different vertex types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>node_type_out_vec</code></em>:</span></p></td>
<td><p>
A vector where the individual generated "outgoing"
vertex types will be stored. If <code class="constant">NULL</code>, the vertex types won't be saved.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>node_type_in_vec</code></em>:</span></p></td>
<td><p>
A vector where the individual generated "incoming"
vertex types will be stored. If <code class="constant">NULL</code>, the vertex types won't be saved.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
<td><p>
Whether loop edges are allowed.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Added in version 0.3.</p>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges in the graph.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_preference_game" title="1.7. igraph_preference_game — Generates a graph with vertex types and connection preferences."><code class="function">igraph_preference_game()</code></a>
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_correlated_game"></a>1.9. <code class="function">igraph_correlated_game</code> — Generates a random graph correlated to an existing graph.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.12.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_correlated_game(igraph_t *new_graph, const igraph_t *old_graph,
igraph_real_t corr, igraph_real_t p,
const igraph_vector_int_t *permutation);
</pre></div>
<p>
</p>
<p>
Sample a new graph by perturbing the adjacency matrix of a
given simple graph and shuffling its vertices.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>new_graph</code></em>:</span></p></td>
<td><p>
The new graph to initialize based on an existing graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>old_graph</code></em>:</span></p></td>
<td><p>
The original graph, which must be a simple graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>corr</code></em>:</span></p></td>
<td><p>
A value 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).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>p</code></em>:</span></p></td>
<td><p>
The probability of an edge between two vertices. It must in the
open (0,1) interval. Typically, the density of <em class="parameter"><code>old_graph</code></em>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>permutation</code></em>:</span></p></td>
<td><p>
A permutation to apply to the vertices of the
generated graph. The i-th element of the vector specifies the index
of the vertex in the <span class="emphasis"><em>original</em></span> graph that will become vertex i in the
new graph. It can also be a null pointer, in which case the vertices
will not be permuted.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_correlated_pair_game" title="1.10. igraph_correlated_pair_game — Generates pairs of correlated random graphs."><code class="function">igraph_correlated_pair_game()</code></a> for generating a pair
of correlated random graphs in one go.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_correlated_pair_game"></a>1.10. <code class="function">igraph_correlated_pair_game</code> — Generates pairs of correlated random graphs.</h3></div></div></div>
<a class="indexterm" name="id-1.13.3.13.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_correlated_pair_game(igraph_t *graph1, igraph_t *graph2,
igraph_int_t n, igraph_real_t corr, igraph_real_t p,
igraph_bool_t directed,
const igraph_vector_int_t *permutation);
</pre></div>
<p>
</p>
<p>
Sample two random graphs, with given correlation.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph1</code></em>:</span></p></td>
<td><p>
The first graph will be stored here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph2</code></em>:</span></p></td>
<td><p>
The second graph will be stored here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in both graphs.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>corr</code></em>:</span></p></td>
<td><p>
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).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>p</code></em>:</span></p></td>
<td><p>
A numeric scalar, the probability of an edge between two
vertices, it must in the open (0,1) interval.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate directed graphs.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>permutation</code></em>:</span></p></td>
<td><p>
A permutation to apply to the vertices of the
generated graph. The i-th element of the vector specifies the index
of the vertex in the <span class="emphasis"><em>first</em></span> graph that will become vertex i in the
second graph. It can also be a null pointer, in which case the vertices
will not be permuted.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_correlated_game" title="1.9. igraph_correlated_game — Generates a random graph correlated to an existing graph."><code class="function">igraph_correlated_game()</code></a> for generating a correlated pair
to a given graph.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="preferential-attachment-games"></a>2. Preferential attachment and related models</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#igraph_barabasi_game">2.1. <code class="function">igraph_barabasi_game</code> — Generates a graph based on the Barabási-Albert model.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_barabasi_aging_game">2.2. <code class="function">igraph_barabasi_aging_game</code> — Preferential attachment with aging of vertices.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_recent_degree_game">2.3. <code class="function">igraph_recent_degree_game</code> — Stochastic graph generator based on the number of incident edges a node has gained recently.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_recent_degree_aging_game">2.4. <code class="function">igraph_recent_degree_aging_game</code> — Preferential attachment based on the number of edges gained recently, with aging of vertices.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_lastcit_game">2.5. <code class="function">igraph_lastcit_game</code> — Simulates a citation network, based on time passed since the last citation.</a></span></dt>
</dl></div>
<p>Preferential attachment models are growing random graphs where vertices are added iteratively,
and connected to previously added vertices based on dynamically changing vertex properties, such as
degree or time since the vertex was added.</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_barabasi_game"></a>2.1. <code class="function">igraph_barabasi_game</code> — Generates a graph based on the Barabási-Albert model.</h3></div></div></div>
<a class="indexterm" name="id-1.13.4.3.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_barabasi_game(igraph_t *graph, igraph_int_t n,
igraph_real_t power,
igraph_int_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);
</pre></div>
<p>
</p>
<p>
This function implements several variants of the preferential attachment
process, including linear and non-linear varieties of the Barabási-Albert
and Price models. The graph construction starts with a single vertex,
or an existing graph given by the <em class="parameter"><code>start_from</code></em> parameter. Then new vertices
are added one at a time. Each new vertex connects to <em class="parameter"><code>m</code></em> existing vertices,
choosing them with probabilities proportional to
</p>
<p>
<code class="literal">d^power + A</code>,
</p>
<p>
where <code class="constant">d</code> is the in- or total degree of the existing vertex (controlled
by the <em class="parameter"><code>outpref</code></em> argument), while <em class="parameter"><code>power</code></em> and <em class="parameter"><code>A</code></em> are given by
parameters. The <span class="emphasis"><em>constant attractiveness</em></span> <em class="parameter"><code>A</code></em>
is used to ensure that vertices with zero in-degree can also be
connected to with non-zero probability.
</p>
<p>
Barabási, A.-L. and Albert R. 1999. Emergence of scaling in
random networks, Science, 286 509--512.
<a class="ulink" href="https://doi.org/10.1126/science.286.5439.509" target="_top">https://doi.org/10.1126/science.286.5439.509</a>
</p>
<p>
de Solla Price, D. J. 1965. Networks of Scientific Papers, Science,
149 510--515.
<a class="ulink" href="https://doi.org/10.1126/science.149.3683.510" target="_top">https://doi.org/10.1126/science.149.3683.510</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
An uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>power</code></em>:</span></p></td>
<td><p>
Power of the preferential attachment. In the classic preferential
attachment model <code class="literal">power=1</code>. Other values allow for
sampling from a non-linear preferential attachment model.
Negative values are only allowed when no zero-degree vertices
are present during the construction process, i.e. when
the starting graph has no isolated vertices and <em class="parameter"><code>outpref</code></em>
is set to <code class="constant">true</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of outgoing edges generated for each
vertex. Only used when <em class="parameter"><code>outseq</code></em> is <code class="constant">NULL</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outseq</code></em>:</span></p></td>
<td><p>
Gives the (out-)degrees of the vertices. If this is
constant, this can be a <code class="constant">NULL</code> pointer.
In this case <em class="parameter"><code>m</code></em> contains the constant out-degree.
The very first vertex has by definition no outgoing edges,
so the first number in this vector is ignored.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outpref</code></em>:</span></p></td>
<td><p>
Boolean, if true not only the in- but also the out-degree
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.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>A</code></em>:</span></p></td>
<td><p>
The constant attractiveness of vertices. When <em class="parameter"><code>outpref</code></em>
is set to <code class="constant">false</code>, it should be positive to ensure that
zero in-degree vertices can be connected to as well.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean, whether to generate a directed graph.
When set to <code class="constant">false</code>, outpref is assumed to be <code class="constant">true</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>algo</code></em>:</span></p></td>
<td>
<p>
The algorithm to use to generate the network. Possible
values:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_BARABASI_BAG</code></span></p></td>
<td><p>
This is the algorithm that was previously (before version
0.6) solely implemented in igraph. It works by putting the
IDs of the vertices into a bag (multiset, really), exactly
as many times as their (in-)degree, plus once more. Then
the required number of cited vertices are drawn from the
bag, with replacement. This method might generate multiple
edges. It only works if power=1 and A=1.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_BARABASI_PSUMTREE</code></span></p></td>
<td><p>
This algorithm uses a partial prefix-sum tree to generate
the graph. It does not generate multiple edges and
works for any power and A values.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_BARABASI_PSUMTREE_MULTIPLE</code></span></p></td>
<td><p>
This algorithm also uses a partial prefix-sum tree to
generate the graph. The difference is, that now multiple
edges are allowed. This method was implemented under the
name <code class="constant">igraph_nonlinear_barabasi_game</code> before version 0.6.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>start_from</code></em>:</span></p></td>
<td><p>
Either a <code class="constant">NULL</code> pointer, or a graph. In the former
case, the starting configuration is a clique of size <em class="parameter"><code>m</code></em>.
In the latter case, the graph is a starting configuration.
The graph must be non-empty, i.e. it must have at least one
vertex. If a graph is supplied here and the <em class="parameter"><code>outseq</code></em>
argument is also given, then <em class="parameter"><code>outseq</code></em> should only contain
information on the vertices that are not in the <em class="parameter"><code>start_from</code></em> graph.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid <em class="parameter"><code>n</code></em>, <em class="parameter"><code>m</code></em>, <em class="parameter"><code>A</code></em> or <em class="parameter"><code>outseq</code></em> parameter.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges.
</p>
<div class="hideshow" onClick="toggle(this, event)">
<div class="example">
<a name="id-1.13.4.3.12.1"></a><p class="title"><b>Example 12.3.  File <code class="code">examples/simple/igraph_barabasi_game.c</code></b></p>
<div class="example-contents">
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> &lt;igraph.h&gt;
int <span class="strong"><strong>main</strong></span>(void) {
igraph_t g;
igraph_vector_int_t v;
igraph_vector_int_t v2, v3;
<span class="emphasis"><em>/* Initialize the library. */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(&amp;g, 10, <span class="emphasis"><em>/*power=*/</em></span> 1, 2, 0, 0, <span class="emphasis"><em>/*A=*/</em></span> 1, 1,
IGRAPH_BARABASI_BAG, <span class="emphasis"><em>/*start_from=*/</em></span> 0);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g) != 18) {
<span class="strong"><strong>return</strong></span> 1;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 10) {
<span class="strong"><strong>return</strong></span> 2;
}
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g)) {
<span class="strong"><strong>return</strong></span> 3;
}
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&amp;v, 0);
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_get_edgelist" title="26.11. igraph_get_edgelist — The list of edges in a graph.">igraph_get_edgelist</a></strong></span>(&amp;g, &amp;v, 0);
<span class="strong"><strong>for</strong></span> (igraph_int_t i = 0; i &lt; <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g); i++) {
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v)[2 * i] &lt;= <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v)[2 * i + 1]) {
<span class="strong"><strong>return</strong></span> 4;
}
}
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;v);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* out-degree sequence */</em></span>
<span class="strong"><strong>igraph_vector_int_init_int</strong></span>(&amp;v3, 10, 0, 1, 3, 3, 4, 5, 6, 7, 8, 9);
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(&amp;g, 10, <span class="emphasis"><em>/*power=*/</em></span> 1, 0, &amp;v3, 0, <span class="emphasis"><em>/*A=*/</em></span> 1, 1,
IGRAPH_BARABASI_BAG, <span class="emphasis"><em>/*start_from=*/</em></span> 0);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g) != <span class="strong"><strong>igraph_vector_int_sum</strong></span>(&amp;v3)) {
<span class="strong"><strong>return</strong></span> 5;
}
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&amp;v2, 0);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;v2, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_OUT, IGRAPH_LOOPS);
<span class="strong"><strong>for</strong></span> (igraph_int_t i = 0; i &lt; <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g); i++) {
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v3)[i] != <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v2)[i]) {
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;v3);
<span class="strong"><strong>printf</strong></span>("\n");
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;v2);
<span class="strong"><strong>return</strong></span> 6;
}
}
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;v3);
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;v2);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* outpref, we cannot really test this quantitatively,</em></span>
<span class="emphasis"><em> would need to set random seed */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(&amp;g, 10, <span class="emphasis"><em>/*power=*/</em></span> 1, 2, 0, 1, <span class="emphasis"><em>/*A=*/</em></span> 1, 1,
IGRAPH_BARABASI_BAG, <span class="emphasis"><em>/*start_from=*/</em></span> 0);
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&amp;v, 0);
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_get_edgelist" title="26.11. igraph_get_edgelist — The list of edges in a graph.">igraph_get_edgelist</a></strong></span>(&amp;g, &amp;v, 0);
<span class="strong"><strong>for</strong></span> (igraph_int_t i = 0; i &lt; <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g); i++) {
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v)[2 * i] &lt;= <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(v)[2 * i + 1]) {
<span class="strong"><strong>return</strong></span> 7;
}
}
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g)) {
<span class="strong"><strong>return</strong></span> 8;
}
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;v);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="strong"><strong>return</strong></span> 0;
}
</pre>
<p></p>
</div>
</div>
<br class="example-break">
</div>
<div class="hideshow" onClick="toggle(this, event)">
<div class="example">
<a name="id-1.13.4.3.12.2"></a><p class="title"><b>Example 12.4.  File <code class="code">examples/simple/igraph_barabasi_game2.c</code></b></p>
<div class="example-contents">
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> &lt;igraph.h&gt;
<span class="strong"><strong>#include</strong></span> &lt;stdio.h&gt;
int <span class="strong"><strong>main</strong></span>(void) {
igraph_t g;
igraph_bool_t simple;
<span class="emphasis"><em>/* Initialize the library. */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(<span class="emphasis"><em>/* graph= */</em></span> &amp;g,
<span class="emphasis"><em>/* n= */</em></span> 100,
<span class="emphasis"><em>/* power= */</em></span> 1.0,
<span class="emphasis"><em>/* m= */</em></span> 2,
<span class="emphasis"><em>/* outseq= */</em></span> 0,
<span class="emphasis"><em>/* outpref= */</em></span> 0,
<span class="emphasis"><em>/* A= */</em></span> 1.0,
<span class="emphasis"><em>/* directed= */</em></span> IGRAPH_DIRECTED,
<span class="emphasis"><em>/* algo= */</em></span> IGRAPH_BARABASI_PSUMTREE,
<span class="emphasis"><em>/* start_from= */</em></span> 0);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g) != 197) {
<span class="strong"><strong>return</strong></span> 1;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 100) {
<span class="strong"><strong>return</strong></span> 2;
}
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph.">igraph_is_simple</a></strong></span>(&amp;g, &amp;simple, IGRAPH_DIRECTED);
<span class="strong"><strong>if</strong></span> (!simple) {
<span class="strong"><strong>return</strong></span> 3;
}
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* ============================== */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(<span class="emphasis"><em>/* graph= */</em></span> &amp;g,
<span class="emphasis"><em>/* n= */</em></span> 100,
<span class="emphasis"><em>/* power= */</em></span> 1.0,
<span class="emphasis"><em>/* m= */</em></span> 2,
<span class="emphasis"><em>/* outseq= */</em></span> 0,
<span class="emphasis"><em>/* outpref= */</em></span> 0,
<span class="emphasis"><em>/* A= */</em></span> 1.0,
<span class="emphasis"><em>/* directed= */</em></span> IGRAPH_DIRECTED,
<span class="emphasis"><em>/* algo= */</em></span> IGRAPH_BARABASI_PSUMTREE_MULTIPLE,
<span class="emphasis"><em>/* start_from= */</em></span> 0);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g) != 198) {
<span class="strong"><strong>return</strong></span> 4;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 100) {
<span class="strong"><strong>return</strong></span> 5;
}
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph.">igraph_is_simple</a></strong></span>(&amp;g, &amp;simple, IGRAPH_DIRECTED);
<span class="strong"><strong>if</strong></span> (simple) {
<span class="strong"><strong>return</strong></span> 6;
}
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* ============================== */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_barabasi_game" title="2.1. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.">igraph_barabasi_game</a></strong></span>(<span class="emphasis"><em>/* graph= */</em></span> &amp;g,
<span class="emphasis"><em>/* n= */</em></span> 100,
<span class="emphasis"><em>/* power= */</em></span> 1.0,
<span class="emphasis"><em>/* m= */</em></span> 2,
<span class="emphasis"><em>/* outseq= */</em></span> 0,
<span class="emphasis"><em>/* outpref= */</em></span> 0,
<span class="emphasis"><em>/* A= */</em></span> 1.0,
<span class="emphasis"><em>/* directed= */</em></span> IGRAPH_DIRECTED,
<span class="emphasis"><em>/* algo= */</em></span> IGRAPH_BARABASI_BAG,
<span class="emphasis"><em>/* start_from= */</em></span> 0);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;g) != 198) {
<span class="strong"><strong>return</strong></span> 7;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 100) {
<span class="strong"><strong>return</strong></span> 8;
}
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph.">igraph_is_simple</a></strong></span>(&amp;g, &amp;simple, IGRAPH_DIRECTED);
<span class="strong"><strong>if</strong></span> (simple) {
<span class="strong"><strong>return</strong></span> 9;
}
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="strong"><strong>return</strong></span> 0;
}
</pre>
<p></p>
</div>
</div>
<br class="example-break">
</div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_barabasi_aging_game"></a>2.2. <code class="function">igraph_barabasi_aging_game</code> — Preferential attachment with aging of vertices.</h3></div></div></div>
<a class="indexterm" name="id-1.13.4.4.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_barabasi_aging_game(igraph_t *graph,
igraph_int_t nodes,
igraph_int_t m,
const igraph_vector_int_t *outseq,
igraph_bool_t outpref,
igraph_real_t pa_exp,
igraph_real_t aging_exp,
igraph_int_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);
</pre></div>
<p>
</p>
<p>
</p>
<p>
This game starts with one vertex (if <em class="parameter"><code>nodes</code></em> &gt; 0). In each step
a new node is added, and it is connected to <em class="parameter"><code>m</code></em> existing nodes.
Existing nodes to connect to are chosen with probability dependent
on their (in-)degree (<code class="constant">k</code>) and age (<code class="constant">l</code>).
The degree-dependent part is
<code class="literal">deg_coef * k^pa_exp + zero_deg_appeal</code>,
while the age-dependent part is
<code class="literal">age_coef * l^aging_exp + zero_age_appeal</code>,
which are multiplied to obtain the final weight.
</p>
<p>
The age <code class="constant">l</code> is based on the number of vertices in the
network and the <em class="parameter"><code>aging_bins</code></em> argument: the age of a node
is incremented by 1 after each
<code class="literal">floor(nodes / aging_bins) + 1</code>
time steps.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of edges to add in each time step.
Ignored if <em class="parameter"><code>outseq</code></em> is a non-zero length vector.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outseq</code></em>:</span></p></td>
<td><p>
The number of edges to add in each time step. If it
is <code class="constant">NULL</code> or a zero-length vector then it is ignored
and the <em class="parameter"><code>m</code></em> argument is used instead.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outpref</code></em>:</span></p></td>
<td><p>
Boolean constant, whether the edges
initiated by a vertex contribute to the probability to gain
a new edge.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pa_exp</code></em>:</span></p></td>
<td><p>
The exponent of the preferential attachment, a small
positive number usually, the value 1 yields the classic
linear preferential attachment.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>aging_exp</code></em>:</span></p></td>
<td><p>
The exponent of the aging, this is a negative
number usually.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>aging_bins</code></em>:</span></p></td>
<td><p>
Integer constant, the number of age bins to use.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>zero_deg_appeal</code></em>:</span></p></td>
<td><p>
The degree dependent part of the
attractiveness of the zero degree vertices.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>zero_age_appeal</code></em>:</span></p></td>
<td><p>
The age dependent part of the attractiveness
of the vertices of age zero. This parameter is usually zero.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>deg_coef</code></em>:</span></p></td>
<td><p>
The coefficient for the degree.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>age_coef</code></em>:</span></p></td>
<td><p>
The coefficient for the age.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean constant, whether to generate a directed
graph.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O((|V|+|V|/aging_bins)*log(|V|)+|E|). |V| is the number
of vertices, |E| the number of edges.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_recent_degree_game"></a>2.3. <code class="function">igraph_recent_degree_game</code> — Stochastic graph generator based on the number of incident edges a node has gained recently.</h3></div></div></div>
<a class="indexterm" name="id-1.13.4.5.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_recent_degree_game(igraph_t *graph, igraph_int_t nodes,
igraph_real_t power,
igraph_int_t time_window,
igraph_int_t m,
const igraph_vector_int_t *outseq,
igraph_bool_t outpref,
igraph_real_t zero_appeal,
igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph, this is the same as
the number of time steps.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>power</code></em>:</span></p></td>
<td><p>
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 <em class="parameter"><code>window</code></em> time steps) to <em class="parameter"><code>power</code></em>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>time_window</code></em>:</span></p></td>
<td><p>
Integer constant, the size of the time window to use
to count the number of recent edges.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
Integer constant, the number of edges to add per time
step if the <em class="parameter"><code>outseq</code></em> parameter is a null pointer or a
zero-length vector.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outseq</code></em>:</span></p></td>
<td><p>
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 <em class="parameter"><code>m</code></em> parameter is used.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outpref</code></em>:</span></p></td>
<td><p>
Boolean 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.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>zero_appeal</code></em>:</span></p></td>
<td><p>
Constant giving the attractiveness of the
vertices which haven't gained any edge recently.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean constant, whether to generate a directed
graph.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|*log(|V|)+|E|), |V| is the number of
vertices, |E| is the number of edges in the graph.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_recent_degree_aging_game"></a>2.4. <code class="function">igraph_recent_degree_aging_game</code> — Preferential attachment based on the number of edges gained recently, with aging of vertices.</h3></div></div></div>
<a class="indexterm" name="id-1.13.4.6.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_recent_degree_aging_game(igraph_t *graph,
igraph_int_t nodes,
igraph_int_t m,
const igraph_vector_int_t *outseq,
igraph_bool_t outpref,
igraph_real_t pa_exp,
igraph_real_t aging_exp,
igraph_int_t aging_bins,
igraph_int_t time_window,
igraph_real_t zero_appeal,
igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
</p>
<p>
This game is very similar to <a class="link" href="igraph-Games.html#igraph_barabasi_aging_game" title="2.2. igraph_barabasi_aging_game — Preferential attachment with aging of vertices."><code class="function">igraph_barabasi_aging_game()</code></a>,
except that instead of the total number of incident edges the
number of edges gained in the last <em class="parameter"><code>time_window</code></em> time steps are
counted.
</p>
<p>The degree dependent part of the attractiveness is
given by k to the power of <em class="parameter"><code>pa_exp</code></em> plus <em class="parameter"><code>zero_appeal</code></em>; the age
dependent part is l to the power to <em class="parameter"><code>aging_exp</code></em>.
k is the number of edges gained in the last <em class="parameter"><code>time_window</code></em> time
steps, l is the age of the vertex.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of edges to add in each time step. If the <em class="parameter"><code>outseq</code></em> argument is not a null vector or a zero-length vector
then it is ignored.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outseq</code></em>:</span></p></td>
<td><p>
Vector giving the number of edges to add in each time
step. If it is a null pointer or a zero-length vector then
it is ignored and the <em class="parameter"><code>m</code></em> argument is used.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>outpref</code></em>:</span></p></td>
<td><p>
Boolean constant, if true the edges initiated by a
vertex are also counted. Normally it is false.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pa_exp</code></em>:</span></p></td>
<td><p>
The exponent for the preferential attachment.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>aging_exp</code></em>:</span></p></td>
<td><p>
The exponent for the aging, normally it is
negative: old vertices gain edges with less probability.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>aging_bins</code></em>:</span></p></td>
<td><p>
Integer constant, the number of age bins to use.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>time_window</code></em>:</span></p></td>
<td><p>
The time window to use to count the number of
incident edges for the vertices.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>zero_appeal</code></em>:</span></p></td>
<td><p>
The degree dependent part of the attractiveness
for zero degree vertices.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean constant, whether to create a directed
graph.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O((|V|+|V|/aging_bins)*log(|V|)+|E|). |V| is the number
of vertices, |E| the number of edges.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_lastcit_game"></a>2.5. <code class="function">igraph_lastcit_game</code> — Simulates a citation network, based on time passed since the last citation.</h3></div></div></div>
<a class="indexterm" name="id-1.13.4.7.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_lastcit_game(igraph_t *graph,
igraph_int_t nodes, igraph_int_t edges_per_node,
igraph_int_t agebins,
const igraph_vector_t *preference,
igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
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 <em class="parameter"><code>edges_per_step</code></em> 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 <em class="parameter"><code>agebins</code></em> bins.
So if the current time step is <code class="constant">t</code> and the last citation to a
given <code class="constant">i</code> vertex was made in time step <code class="constant">t0</code>, then
<code class="literal">(t-t0) / binwidth</code>
is calculated where binwidth is
<code class="literal">nodes/agebins + 1</code>,
in the last expression '/' denotes integer division, so the
fraction part is omitted.
</p>
<p>
The <em class="parameter"><code>preference</code></em> 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.
</p>
<p>
Note that this function generates networks with multiple edges if
<em class="parameter"><code>edges_per_step</code></em> is bigger than one, call <a class="link" href="igraph-Operators.html#igraph_simplify" title="3.11. igraph_simplify — Removes loop and/or multiple edges from the graph."><code class="function">igraph_simplify()</code></a>
on the result to get rid of these edges.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object, the result
will be stored here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the network.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>edges_per_node</code></em>:</span></p></td>
<td><p>
The number of edges to add in each time
step.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>agebins</code></em>:</span></p></td>
<td><p>
The number of age bins to use.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>preference</code></em>:</span></p></td>
<td><p>
Pointer to an initialized vector of length
<code class="literal">agebins + 1</code>. This contains the "attractivity" of the various
age bins, the last element is the attractivity of the vertices
which were never cited, and it should be greater than zero.
It is a good idea to have all positive values in this vector.
Preferences cannot be negative.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean constant, whether to create directed
networks.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_barabasi_aging_game" title="2.2. igraph_barabasi_aging_game — Preferential attachment with aging of vertices."><code class="function">igraph_barabasi_aging_game()</code></a>.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|*a+|E|*log|V|), |V| is the number of vertices,
|E| is the total number of edges, a is the <em class="parameter"><code>agebins</code></em> parameter.
</p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="growing-random-games"></a>3. Growing random graph models</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#igraph_growing_random_game">3.1. <code class="function">igraph_growing_random_game</code> — Generates a growing random graph.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_callaway_traits_game">3.2. <code class="function">igraph_callaway_traits_game</code> — Simulates a growing network with vertex types.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_establishment_game">3.3. <code class="function">igraph_establishment_game</code> — Generates a graph with a simple growing model with vertex types.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_cited_type_game">3.4. <code class="function">igraph_cited_type_game</code> — Simulates a citation based on vertex types.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_citing_cited_type_game">3.5. <code class="function">igraph_citing_cited_type_game</code> — Simulates a citation network based on vertex types.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_forest_fire_game">3.6. <code class="function">igraph_forest_fire_game</code> — Generates a network according to the <span class="quote">“<span class="quote">forest fire game</span>”</span>.</a></span></dt>
</dl></div>
<p>In growing random graphs, vertices are added iteratively, and connected based on various rules.
Preferential attachment models are documented <a class="link" href="igraph-Games.html#preferential-attachment-games" title="2. Preferential attachment and related models">in their
own section</a>.
</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_growing_random_game"></a>3.1. <code class="function">igraph_growing_random_game</code> — Generates a growing random graph.</h3></div></div></div>
<a class="indexterm" name="id-1.13.5.3.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_growing_random_game(igraph_t *graph, igraph_int_t n,
igraph_int_t m, igraph_bool_t directed,
igraph_bool_t citation);
</pre></div>
<p>
</p>
<p>
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.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>m</code></em>:</span></p></td>
<td><p>
The number of edges to add in a time step (i.e. after
adding a vertex).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean, whether to generate a directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>citation</code></em>:</span></p></td>
<td><p>
Boolean, if <code class="constant">true</code>, the edges always
originate from the most recently added vertex and are
connected to a previous vertex.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid
<em class="parameter"><code>n</code></em> or <em class="parameter"><code>m</code></em>
parameter.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_callaway_traits_game"></a>3.2. <code class="function">igraph_callaway_traits_game</code> — Simulates a growing network with vertex types.</h3></div></div></div>
<a class="indexterm" name="id-1.13.5.4.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_callaway_traits_game(igraph_t *graph, igraph_int_t nodes,
igraph_int_t types, igraph_int_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);
</pre></div>
<p>
</p>
<p>
The different types of vertices prefer to connect other types of
vertices with a given probability.
</p>
<p>
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 <em class="parameter"><code>type_dist</code></em>. 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
<em class="parameter"><code>pref_matrix</code></em>. Then another two vertices are selected and this is
repeated <em class="parameter"><code>edges_per_step</code></em> times in each time step.
</p>
<p>
References:
</p>
<p>
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).
<a class="ulink" href="https://doi.org/10.1103/PhysRevE.64.041902" target="_top">https://doi.org/10.1103/PhysRevE.64.041902</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of nodes in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
<td><p>
Number of node types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>edges_per_step</code></em>:</span></p></td>
<td><p>
The number of connections tried in each time step.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>type_dist</code></em>:</span></p></td>
<td><p>
Vector giving the distribution of the vertex types.
If <code class="constant">NULL</code>, the distribution is assumed to be uniform.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref_matrix</code></em>:</span></p></td>
<td><p>
Matrix giving the connection probabilities for
the vertex types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate a directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>node_type_vec</code></em>:</span></p></td>
<td><p>
An initialized vector or <code class="constant">NULL</code>.
If not <code class="constant">NULL</code>, the type of each node will be stored here.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Added in version 0.2.</p>
<p>
Time complexity: O(|V|*k*log(|V|)), |V| is the number of vertices,
k is <em class="parameter"><code>edges_per_step</code></em>.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_establishment_game"></a>3.3. <code class="function">igraph_establishment_game</code> — Generates a graph with a simple growing model with vertex types.</h3></div></div></div>
<a class="indexterm" name="id-1.13.5.5.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_establishment_game(igraph_t *graph, igraph_int_t nodes,
igraph_int_t types, igraph_int_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);
</pre></div>
<p>
</p>
<p>
</p>
<p>
The simulation goes like this: a single vertex is added at each
time step. This new vertex tries to connect to <em class="parameter"><code>k</code></em> vertices in the
graph. The probability that such a connection is realized depends
on the types of the vertices involved.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
<td><p>
The number of vertex types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>k</code></em>:</span></p></td>
<td><p>
The number of connections tried in each time step.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>type_dist</code></em>:</span></p></td>
<td><p>
Vector giving the distribution of vertex types.
If <code class="constant">NULL</code>, the distribution is assumed to be uniform.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref_matrix</code></em>:</span></p></td>
<td><p>
Matrix giving the connection probabilities for
different vertex types.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to generate a directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>node_type_vec</code></em>:</span></p></td>
<td><p>
An initialized vector or <code class="constant">NULL</code>.
If not <code class="constant">NULL</code>, the type of each node will be stored here.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Added in version 0.2.</p>
<p>
Time complexity: O(|V|*k*log(|V|)), |V| is the number of vertices
and k is the <em class="parameter"><code>k</code></em> parameter.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_cited_type_game"></a>3.4. <code class="function">igraph_cited_type_game</code> — Simulates a citation based on vertex types.</h3></div></div></div>
<a class="indexterm" name="id-1.13.5.6.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_cited_type_game(igraph_t *graph, igraph_int_t nodes,
const igraph_vector_int_t *types,
const igraph_vector_t *pref,
igraph_int_t edges_per_step,
igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
Function to create a network based on some vertex categories. This
function creates a citation network: in each step a single vertex
and <em class="parameter"><code>edges_per_step</code></em> citing edges are added. Nodes with
different categories may have different probabilities to get
cited, as given by the <em class="parameter"><code>pref</code></em> vector.
</p>
<p>
Note that this function might generate networks with multiple edges
if <em class="parameter"><code>edges_per_step</code></em> is greater than one. You might want to call
<a class="link" href="igraph-Operators.html#igraph_simplify" title="3.11. igraph_simplify — Removes loop and/or multiple edges from the graph."><code class="function">igraph_simplify()</code></a> on the result to remove multiple edges.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the network.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
<td><p>
Numeric vector giving the categories of the vertices,
so it should contain <em class="parameter"><code>nodes</code></em> non-negative integer
numbers. Types are numbered from zero.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref</code></em>:</span></p></td>
<td><p>
The attractivity of the different vertex categories in
a vector. Its length should be the maximum element in <em class="parameter"><code>types</code></em>
plus one (types are numbered from zero).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>edges_per_step</code></em>:</span></p></td>
<td><p>
Integer constant, the number of edges to add
in each time step.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean constant, whether to create a directed
network.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_citing_cited_type_game" title="3.5. igraph_citing_cited_type_game — Simulates a citation network based on vertex types."><code class="function">igraph_citing_cited_type_game()</code></a> for a bit more general
game.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O((|V|+|E|)log|V|), |V| and |E| are number of
vertices and edges, respectively.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_citing_cited_type_game"></a>3.5. <code class="function">igraph_citing_cited_type_game</code> — Simulates a citation network based on vertex types.</h3></div></div></div>
<a class="indexterm" name="id-1.13.5.7.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_citing_cited_type_game(igraph_t *graph, igraph_int_t nodes,
const igraph_vector_int_t *types,
const igraph_matrix_t *pref,
igraph_int_t edges_per_step,
igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
This game is similar to <a class="link" href="igraph-Games.html#igraph_cited_type_game" title="3.4. igraph_cited_type_game — Simulates a citation based on vertex types."><code class="function">igraph_cited_type_game()</code></a> but here the
category of the citing vertex is also considered.
</p>
<p>
An evolving citation network is modeled here, a single vertex and
its <em class="parameter"><code>edges_per_step</code></em> 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 <em class="parameter"><code>pref</code></em> 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 <code class="constant">i</code> and column <code class="constant">j</code> gives the
probability that a <code class="constant">j</code> vertex is cited, if the category of the
citing vertex is <code class="constant">i</code>.
</p>
<p>
Note that this function might generate networks with multiple edges
if <em class="parameter"><code>edges_per_step</code></em> is greater than one. You might want to call
<a class="link" href="igraph-Operators.html#igraph_simplify" title="3.11. igraph_simplify — Removes loop and/or multiple edges from the graph."><code class="function">igraph_simplify()</code></a> on the result to remove multiple edges.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the network.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>types</code></em>:</span></p></td>
<td><p>
A numeric vector of length <em class="parameter"><code>nodes</code></em>, containing the
categories of the vertices. The categories are numbered from
zero.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pref</code></em>:</span></p></td>
<td><p>
The preference matrix, a square matrix is required,
both the number of rows and columns should be the maximum
element in <em class="parameter"><code>types</code></em> plus one (types are numbered from zero).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>edges_per_step</code></em>:</span></p></td>
<td><p>
Integer constant, the number of edges to add
in each time step.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Boolean constant, whether to create a directed
network.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O((|V|+|E|)log|V|), |V| and |E| are number of
vertices and edges, respectively.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_forest_fire_game"></a>3.6. <code class="function">igraph_forest_fire_game</code> — Generates a network according to the <span class="quote">“<span class="quote">forest fire game</span>”</span>.</h3></div></div></div>
<a class="indexterm" name="id-1.13.5.8.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_forest_fire_game(igraph_t *graph, igraph_int_t nodes,
igraph_real_t fw_prob, igraph_real_t bw_factor,
igraph_int_t pambs, igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
The forest fire model intends to reproduce the following network
characteristics, observed in real networks:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem"><p>
Heavy-tailed in- and out-degree distributions.
</p></li>
<li class="listitem"><p>
Community structure.
</p></li>
<li class="listitem"><p>
Densification power-law. The network is densifying in time,
according to a power-law rule.
</p></li>
<li class="listitem"><p>
Shrinking diameter. The diameter of the network decreases in
time.
</p></li>
</ul></div>
<p>
</p>
<p>
The network is generated in the following way. One vertex is added at
a time. This vertex connects to (cites) <code class="literal">ambs</code> vertices already
present in the network, chosen uniformly random. Now, for each cited
vertex <code class="literal">v</code> we do the following procedure:
</p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem"><p>
We generate two random numbers, <code class="literal">x</code> and <code class="literal">y</code>, that are
geometrically distributed with means <code class="literal">p/(1-p)</code> and
<code class="literal">rp(1-rp)</code>. (<code class="literal">p</code> is <em class="parameter"><code>fw_prob</code></em>, <code class="literal">r</code> is
<em class="parameter"><code>bw_factor</code></em>.) The new vertex cites <code class="literal">x</code> outgoing neighbors
and <code class="literal">y</code> incoming neighbors of <code class="literal">v</code>, from those which are
not yet cited by the new vertex. If there are less than <code class="literal">x</code> or
<code class="literal">y</code> such vertices available then we cite all of them.
</p></li>
<li class="listitem"><p>
The same procedure is applied to all the newly cited
vertices.
</p></li>
</ol></div>
<p>
</p>
<p>
See also:
Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time:
densification laws, shrinking diameters and possible explanations.
<span class="emphasis"><em> KDD '05: Proceeding of the eleventh ACM SIGKDD international
conference on Knowledge discovery in data mining </em></span>, 177--187, 2005.
</p>
<p>
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
<a class="ulink" href="https://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf" target="_top">https://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf</a>, our
implementation is based on this.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>fw_prob</code></em>:</span></p></td>
<td><p>
The forward burning probability.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>bw_factor</code></em>:</span></p></td>
<td><p>
The backward burning ratio. The backward burning
probability is calculated as <code class="literal">bw_factor * fw_prob</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>pambs</code></em>:</span></p></td>
<td><p>
The number of ambassador vertices.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to create a directed graph.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: TODO.
</p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="degree-constrained-games"></a>4. Degree-constrained models</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#igraph_degree_sequence_game">4.1. <code class="function">igraph_degree_sequence_game</code> — Generates a random graph with a given degree sequence.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_k_regular_game">4.2. <code class="function">igraph_k_regular_game</code> — Generates a random graph where each vertex has the same degree.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_rewire">4.3. <code class="function">igraph_rewire</code> — Randomly rewires a graph while preserving its degree sequence.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_chung_lu_game">4.4. <code class="function">igraph_chung_lu_game</code> — Samples graphs from the Chung-Lu model.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_static_fitness_game">4.5. <code class="function">igraph_static_fitness_game</code> — Non-growing random graph with edge probabilities proportional to node fitness scores.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_static_power_law_game">4.6. <code class="function">igraph_static_power_law_game</code> — Generates a non-growing random graph with expected power-law degree distributions.</a></span></dt>
</dl></div>
<p>Random graph models with hard or soft degree constraints.</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_degree_sequence_game"></a>4.1. <code class="function">igraph_degree_sequence_game</code> — Generates a random graph with a given degree sequence.</h3></div></div></div>
<a class="indexterm" name="id-1.13.6.3.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_degree_sequence_game(
igraph_t *graph,
const igraph_vector_int_t *out_degrees,
const igraph_vector_int_t *in_degrees,
igraph_degseq_t method);
</pre></div>
<p>
</p>
<p>
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.
</p>
<p>
References:
</p>
<p>
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).
<a class="ulink" href="https://doi.org/10.1093/comnet/cnv013" target="_top">https://doi.org/10.1093/comnet/cnv013</a>.
</p>
<p>
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).
<a class="ulink" href="https://doi.org/10.1088/2632-072x/abced5" target="_top">https://doi.org/10.1088/2632-072x/abced5</a>.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>out_degrees</code></em>:</span></p></td>
<td><p>
A vector of integers specifying the degree sequence for
undirected graphs or the out-degree sequence for directed graphs.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>in_degrees</code></em>:</span></p></td>
<td><p>
A vector of integers specifying the in-degree sequence for
directed graphs. For undirected graphs, it must be <code class="constant">NULL</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>method</code></em>:</span></p></td>
<td>
<p>
The method to generate the graph. Possible values:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_DEGSEQ_CONFIGURATION</code></span></p></td>
<td><p>
This method implements the configuration model.
For undirected graphs, it puts all vertex IDs in a bag
such that the multiplicity of a vertex in the bag is the same as
its degree. Then it draws pairs from the bag until the bag becomes
empty. This method may generate both loop (self) edges and multiple
edges. For directed graphs, the algorithm is basically the same,
but two separate bags are used for the in- and out-degrees.
Undirected graphs are generated with probability proportional to
<code class="literal">(\prod_{i&lt;j} A_{ij} ! \prod_i A_{ii} !!)^{-1}</code>,
where <code class="constant">A</code> denotes the adjacency matrix and <code class="literal">!!</code> denotes
the double factorial. Here <code class="constant">A</code> is assumed to have twice the number of
self-loops on its diagonal.
The corresponding expression for directed graphs is
<code class="literal">(\prod_{i,j} A_{ij}!)^{-1}</code>.
Thus the probability of all simple graphs (which only have 0s and 1s
in the adjacency matrix) is the same, while that of
non-simple ones depends on their edge and self-loop multiplicities.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_DEGSEQ_CONFIGURATION_SIMPLE</code></span></p></td>
<td><p>
This method is identical to <code class="constant">IGRAPH_DEGSEQ_CONFIGURATION</code>, but if the
generated graph is not simple, it rejects it and re-starts the
generation. It generates all simple graphs with the same probability.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE</code></span></p></td>
<td><p>
This method generates simple graphs.
It is similar to <code class="constant">IGRAPH_DEGSEQ_CONFIGURATION</code>
but tries to avoid multiple and loop edges and restarts the
generation from scratch if it gets stuck. It can generate all simple
realizations of a degree sequence, but it is not guaranteed
to sample them uniformly. This method is relatively fast and it will
eventually succeed if the provided degree sequence is graphical,
but there is no upper bound on the number of iterations.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE</code></span></p></td>
<td><p>
This is an MCMC sampler based on degree-preserving edge switches.
It generates simple undirected or directed graphs.
It uses <a class="link" href="igraph-Generators.html#igraph_realize_degree_sequence" title="6.1. igraph_realize_degree_sequence — Generates a graph with the given degree sequence."><code class="function">igraph_realize_degree_sequence()</code></a> to construct an initial
graph, then rewires it using <a class="link" href="igraph-Games.html#igraph_rewire" title="4.3. igraph_rewire — Randomly rewires a graph while preserving its degree sequence."><code class="function">igraph_rewire()</code></a>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_DEGSEQ_VL</code></span></p></td>
<td><p>
This method samples undirected <span class="emphasis"><em>connected</em></span> graphs approximately
uniformly. It is a Monte Carlo method based on degree-preserving
edge switches.
This generator should be favoured if undirected and connected
graphs are to be generated and execution time is not a concern.
igraph uses the original implementation of Fabien Viger; for the algorithm,
see <a class="ulink" href="https://www-complexnetworks.lip6.fr/~latapy/FV/generation.html" target="_top">https://www-complexnetworks.lip6.fr/~latapy/FV/generation.html</a>
and the paper <a class="ulink" href="https://arxiv.org/abs/cs/0502085" target="_top">https://arxiv.org/abs/cs/0502085</a>
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough
memory to perform the operation.
<code class="constant">IGRAPH_EINVAL</code>: invalid method parameter, or
invalid in- and/or out-degree vectors. The degree vectors
should be non-negative, <em class="parameter"><code>out_deg</code></em> should sum
up to an even integer for undirected graphs; the length
and sum of <em class="parameter"><code>out_deg</code></em> and
<em class="parameter"><code>in_deg</code></em>
should match for directed graphs.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges
for <code class="constant">IGRAPH_DEGSEQ_CONFIGURATION</code> and <code class="constant">IGRAPH_DEGSEQ_EDGE_SWITCHING_SIMPLE</code>.
The time complexity of the other modes is not known.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Structural.html#igraph_is_graphical" title="10.1. igraph_is_graphical — Is there a graph with the given degree sequence?"><code class="function">igraph_is_graphical()</code></a> to determine if there exist graphs with a certain
degree sequence; <a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnm" title="1.1. igraph_erdos_renyi_game_gnm — Generates a random (Erdős-Rényi) graph with a fixed number of edges."><code class="function">igraph_erdos_renyi_game_gnm()</code></a> to generate graphs with a
fixed number of edges, without any degree constraints; <a class="link" href="igraph-Games.html#igraph_chung_lu_game" title="4.4. igraph_chung_lu_game — Samples graphs from the Chung-Lu model."><code class="function">igraph_chung_lu_game()</code></a>
and <a class="link" href="igraph-Games.html#igraph_static_fitness_game" title="4.5. igraph_static_fitness_game — Non-growing random graph with edge probabilities proportional to node fitness scores."><code class="function">igraph_static_fitness_game()</code></a> to sample random graphs with a prescribed
<span class="emphasis"><em>expected</em></span> degree sequence (but variable actual degrees);
<a class="link" href="igraph-Generators.html#igraph_realize_degree_sequence" title="6.1. igraph_realize_degree_sequence — Generates a graph with the given degree sequence."><code class="function">igraph_realize_degree_sequence()</code></a> and <a class="link" href="igraph-Generators.html#igraph_realize_bipartite_degree_sequence" title="6.2. igraph_realize_bipartite_degree_sequence — Generates a bipartite graph with the given bidegree sequence."><code class="function">igraph_realize_bipartite_degree_sequence()</code></a>
to generate a single (non-random) graph with given degrees.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<div class="hideshow" onClick="toggle(this, event)">
<div class="example">
<a name="id-1.13.6.3.13.1"></a><p class="title"><b>Example 12.5.  File <code class="code">examples/simple/igraph_degree_sequence_game.c</code></b></p>
<div class="example-contents">
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> &lt;igraph.h&gt;
int <span class="strong"><strong>main</strong></span>(void) {
igraph_t g;
igraph_vector_int_t outdeg, indeg;
igraph_vector_int_t vec;
igraph_bool_t is_simple;
<span class="emphasis"><em>/* Initialize the library. */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
<span class="emphasis"><em>/* Set random seed for reproducibility */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_seed" title="3.3. igraph_rng_seed — Seeds a random number generator.">igraph_rng_seed</a></strong></span>(<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_default" title="2.1. igraph_rng_default — Query the default random number generator.">igraph_rng_default</a></strong></span>(), 42);
<span class="strong"><strong>igraph_vector_int_init_int</strong></span>(&amp;outdeg, 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3);
<span class="strong"><strong>igraph_vector_int_init_int</strong></span>(&amp;indeg, 10, 4, 4, 2, 2, 4, 4, 2, 2, 3, 3);
<span class="strong"><strong>igraph_vector_int_init</strong></span>(&amp;vec, 0);
<span class="emphasis"><em>/* checking the configuration model, undirected graphs */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence.">igraph_degree_sequence_game</a></strong></span>(&amp;g, &amp;outdeg, 0, IGRAPH_DEGSEQ_CONFIGURATION);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g) || <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 10) {
<span class="strong"><strong>return</strong></span> 1;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_OUT, IGRAPH_LOOPS)) {
<span class="strong"><strong>return</strong></span> 2;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* checking the Viger-Latapy method, undirected graphs */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence.">igraph_degree_sequence_game</a></strong></span>(&amp;g, &amp;outdeg, 0, IGRAPH_DEGSEQ_VL);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g) || <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 10) {
<span class="strong"><strong>return</strong></span> 3;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph.">igraph_is_simple</a></strong></span>(&amp;g, &amp;is_simple, IGRAPH_DIRECTED) || !is_simple) {
<span class="strong"><strong>return</strong></span> 4;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_OUT, IGRAPH_NO_LOOPS)) {
<span class="strong"><strong>return</strong></span> 5;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* checking the configuration model, directed graphs */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence.">igraph_degree_sequence_game</a></strong></span>(&amp;g, &amp;outdeg, &amp;indeg, IGRAPH_DEGSEQ_CONFIGURATION);
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g) || <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 10) {
<span class="strong"><strong>return</strong></span> 6;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_OUT, IGRAPH_LOOPS)) {
<span class="strong"><strong>return</strong></span> 7;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_IN, IGRAPH_LOOPS)) {
<span class="strong"><strong>return</strong></span> 8;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* checking the fast heuristic method, undirected graphs */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence.">igraph_degree_sequence_game</a></strong></span>(&amp;g, &amp;outdeg, 0, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g) || <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 10) {
<span class="strong"><strong>return</strong></span> 9;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph.">igraph_is_simple</a></strong></span>(&amp;g, &amp;is_simple, IGRAPH_DIRECTED) || !is_simple) {
<span class="strong"><strong>return</strong></span> 10;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_OUT, IGRAPH_LOOPS)) {
<span class="strong"><strong>return</strong></span> 11;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="emphasis"><em>/* checking the fast heuristic method, directed graphs */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence.">igraph_degree_sequence_game</a></strong></span>(&amp;g, &amp;outdeg, &amp;indeg, IGRAPH_DEGSEQ_FAST_HEUR_SIMPLE);
<span class="strong"><strong>if</strong></span> (!<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_is_directed" title="5.2.3. igraph_is_directed — Is this a directed graph?">igraph_is_directed</a></strong></span>(&amp;g) || <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_vcount" title="5.2.1. igraph_vcount — The number of vertices in a graph.">igraph_vcount</a></strong></span>(&amp;g) != 10) {
<span class="strong"><strong>return</strong></span> 12;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_is_simple" title="20.1. igraph_is_simple — Decides whether the input graph is a simple graph.">igraph_is_simple</a></strong></span>(&amp;g, &amp;is_simple, IGRAPH_DIRECTED) || !is_simple) {
<span class="strong"><strong>return</strong></span> 13;
}
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_OUT, IGRAPH_LOOPS)) {
<span class="strong"><strong>return</strong></span> 14;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong>if</strong></span> (<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_degree" title="5.2.14. igraph_degree — The degree of some vertices in a graph.">igraph_degree</a></strong></span>(&amp;g, &amp;vec, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_vss_all" title="4.1. igraph_vss_all — All vertices of a graph (immediate version).">igraph_vss_all</a></strong></span>(), IGRAPH_IN, IGRAPH_LOOPS)) {
<span class="strong"><strong>return</strong></span> 15;
}
<span class="strong"><strong>igraph_vector_int_print</strong></span>(&amp;vec);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;g);
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;vec);
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;outdeg);
<span class="strong"><strong>igraph_vector_int_destroy</strong></span>(&amp;indeg);
<span class="strong"><strong>return</strong></span> 0;
}
</pre>
<p></p>
</div>
</div>
<br class="example-break">
</div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_k_regular_game"></a>4.2. <code class="function">igraph_k_regular_game</code> — Generates a random graph where each vertex has the same degree.</h3></div></div></div>
<a class="indexterm" name="id-1.13.6.4.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_k_regular_game(igraph_t *graph,
igraph_int_t no_of_nodes, igraph_int_t k,
igraph_bool_t directed, igraph_bool_t multiple);
</pre></div>
<p>
</p>
<p>
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.
</p>
<p>
Currently, this game simply uses <a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game</code></a> with
the <code class="constant">IGRAPH_DEGSEQ_CONFIGURATION</code> or the <code class="constant">IGRAPH_DEGSEQ_FAST_SIMPLE</code>
method and appropriately constructed degree sequences.
Thefore, it does not sample uniformly: while it can generate all k-regular
graphs with the given number of vertices, it does not generate each one with
the same probability.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>no_of_nodes</code></em>:</span></p></td>
<td><p>
The number of nodes in the generated graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>k</code></em>:</span></p></td>
<td><p>
The degree of each vertex in an undirected graph, or
the out-degree and in-degree of each vertex in a
directed graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether the generated graph will be directed.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>multiple</code></em>:</span></p></td>
<td><p>
Whether to allow multiple edges in the generated graph.</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid parameter; e.g., negative number of nodes,
or odd number of nodes and odd k for undirected
graphs.
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|) if <code class="constant">multiple</code> is true, otherwise not known.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_rewire"></a>4.3. <code class="function">igraph_rewire</code> — Randomly rewires a graph while preserving its degree sequence.</h3></div></div></div>
<a class="indexterm" name="id-1.13.6.5.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_rewire(igraph_t *graph, igraph_int_t n, igraph_edge_type_sw_t allowed_edge_types, igraph_rewiring_stats_t *stats);
</pre></div>
<p>
</p>
<p>
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 <a class="link" href="igraph-Basic.html#igraph_copy" title="5.1.3. igraph_copy — Creates an exact (deep) copy of a graph."><code class="function">igraph_copy()</code></a>
beforehand. All graph attributes will be lost.
</p>
<p>
The rewiring is performed with degree-preserving edge switches:
Two arbitrary edges are picked uniformly at random, namely
<code class="literal">(a, b)</code> and <code class="literal">(c, d)</code>, then they are replaced
by <code class="literal">(a, d)</code> and <code class="literal">(b, c)</code> if this preserves the
constraints specified by <em class="parameter"><code>mode</code></em>.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The graph object to be rewired.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
Number of rewiring trials to perform.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td>
<p>
The types of edges that rewiring may create in the graph.
See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a> for details.
Currently, the following are implemented:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_SIMPLE_SW</code></span></p></td>
<td><p>
simple graphs (i.e. no self-loops or multi-edges allowed).
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_SW</code></span></p></td>
<td><p>
single self-loops are allowed, but not multi-edges.
</p></td>
</tr>
</tbody>
</table></div>
<p>
Multigraphs are not yet supported.
</p>
</td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>stats</code></em>:</span></p></td>
<td><p>
Counts of the number of different operations
performed by the algorithm are stored here.</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td>
<p>
Error code:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_EINVMODE</code></span></p></td>
<td><p>
Invalid rewiring mode.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_ENOMEM</code></span></p></td>
<td><p>
Not enough memory for temporary data.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</td>
</tr></tbody>
</table></div>
<p>
Time complexity: TODO.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_chung_lu_game"></a>4.4. <code class="function">igraph_chung_lu_game</code> — Samples graphs from the Chung-Lu model.</h3></div></div></div>
<a class="indexterm" name="id-1.13.6.6.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
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);
</pre></div>
<p>
</p>
<p>
</p>
<div class="warning" style="margin-left: 0.5in; margin-right: 0.5in;">
<h3 class="title">Warning</h3>
<p>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.</p>
</div>
<p>The Chung-Lu 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.
</p>
<p>
In the original Chung-Lu model, each pair of vertices <code class="constant">i</code> and <code class="constant">j</code> is
connected with independent probability <code class="literal">p_ij = w_i w_j / S</code>,
where <code class="constant">w_i</code> is a weight associated with vertex <code class="constant">i</code> and
<code class="literal">S = sum_k w_k</code> is the sum of weights. In the directed variant,
vertices have both out-weights, <code class="literal">w^out</code>, and in-weights,
<code class="literal">w^in</code>, with equal sums,
<code class="literal">S = sum_k w^out_k = sum_k w^in_k</code>.
The connection probability between <code class="constant">i</code> and <code class="constant">j</code> is
<code class="literal">p_ij = w^out_i w^in_j / S</code>.
</p>
<p>
This model is commonly used to create random graphs with a fixed <span class="emphasis"><em>expected</em></span>
degree sequence. The expected degree of vertex <code class="constant">i</code> is approximately equal
to the weight <code class="constant">w_i</code>. Specifically, if the graph is directed and self-loops
are allowed, then the expected out- and in-degrees are precisely
<code class="literal">w^out</code> and <code class="literal">w^in</code>. If self-loops are disallowed,
then the expected out- and in-degrees are <code class="literal">w^out (S - w^in) / S</code>
and <code class="literal">w^in (S - w^out) / S</code>, respectively. If the graph is
undirected, then the expected degrees with and without self-loops are
<code class="literal">w (S + w) / S</code> and <code class="literal">w (S - w) / S</code>, respectively.
</p>
<p>
A limitation of the original Chung-Lu model is that when some of the
weights are large, the formula for <code class="constant">p_ij</code> yields values larger than 1.
Chung and Lu's original paper excludes the use of such weights. When
<code class="literal">p_ij &gt; 1</code>, this function simply issues a warning and creates
a connection between <code class="constant">i</code> and <code class="constant">j</code>. However, in this case the expected degrees
will no longer relate to the weights in the manner stated above. Thus the
original Chung-Lu model cannot produce certain (large) expected degrees.
</p>
<p>
The overcome this limitation, this function implements additional variants of
the model, with modified expressions for the connection probability <code class="constant">p_ij</code>
between vertices <code class="constant">i</code> and <code class="constant">j</code>. Let <code class="literal">q_ij = w_i w_j / S</code>, or
<code class="literal">q_ij = w^out_i w^in_j / S</code> in the directed case. All model
variants become equivalent in the limit of sparse graphs where <code class="constant">q_ij</code>
approaches zero. In the original Chung-Lu model, selectable by setting
<em class="parameter"><code>variant</code></em> to <code class="constant">IGRAPH_CHUNG_LU_ORIGINAL</code>, <code class="literal">p_ij = min(q_ij, 1)</code>.
The <code class="constant">IGRAPH_CHUNG_LU_MAXENT</code> variant, sometiems referred to a the generalized
random graph, uses <code class="literal">p_ij = q_ij / (1 + q_ij)</code>, 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 <code class="literal">exp(-Theta_ij) = w_i w_j / S</code>. This model is also
discussed by Britton, Deijfen and Martin-Löf (2006). By virtue of being
a degree-constrained maximum entropy model, it produces graphs with the
same degree sequence with the same probability.
A third variant can be requested with <code class="constant">IGRAPH_CHUNG_LU_NR</code>, and uses
<code class="literal">p_ij = 1 - exp(-q_ij)</code>. 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).
</p>
<p>
References:
</p>
<p>
Chung F and Lu L: Connected components in a random graph with given
degree sequences. Annals of Combinatorics 6, 125-145 (2002).
<a class="ulink" href="https://doi.org/10.1007/PL00012580" target="_top">https://doi.org/10.1007/PL00012580</a>
</p>
<p>
Miller JC and Hagberg A:
Efficient Generation of Networks with Given Expected Degrees (2011).
<a class="ulink" href="https://doi.org/10.1007/978-3-642-21286-4_10" target="_top">https://doi.org/10.1007/978-3-642-21286-4_10</a>
</p>
<p>
Park J and Newman MEJ: Statistical mechanics of networks.
Physical Review E 70, 066117 (2004).
<a class="ulink" href="https://doi.org/10.1103/PhysRevE.70.066117" target="_top">https://doi.org/10.1103/PhysRevE.70.066117</a>
</p>
<p>
Britton T, Deijfen M, Martin-Löf A:
Generating Simple Random Graphs with Prescribed Degree Distribution.
J Stat Phys 124, 1377–1397 (2006).
<a class="ulink" href="https://doi.org/10.1007/s10955-006-9168-x" target="_top">https://doi.org/10.1007/s10955-006-9168-x</a>
</p>
<p>
Norros I and Reittu H: On a conditionally Poissonian graph process.
Advances in Applied Probability 38, 59–75 (2006).
<a class="ulink" href="https://doi.org/10.1239/aap/1143936140" target="_top">https://doi.org/10.1239/aap/1143936140</a>
</p>
<p>
Bollobás B, Janson S, Riordan O:
The phase transition in inhomogeneous random graphs.
Random Struct Algorithms 31, 3–122 (2007).
<a class="ulink" href="https://doi.org/10.1002/rsa.20168" target="_top">https://doi.org/10.1002/rsa.20168</a>
</p>
<p>
Van Der Hofstad R: Critical behavior in inhomogeneous random graphs.
Random Struct Algorithms 42, 480–508 (2013).
<a class="ulink" href="https://doi.org/10.1002/rsa.20450" target="_top">https://doi.org/10.1002/rsa.20450</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>out_weights</code></em>:</span></p></td>
<td><p>
A vector of non-negative vertex weights (or out-weights).
In sparse graphs these will be approximately equal to the expected
(out-)degrees.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>in_weights</code></em>:</span></p></td>
<td><p>
A vector of non-negative in-weights, approximately equal
to the expected in-degrees in sparse graphs. May be set to <code class="constant">NULL</code>,
in which case undirected graphs are generated.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
<td><p>
Whether to allow the creation of self-loops. Since vertex
pairs are connected independently, setting this to false is equivalent
to simply discarding self-loops from an existing loopy Chung-Lu graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>variant</code></em>:</span></p></td>
<td>
<p>
The model variant to sample from, with different definitions
of the connection probability between vertices <code class="constant">i</code> and <code class="constant">j</code>. Given
<code class="literal">q_ij = w_i w_j / S</code>, the following formulations are available:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_CHUNG_LU_ORIGINAL</code></span></p></td>
<td><p>
the original Chung-Lu model, <code class="literal">p_ij = min(q_ij, 1)</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_CHUNG_LU_MAXENT</code></span></p></td>
<td><p>
maximum entropy model with fixed expected degrees,
<code class="literal">p_ij = q_ij / (1 + q_ij)</code>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_CHUNG_LU_NR</code></span></p></td>
<td><p>
Norros and Reittu's model, <code class="literal">p_ij = 1 - exp(-q_ij)</code>.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_static_fitness_game" title="4.5. igraph_static_fitness_game — Non-growing random graph with edge probabilities proportional to node fitness scores."><code class="function">igraph_static_fitness_game()</code></a> implements a similar model with
a sharp constraint on the number of edges;
<a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game()</code></a> samples random graphs with sharply
specified degrees; <a class="link" href="igraph-Games.html#igraph_erdos_renyi_game_gnp" title="1.2. igraph_erdos_renyi_game_gnp — Generates a random (Erdős-Rényi) graph with fixed edge probabilities."><code class="function">igraph_erdos_renyi_game_gnp()</code></a> creates random
graphs with a fixed connection probability <code class="constant">p</code> between all vertex pairs.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|E| + |V|), linear in the number of edges.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_static_fitness_game"></a>4.5. <code class="function">igraph_static_fitness_game</code> — Non-growing random graph with edge probabilities proportional to node fitness scores.</h3></div></div></div>
<a class="indexterm" name="id-1.13.6.7.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_static_fitness_game(igraph_t *graph, igraph_int_t no_of_edges,
const igraph_vector_t *fitness_out, const igraph_vector_t *fitness_in,
igraph_edge_type_sw_t allowed_edge_types);
</pre></div>
<p>
</p>
<p>
This game generates a directed or undirected random graph where the
probability of an edge between vertices <code class="constant">i</code> and <code class="constant">j</code> 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 in-fitness, and the probability of an edge from <code class="constant">i</code> to <code class="constant">j</code> depends on
the out-fitness of vertex <code class="constant">i</code> and the in-fitness of vertex <code class="constant">j</code>.
</p>
<p>
The generation process goes as follows. We start from <code class="constant">N</code> disconnected nodes
(where <code class="constant">N</code> is given by the length of the fitness vector). Then we randomly
select two vertices <code class="constant">i</code> and <code class="constant">j</code>, with probabilities proportional to their
fitnesses. (When the generated graph is directed, <code class="constant">i</code> is selected according to
the out-fitnesses and <code class="constant">j</code> is selected according to the in-fitnesses). 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.
</p>
<p>
The <span class="emphasis"><em>expected</em></span> degree (though not the actual degree) of each vertex will be
proportional to its fitness. This is exactly true when self-loops and multi-edges
are allowed, and approximately true otherwise. If you need to generate a graph
with an exact degree sequence, consider <a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game()</code></a> and
<a class="link" href="igraph-Generators.html#igraph_realize_degree_sequence" title="6.1. igraph_realize_degree_sequence — Generates a graph with the given degree sequence."><code class="function">igraph_realize_degree_sequence()</code></a> instead.
</p>
<p>
To generate random undirected graphs with a given expected degree sequence, set
<em class="parameter"><code>fitness_out</code></em> (and in the directed case <em class="parameter"><code>fitness_out</code></em>) to the desired expected
degrees, and <em class="parameter"><code>no_of_edges</code></em> to the corresponding edge count, i.e. half the sum of
expected degrees in the undirected case, and the sum of out- or in-degrees in the
directed case.
</p>
<p>
This model is similar to the better-known Chung-Lu model, implemented in igraph
as <a class="link" href="igraph-Games.html#igraph_chung_lu_game" title="4.4. igraph_chung_lu_game — Samples graphs from the Chung-Lu model."><code class="function">igraph_chung_lu_game()</code></a>, but with a sharply fixed edge count.
</p>
<p>
This model is commonly used to generate static scale-free networks. To
achieve this, you have to draw the fitness scores from the desired power-law
distribution. Alternatively, you may use <a class="link" href="igraph-Games.html#igraph_static_power_law_game" title="4.6. igraph_static_power_law_game — Generates a non-growing random graph with expected power-law degree distributions."><code class="function">igraph_static_power_law_game()</code></a>
which generates the fitnesses for you with a given exponent.
</p>
<p>
Reference:
</p>
<p>
Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution
in scale-free networks. Phys Rev Lett 87(27):278701, 2001
<a class="ulink" href="https://doi.org/10.1103/PhysRevLett.87.278701" target="_top">https://doi.org/10.1103/PhysRevLett.87.278701</a>.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>no_of_edges</code></em>:</span></p></td>
<td><p>
The number of edges in the generated graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>fitness_out</code></em>:</span></p></td>
<td><p>
A numeric vector containing the fitness of each vertex.
For directed graphs, this specifies the out-fitness
of each vertex.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>fitness_in</code></em>:</span></p></td>
<td><p>
If <code class="constant">NULL</code>, the generated graph will be undirected.
If not <code class="constant">NULL</code>, this argument specifies the in-fitness
of each vertex.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are allowed in the generated graph. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid parameter
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough
memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_static_power_law_game" title="4.6. igraph_static_power_law_game — Generates a non-growing random graph with expected power-law degree distributions."><code class="function">igraph_static_power_law_game()</code></a>, <a class="link" href="igraph-Games.html#igraph_chung_lu_game" title="4.4. igraph_chung_lu_game — Samples graphs from the Chung-Lu model."><code class="function">igraph_chung_lu_game()</code></a>,
<a class="link" href="igraph-Games.html#igraph_degree_sequence_game" title="4.1. igraph_degree_sequence_game — Generates a random graph with a given degree sequence."><code class="function">igraph_degree_sequence_game()</code></a>
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V| + |E| log |E|).
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_static_power_law_game"></a>4.6. <code class="function">igraph_static_power_law_game</code> — Generates a non-growing random graph with expected power-law degree distributions.</h3></div></div></div>
<a class="indexterm" name="id-1.13.6.8.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_static_power_law_game(igraph_t *graph,
igraph_int_t no_of_nodes, igraph_int_t no_of_edges,
igraph_real_t exponent_out, igraph_real_t exponent_in,
igraph_edge_type_sw_t allowed_edge_types,
igraph_bool_t finite_size_correction);
</pre></div>
<p>
</p>
<p>
This game generates a directed or undirected random graph where the
degrees of vertices follow power-law distributions with prescribed
exponents. For directed graphs, the exponents of the in- and out-degree
distributions may be specified separately.
</p>
<p>
The game simply uses <a class="link" href="igraph-Games.html#igraph_static_fitness_game" title="4.5. igraph_static_fitness_game — Non-growing random graph with edge probabilities proportional to node fitness scores."><code class="function">igraph_static_fitness_game()</code></a> with appropriately
constructed fitness vectors. In particular, the fitness of vertex <code class="constant">i</code>
is <code class="literal">i^(-alpha)</code>, where <code class="literal">alpha = 1/(gamma-1)</code>
and <code class="constant">gamma</code> is the exponent given in the arguments.
</p>
<p>
To remove correlations between in- and out-degrees in case of directed
graphs, the in-fitness vector will be shuffled after it has been set up
and before <a class="link" href="igraph-Games.html#igraph_static_fitness_game" title="4.5. igraph_static_fitness_game — Non-growing random graph with edge probabilities proportional to node fitness scores."><code class="function">igraph_static_fitness_game()</code></a> is called.
</p>
<p>
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 <code class="constant">i</code> is
<code class="literal">(i+i0-1)^(-alpha)</code>,
where <code class="constant">i0</code> 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.
</p>
<p>
References:
</p>
<p>
Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution
in scale-free networks. Phys Rev Lett 87(27):278701, 2001.
<a class="ulink" href="https://doi.org/10.1103/PhysRevLett.87.278701" target="_top">https://doi.org/10.1103/PhysRevLett.87.278701</a>
</p>
<p>
Chung F and Lu L: Connected components in a random graph with given
degree sequences. Annals of Combinatorics 6, 125-145, 2002.
<a class="ulink" href="https://doi.org/10.1007/PL00012580" target="_top">https://doi.org/10.1007/PL00012580</a>
</p>
<p>
Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in
scale-free networks under the Achlioptas process. Phys Rev Lett
103:135702, 2009.
<a class="ulink" href="https://doi.org/10.1103/PhysRevLett.103.135702" target="_top">https://doi.org/10.1103/PhysRevLett.103.135702</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>no_of_nodes</code></em>:</span></p></td>
<td><p>
The number of nodes in the generated graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>no_of_edges</code></em>:</span></p></td>
<td><p>
The number of edges in the generated graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>exponent_out</code></em>:</span></p></td>
<td><p>
The power law exponent of the degree distribution.
For directed graphs, this specifies the exponent of the
out-degree distribution. It must be greater than or
equal to 2. If you pass <code class="constant">IGRAPH_INFINITY</code> here, you
will get back an Erdős-Rényi random network.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>exponent_in</code></em>:</span></p></td>
<td><p>
If negative, the generated graph will be undirected.
If greater than or equal to 2, this argument specifies
the exponent of the in-degree distribution. If
non-negative but less than 2, an error will be
generated.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are allowed in the generated graph. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>finite_size_correction</code></em>:</span></p></td>
<td><p>
Whether to use the proposed finite size
correction of Cho et al.</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid parameter
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough
memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V| + |E| log |E|).
</p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="edge-rewiring-games"></a>5. Edge rewiring models</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#igraph_watts_strogatz_game">5.1. <code class="function">igraph_watts_strogatz_game</code> — The Watts-Strogatz small-world model.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_rewire_edges">5.2. <code class="function">igraph_rewire_edges</code> — Rewires the edges of a graph with constant probability.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_rewire_directed_edges">5.3. <code class="function">igraph_rewire_directed_edges</code> — Rewires the chosen endpoint of directed edges.</a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_watts_strogatz_game"></a>5.1. <code class="function">igraph_watts_strogatz_game</code> — The Watts-Strogatz small-world model.</h3></div></div></div>
<a class="indexterm" name="id-1.13.7.2.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_watts_strogatz_game(
igraph_t *graph, igraph_int_t dim,
igraph_int_t size, igraph_int_t nei,
igraph_real_t p,
igraph_edge_type_sw_t allowed_edge_types);
</pre></div>
<p>
</p>
<p>
This function generates networks with the small-world property
based on a variant of the Watts-Strogatz model. The network is obtained
by first creating a periodic undirected lattice, then rewiring both
endpoints of each edge with probability <em class="parameter"><code>p</code></em>, while avoiding the
creation of multi-edges.
</p>
<p>
This process differs from the original model of Watts and Strogatz
(see reference) in that it rewires <span class="emphasis"><em>both</em></span> endpoints of edges. Thus in
the limit of <code class="literal">p=1</code>, we obtain a G(n,m) random graph with the
same number of vertices and edges as the original lattice. In comparison,
the original Watts-Strogatz model only rewires a single endpoint of each edge,
thus the network does not become fully random even for <code class="literal">p=1</code>.
For appropriate choices of <em class="parameter"><code>p</code></em>, both models exhibit the property of
simultaneously having short path lengths and high clustering.
</p>
<p>
Reference:
</p>
<p>
Duncan J Watts and Steven H Strogatz:
Collective dynamics of <span class="quote">“<span class="quote">small world</span>”</span> networks,
Nature 393, 440-442, 1998.
<a class="ulink" href="https://doi.org/10.1038/30918" target="_top">https://doi.org/10.1038/30918</a>
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The graph to initialize.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>dim</code></em>:</span></p></td>
<td><p>
The dimension of the lattice.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>size</code></em>:</span></p></td>
<td><p>
The size of the lattice along each dimension.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nei</code></em>:</span></p></td>
<td><p>
The size of the neighborhood for each vertex. This is
the same as the <em class="parameter"><code>order</code></em> argument of <a class="link" href="igraph-Operators.html#igraph_connect_neighborhood" title="3.1. igraph_connect_neighborhood — Connects each vertex to its neighborhood."><code class="function">igraph_connect_neighborhood()</code></a>.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>p</code></em>:</span></p></td>
<td><p>
The rewiring probability. A real number between zero and
one (inclusive).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are allowed in the generated graph. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Generators.html#igraph_square_lattice" title="4.4. igraph_square_lattice — Arbitrary dimensional square lattices."><code class="function">igraph_square_lattice()</code></a>, <a class="link" href="igraph-Operators.html#igraph_connect_neighborhood" title="3.1. igraph_connect_neighborhood — Connects each vertex to its neighborhood."><code class="function">igraph_connect_neighborhood()</code></a> and
<a class="link" href="igraph-Games.html#igraph_rewire_edges" title="5.2. igraph_rewire_edges — Rewires the edges of a graph with constant probability."><code class="function">igraph_rewire_edges()</code></a> can be used if more flexibility is
needed, e.g. a different type of lattice.
</p></td>
</tr></tbody>
</table></div>
<p>
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 <em class="parameter"><code>nei</code></em>
argument.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_rewire_edges"></a>5.2. <code class="function">igraph_rewire_edges</code> — Rewires the edges of a graph with constant probability.</h3></div></div></div>
<a class="indexterm" name="id-1.13.7.3.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_rewire_edges(igraph_t *graph, igraph_real_t prob,
igraph_edge_type_sw_t allowed_edge_types);
</pre></div>
<p>
</p>
<p>
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 <em class="parameter"><code>prob</code></em>.
</p>
<p> Note that this function modifies the input <em class="parameter"><code>graph</code></em>,
call <a class="link" href="igraph-Basic.html#igraph_copy" title="5.1.3. igraph_copy — Creates an exact (deep) copy of a graph."><code class="function">igraph_copy()</code></a> if you want to keep it.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The input graph, this will be rewired, it can be
directed or undirected.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>prob</code></em>:</span></p></td>
<td><p>
The rewiring probability a constant between zero and
one (inclusive).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>allowed_edge_types</code></em>:</span></p></td>
<td><p>
Controls whether multi-edges and self-loops
are allowed in the new graph. See <a class="link" href="igraph-Games.html#igraph_edge_type_sw_t" title="7.1. igraph_edge_type_sw_t — What types of non-simple edges to allow?"><code class="function">igraph_edge_type_sw_t</code></a>.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_watts_strogatz_game" title="5.1. igraph_watts_strogatz_game — The Watts-Strogatz small-world model."><code class="function">igraph_watts_strogatz_game()</code></a> uses this function for the
rewiring.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|).
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_rewire_directed_edges"></a>5.3. <code class="function">igraph_rewire_directed_edges</code> — Rewires the chosen endpoint of directed edges.</h3></div></div></div>
<a class="indexterm" name="id-1.13.7.4.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_rewire_directed_edges(igraph_t *graph, igraph_real_t prob,
igraph_bool_t loops, igraph_neimode_t mode);
</pre></div>
<p>
</p>
<p>
This function rewires either the start or end of directed edges in a graph
with a constant probability. Correspondingly, either the in-degree sequence
or the out-degree sequence of the graph will be preserved.
</p>
<p> Note that this function modifies the input <em class="parameter"><code>graph</code></em>,
call <a class="link" href="igraph-Basic.html#igraph_copy" title="5.1.3. igraph_copy — Creates an exact (deep) copy of a graph."><code class="function">igraph_copy()</code></a> if you want to keep it.
</p>
<p> This function can produce multiple edges between two vertices.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The input graph, this will be rewired, it can be
directed or undirected. If it is undirected or <em class="parameter"><code>mode</code></em> is set to
IGRAPH_ALL, <a class="link" href="igraph-Games.html#igraph_rewire_edges" title="5.2. igraph_rewire_edges — Rewires the edges of a graph with constant probability."><code class="function">igraph_rewire_edges()</code></a> will be called.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>prob</code></em>:</span></p></td>
<td><p>
The rewiring probability, a constant between zero and
one (inclusive).
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>loops</code></em>:</span></p></td>
<td><p>
Boolean, whether loop edges are allowed in the new
graph, or not.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>mode</code></em>:</span></p></td>
<td>
<p>
The endpoints of directed edges to rewire. It is ignored for
undirected graphs. Possible values:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_OUT</code></span></p></td>
<td><p>
rewire the end of each directed edge
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_IN</code></span></p></td>
<td><p>
rewire the start of each directed edge
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_ALL</code></span></p></td>
<td><p>
rewire both endpoints of each edge
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Games.html#igraph_rewire_edges" title="5.2. igraph_rewire_edges — Rewires the edges of a graph with constant probability."><code class="function">igraph_rewire_edges()</code></a>, <a class="link" href="igraph-Games.html#igraph_rewire" title="4.3. igraph_rewire — Randomly rewires a graph while preserving its degree sequence."><code class="function">igraph_rewire()</code></a>
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|E|).
</p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="other-random-games"></a>6. Other random graphs</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="igraph-Games.html#igraph_grg_game">6.1. <code class="function">igraph_grg_game</code> — Generates a geometric random graph.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_dot_product_game">6.2. <code class="function">igraph_dot_product_game</code> — Generates a random dot product graph.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_simple_interconnected_islands_game">6.3. <code class="function">igraph_simple_interconnected_islands_game</code> — Generates a random graph made of several interconnected islands, each island being a random graph.</a></span></dt>
<dt><span class="section"><a href="igraph-Games.html#igraph_tree_game">6.4. <code class="function">igraph_tree_game</code> — Generates a random tree with the given number of nodes.</a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_grg_game"></a>6.1. <code class="function">igraph_grg_game</code> — Generates a geometric random graph.</h3></div></div></div>
<a class="indexterm" name="id-1.13.8.2.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_grg_game(igraph_t *graph, igraph_int_t nodes,
igraph_real_t radius, igraph_bool_t torus,
igraph_vector_t *x, igraph_vector_t *y);
</pre></div>
<p>
</p>
<p>
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 <code class="constant">radius</code> apart in Euclidean distance.
</p>
<p>
Original code contributed by Keith Briggs, thanks Keith.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>nodes</code></em>:</span></p></td>
<td><p>
The number of vertices in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>radius</code></em>:</span></p></td>
<td><p>
The radius within which the vertices will be connected.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>torus</code></em>:</span></p></td>
<td><p>
Boolean constant. If true, periodic boundary conditions
will be used, i.e. the vertices are assumed to be on a torus
instead of a square.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>x</code></em>:</span></p></td>
<td><p>
An initialized vector or <code class="constant">NULL</code>. If not <code class="constant">NULL</code>, the points'
x coordinates will be returned here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>y</code></em>:</span></p></td>
<td><p>
An initialized vector or <code class="constant">NULL</code>. If not <code class="constant">NULL</code>, the points'
y coordinates will be returned here.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: TODO, less than O(|V|^2+|E|).
</p>
<div class="hideshow" onClick="toggle(this, event)">
<div class="example">
<a name="id-1.13.8.2.9.1"></a><p class="title"><b>Example 12.6.  File <code class="code">examples/simple/igraph_grg_game.c</code></b></p>
<div class="example-contents">
<pre class="programlisting"><span class="strong"><strong>#include</strong></span> &lt;igraph.h&gt;
<span class="strong"><strong>#include</strong></span> &lt;math.h&gt;
int <span class="strong"><strong>main</strong></span>(void) {
igraph_t graph;
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1.  About igraph_vector_t objects">igraph_vector_t</a> x, y;
<a class="link" href="igraph-Data-structures.html#igraph_vector_t" title="2.1.  About igraph_vector_t objects">igraph_vector_t</a> weights;
igraph_eit_t eit;
igraph_real_t avg_dist;
<span class="emphasis"><em>/* Initialize the library. */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_setup" title="4.1. igraph_setup — Initializes the igraph library.">igraph_setup</a></strong></span>();
<span class="emphasis"><em>/* Set random seed for reproducible results */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_seed" title="3.3. igraph_rng_seed — Seeds a random number generator.">igraph_rng_seed</a></strong></span>(<span class="strong"><strong><a class="link" href="igraph-Random.html#igraph_rng_default" title="2.1. igraph_rng_default — Query the default random number generator.">igraph_rng_default</a></strong></span>(), 42);
<span class="emphasis"><em>/* Create a random geometric graph and retrieve vertex coordinates */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_init" title="2.2.1. igraph_vector_init — Initializes a vector object (constructor).">igraph_vector_init</a></strong></span>(&amp;x, 0);
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_init" title="2.2.1. igraph_vector_init — Initializes a vector object (constructor).">igraph_vector_init</a></strong></span>(&amp;y, 0);
<span class="strong"><strong><a class="link" href="igraph-Games.html#igraph_grg_game" title="6.1. igraph_grg_game — Generates a geometric random graph.">igraph_grg_game</a></strong></span>(&amp;graph, 200, 0.1, <span class="emphasis"><em>/* torus */</em></span> false, &amp;x, &amp;y);
<span class="emphasis"><em>/* Compute edge weights as geometric distance */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_init" title="2.2.1. igraph_vector_init — Initializes a vector object (constructor).">igraph_vector_init</a></strong></span>(&amp;weights, <span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_ecount" title="5.2.2. igraph_ecount — The number of edges in a graph.">igraph_ecount</a></strong></span>(&amp;graph));
<span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_eit_create" title="9.1. igraph_eit_create — Creates an edge iterator from an edge selector.">igraph_eit_create</a></strong></span>(&amp;graph, <span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_ess_all" title="7.1. igraph_ess_all — Edge set, all edges (immediate version).">igraph_ess_all</a></strong></span>(IGRAPH_EDGEORDER_ID), &amp;eit);
<span class="strong"><strong>for</strong></span> (; ! <span class="strong"><strong><a class="link" href="igraph-Iterators.html#IGRAPH_EIT_END" title="9.5. IGRAPH_EIT_END — Are we at the end?">IGRAPH_EIT_END</a></strong></span>(eit); <span class="strong"><strong><a class="link" href="igraph-Iterators.html#IGRAPH_EIT_NEXT" title="9.4. IGRAPH_EIT_NEXT — Next edge.">IGRAPH_EIT_NEXT</a></strong></span>(eit)) {
igraph_int_t e = <span class="strong"><strong><a class="link" href="igraph-Iterators.html#IGRAPH_EIT_GET" title="9.8. IGRAPH_EIT_GET — Query an edge iterator.">IGRAPH_EIT_GET</a></strong></span>(eit);
igraph_int_t u = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_FROM" title="5.2.6. IGRAPH_FROM — The source vertex of an edge.">IGRAPH_FROM</a></strong></span>(&amp;graph, e);
igraph_int_t v = <span class="strong"><strong><a class="link" href="igraph-Basic.html#IGRAPH_TO" title="5.2.7. IGRAPH_TO — The target vertex of an edge.">IGRAPH_TO</a></strong></span>(&amp;graph, e);
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(weights)[e] = <span class="strong"><strong>hypot</strong></span>(<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(x)[u] - <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(x)[v], <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(y)[u] - <span class="strong"><strong><a class="link" href="igraph-Data-structures.html#VECTOR" title="2.4.1. VECTOR — Accessing an element of a vector.">VECTOR</a></strong></span>(y)[v]);
}
<span class="strong"><strong><a class="link" href="igraph-Iterators.html#igraph_eit_destroy" title="9.2. igraph_eit_destroy — Destroys an edge iterator.">igraph_eit_destroy</a></strong></span>(&amp;eit);
<span class="emphasis"><em>/* Compute average path length */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Structural.html#igraph_average_path_length" title="3.20. igraph_average_path_length — The average shortest path length between all vertex pairs.">igraph_average_path_length</a></strong></span>(&amp;graph, &amp;weights, &amp;avg_dist, NULL, IGRAPH_UNDIRECTED, <span class="emphasis"><em>/* unconn */</em></span> true);
<span class="strong"><strong>printf</strong></span>("Average distance in the geometric graph: %g.\n", avg_dist);
<span class="emphasis"><em>/* Destroy data structures when no longer needed */</em></span>
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_destroy" title="2.2.5. igraph_vector_destroy — Destroys a vector object.">igraph_vector_destroy</a></strong></span>(&amp;weights);
<span class="strong"><strong><a class="link" href="igraph-Basic.html#igraph_destroy" title="5.1.4. igraph_destroy — Frees the memory allocated for a graph object.">igraph_destroy</a></strong></span>(&amp;graph);
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_destroy" title="2.2.5. igraph_vector_destroy — Destroys a vector object.">igraph_vector_destroy</a></strong></span>(&amp;x);
<span class="strong"><strong><a class="link" href="igraph-Data-structures.html#igraph_vector_destroy" title="2.2.5. igraph_vector_destroy — Destroys a vector object.">igraph_vector_destroy</a></strong></span>(&amp;y);
<span class="strong"><strong>return</strong></span> 0;
}
</pre>
<p></p>
</div>
</div>
<br class="example-break">
</div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_dot_product_game"></a>6.2. <code class="function">igraph_dot_product_game</code> — Generates a random dot product graph.</h3></div></div></div>
<a class="indexterm" name="id-1.13.8.3.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_dot_product_game(igraph_t *graph, const igraph_matrix_t *vecs,
igraph_bool_t directed);
</pre></div>
<p>
</p>
<p>
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.
</p>
<p>
See also Christine Leigh Myers Nickel: Random dot product graphs, a
model for social networks. Dissertation, Johns Hopkins University,
Maryland, USA, 2006.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
The output graph is stored here.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>vecs</code></em>:</span></p></td>
<td><p>
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.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Should the generated graph be directed?
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(n*n*m), where n is the number of vertices,
and m is the length of the latent vectors.
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Nongraph.html#igraph_rng_sample_dirichlet" title="4.3. igraph_rng_sample_dirichlet — Sample points from a Dirichlet distribution."><code class="function">igraph_rng_sample_dirichlet()</code></a>, <a class="link" href="igraph-Nongraph.html#igraph_rng_sample_sphere_volume" title="4.2. igraph_rng_sample_sphere_volume — Sample points uniformly from the volume of a sphere."><code class="function">igraph_rng_sample_sphere_volume()</code></a>, <a class="link" href="igraph-Nongraph.html#igraph_rng_sample_sphere_surface" title="4.1. igraph_rng_sample_sphere_surface — Sample points uniformly from the surface of a sphere."><code class="function">igraph_rng_sample_sphere_surface()</code></a>
for functions to generate the latent vectors.
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_simple_interconnected_islands_game"></a>6.3. <code class="function">igraph_simple_interconnected_islands_game</code> — Generates a random graph made of several interconnected islands, each island being a random graph.</h3></div></div></div>
<a class="indexterm" name="id-1.13.8.4.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_simple_interconnected_islands_game(
igraph_t *graph,
igraph_int_t islands_n,
igraph_int_t islands_size,
igraph_real_t islands_pin,
igraph_int_t n_inter);
</pre></div>
<p>
</p>
<p>
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.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>islands_n</code></em>:</span></p></td>
<td><p>
The number of islands in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>islands_size</code></em>:</span></p></td>
<td><p>
The size of islands in the graph.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>islands_pin</code></em>:</span></p></td>
<td><p>
The probability to create each possible edge within islands.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n_inter</code></em>:</span></p></td>
<td><p>
The number of edges to create between two islands. It may be
larger than <em class="parameter"><code>islands_size</code></em> squared, but in this case it is assumed
to be <em class="parameter"><code>islands_size</code></em> squared.</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_EINVAL</code>: invalid parameter
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough memory for the operation.
</p></td>
</tr></tbody>
</table></div>
<p>
Time complexity: O(|V|+|E|), the
number of vertices plus the number of edges in the graph.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_tree_game"></a>6.4. <code class="function">igraph_tree_game</code> — Generates a random tree with the given number of nodes.</h3></div></div></div>
<a class="indexterm" name="id-1.13.8.5.2"></a><p>
</p>
<div class="informalexample"><pre class="programlisting">
igraph_error_t igraph_tree_game(igraph_t *graph, igraph_int_t n, igraph_bool_t directed, igraph_random_tree_t method);
</pre></div>
<p>
</p>
<p>
This function samples uniformly from the set of labelled trees,
i.e. it generates each labelled tree with the same probability.
</p>
<p>
Note that for <code class="literal">n=0</code>, the null graph is returned,
which is not considered to be a tree by <a class="link" href="igraph-Structural.html#igraph_is_tree" title="16.3. igraph_is_tree — Decides whether the graph is a tree."><code class="function">igraph_is_tree()</code></a>.
</p>
<p><b>Arguments: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><em class="parameter"><code>graph</code></em>:</span></p></td>
<td><p>
Pointer to an uninitialized graph object.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>n</code></em>:</span></p></td>
<td><p>
The number of nodes in the tree.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>directed</code></em>:</span></p></td>
<td><p>
Whether to create a directed tree. The edges are oriented away from the root.
</p></td>
</tr>
<tr>
<td><p><span class="term"><em class="parameter"><code>method</code></em>:</span></p></td>
<td>
<p>
The algorithm to use to generate the tree. Possible values:
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_RANDOM_TREE_PRUFER</code></span></p></td>
<td><p>
This algorithm samples Prüfer sequences uniformly, then converts them to trees.
Directed trees are not currently supported.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_RANDOM_LERW</code></span></p></td>
<td><p>
This algorithm effectively performs a loop-erased random walk on the complete graph
to uniformly sample its spanning trees (Wilson's algorithm).
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</td>
</tr>
</tbody>
</table></div>
<p>
</p>
<p><b>Returns: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
Error code:
<code class="constant">IGRAPH_ENOMEM</code>: there is not enough
memory to perform the operation.
<code class="constant">IGRAPH_EINVAL</code>: invalid tree size
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
<p><b>See also: </b></p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody><tr>
<td><p><span class="term"><em class="parameter"><code></code></em></span></p></td>
<td><p>
<a class="link" href="igraph-Generators.html#igraph_from_prufer" title="5.5. igraph_from_prufer — Generates a tree from a Prüfer sequence."><code class="function">igraph_from_prufer()</code></a>
</p></td>
</tr></tbody>
</table></div>
<p>
</p>
</div>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="generator-types-and-constants"></a>7. Common types and constants</h2></div></div></div>
<div class="toc"><dl class="toc"><dt><span class="section"><a href="igraph-Games.html#igraph_edge_type_sw_t">7.1. <code class="function">igraph_edge_type_sw_t</code> — What types of non-simple edges to allow?</a></span></dt></dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="igraph_edge_type_sw_t"></a>7.1. <code class="function">igraph_edge_type_sw_t</code> — What types of non-simple edges to allow?</h3></div></div></div>
<a class="indexterm" name="id-1.13.9.2.2"></a><pre class="programlisting">
typedef unsigned int igraph_edge_type_sw_t;
</pre>
<p>
This type is used with multiple functions to specify what types of non-simple
edges to allow, create or consider a graph. The constants below are treated
as "switches" that can be turned on individually and combined using the
bitwise-or operator. For example,
<code class="literal">IGRAPH_LOOPS_SW</code>
allows only self-loops but not multi-edges, while
<code class="literal">IGRAPH_LOOPS_SW | IGRAPH_MULTI_SW</code>
allows both.
</p>
<p><b>Values: </b>
</p>
<div class="variablelist"><table border="0" class="variablelist">
<colgroup>
<col align="left" valign="top">
<col>
</colgroup>
<tbody>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_SIMPLE_SW</code>:</span></p></td>
<td><p>
A shorthand for simple graphs only, which is the default
assumption.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_LOOPS_SW</code>:</span></p></td>
<td><p>
Allow or consider self-loops.
</p></td>
</tr>
<tr>
<td><p><span class="term"><code class="constant">IGRAPH_MULTI_SW</code>:</span></p></td>
<td><p>
Allow or consider multi-edges.
</p></td>
</tr>
</tbody>
</table></div>
<p>
</p>
</div>
</div>
</div>
<table class="navigation-footer" width="100%" summary="Navigation footer" cellpadding="2" cellspacing="0"><tr valign="middle">
<td align="left"><a accesskey="p" href="igraph-Generators.html"><b>← Chapter 11. Deterministic graph generators</b></a></td>
<td align="right"><a accesskey="n" href="igraph-Bipartite.html"><b>Chapter 13. Bipartite, i.e. two-mode graphs →</b></a></td>
</tr></table>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink