igraph Reference Manual

For using the igraph C library

Chapter 10. Games on graphs

1. Microscopic update rules
2. Epidemic models

1. Microscopic update rules

1.1. igraph_deterministic_optimal_imitation — Adopt a strategy via deterministic optimal imitation.
1.2. igraph_moran_process — The Moran process in a network setting.
1.3. igraph_roulette_wheel_imitation — Adopt a strategy via roulette wheel selection.
1.4. igraph_stochastic_imitation — Adopt a strategy via stochastic imitation with uniform selection.

1.1. `igraph_deterministic_optimal_imitation` — Adopt a strategy via deterministic optimal imitation.

igraph_error_t igraph_deterministic_optimal_imitation(const igraph_t *graph,
        igraph_integer_t vid,
        igraph_optimal_t optimality,
        const igraph_vector_t *quantities,
        igraph_vector_int_t *strategies,
        igraph_neimode_t mode);

A simple deterministic imitation strategy where a vertex revises its strategy to that which yields a local optimum. Here "local" is with respect to the immediate neighbours of the vertex. The vertex retains its current strategy where this strategy yields a locally optimal quantity. The quantity in this case could be a measure such as fitness.

Arguments:

graph:

The graph object representing the game network. This cannot be the empty or trivial graph, but must have at least two vertices and one edge. If graph has one vertex, then no strategy update would take place. Furthermore, if graph has at least two vertices but zero edges, then strategy update would also not take place.

vid:

The vertex whose strategy is to be updated. It is assumed that vid represents a vertex in graph. No checking is performed and it is your responsibility to ensure that vid is indeed a vertex of graph. If an isolated vertex is provided, i.e. the input vertex has degree 0, then no strategy update would take place and vid would retain its current strategy. Strategy update would also not take place if the local neighbourhood of vid are its in-neighbours (respectively out-neighbours), but vid has zero in-neighbours (respectively out-neighbours). Loops are ignored in computing the degree (in, out, all) of vid.

optimality:

Logical; controls the type of optimality to be used. Supported values are:

`IGRAPH_MAXIMUM`	Use maximum deterministic imitation, where the strategy of the vertex with maximum quantity (e.g. fitness) would be adopted. We update the strategy of `vid` to that which yields a local maximum.
`IGRAPH_MINIMUM`	Use minimum deterministic imitation. That is, the strategy of the vertex with minimum quantity would be imitated. In other words, update to the strategy that yields a local minimum.

quantities:

strategies:

A vector of the current strategies for the vertex population. The updated strategy for vid would be stored here. Each strategy is identified with a nonnegative integer, whose interpretation depends on the payoff matrix of the game. Generally we use the strategy ID as a row or column index of the payoff matrix. The length of this vector must be the same as the number of vertices in the vertex set of graph.

mode:

Defines the sort of neighbourhood to consider for vid. If graph is undirected, then we use all the immediate neighbours of vid. Thus if you know that graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

`IGRAPH_OUT`	Use the out-neighbours of `vid`. This option is only relevant when `graph` is a directed graph.
`IGRAPH_IN`	Use the in-neighbours of `vid`. Again this option is only relevant when `graph` is a directed graph.
`IGRAPH_ALL`	Use both the in- and out-neighbours of `vid`. This option is only relevant if `graph` is a digraph. Also use this value if `graph` is undirected.

Returns:

The error code IGRAPH_EINVAL is returned in each of the following cases: (1) Any of the parameters graph, quantities, or strategies is a null pointer. (2) The vector quantities or strategies has a length different from the number of vertices in graph. (3) The parameter graph is the empty or null graph, i.e. the graph with zero vertices and edges.

Time complexity: O(2d), where d is the degree of the vertex vid.

Example 10.1. File examples/simple/igraph_deterministic_optimal_imitation.c

#include <igraph.h>
#include <stdio.h>

/* test parameters structure */
typedef struct {
    igraph_t *graph;
    igraph_integer_t vertex;
    igraph_optimal_t optimality;
    igraph_vector_t *quantities;
    igraph_vector_int_t *strategies;
    igraph_neimode_t mode;
    igraph_error_t retval;
} strategy_test_t;

/* Updating the strategy of an isolated vertex. In this case, the strategies
 * vector should not change at all.
 */
igraph_error_t isolated_vertex_test(void) {
    igraph_t g;
    igraph_vector_t quant;
    igraph_vector_int_t strat, v;
    igraph_integer_t i;
    igraph_error_t ret;

    /* graph with one isolated vertex */
    igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, -1);
    igraph_add_vertices(&g, 1, 0);  /* new vertex 3 is isolated */
    /* quantities vector: all vertices have the same fitness */
    igraph_vector_init_real(&quant, 4, 0.25, 0.25, 0.25, 0.25);
    /* strategies vector: 0 means aggressive strategy; 1 means passive */
    igraph_vector_int_init_int(&strat, 4, 1, 0, 1, 0);
    /* make a copy of the original strategies vector for comparison later on */
    igraph_vector_int_init_copy(&v, &strat);
    /* Now update strategy of vertex 3. Since this vertex is isolated, no */
    /* strategy update would take place. The resulting strategies vector */
    /* would be the same as it was originally. */
    ret = igraph_deterministic_optimal_imitation(/*graph*/ &g,
            /*vertex*/ 3,
            /*optimality*/ IGRAPH_MAXIMUM,
            /*quantities*/ &quant,
            /*strategies*/ &strat,
            /*mode*/ IGRAPH_ALL);
    if (ret) {
        printf("Isolated vertex test failed.\n");
        return IGRAPH_FAILURE;
    }
    for (i = 0; i < igraph_vector_int_size(&strat); i++) {
        if (VECTOR(strat)[i] != VECTOR(v)[i]) {
            printf("Isolated vertex test failed.\n");
            return IGRAPH_FAILURE;
        }
    }
    /* clean up */
    igraph_destroy(&g);
    igraph_vector_destroy(&quant);
    igraph_vector_int_destroy(&strat);
    igraph_vector_int_destroy(&v);

    return IGRAPH_SUCCESS;
}

/* A game on the Petersen graph. This graph has 10 vertices and 15 edges.
 * The Petersen graph is initialized with a default quantities vector and a
 * default strategies vector. For each vertex v in the graph, we update the
 * strategy of v via deterministic optimal imitation. The resulting updated
 * strategies vector is compared with the known result vector. A mismatch would
 * raise an error code. If the updated strategies vector matches the known
 * result vector, we reset the strategies vector to its default state and
 * repeat the game with another vertex.
 */
igraph_error_t petersen_game_test(void) {
    igraph_t g;
    igraph_vector_t quant;
    igraph_vector_int_t known_max_v, known_min_v, strat, stratcopy;
    igraph_integer_t i, nvert;

    /* the Petersen graph */
    igraph_small(&g, /*n=*/ 0, IGRAPH_UNDIRECTED,
                 0, 1, 0, 4, 0, 5, 1, 2, 1, 6, 2, 3, 2, 7, 3, 4, 3, 8, 4, 9,
                 5, 7, 5, 8, 6, 8, 6, 9, 7, 9, -1);
    nvert = igraph_vcount(&g);
    /* Strategies vector, one strategy for each vertex. Thus vec[i] is the */
    /* strategy of vertex i. The strategy space is: {0, 1, 2, 3}. */
    igraph_vector_int_init_int(&strat, nvert, 1, 1, 2, 2, 0, 0, 0, 1, 2, 3);
    /* Quantities vector, one quantity per vertex. Thus vec[i] is the */
    /* quantity for vertex i. */
    igraph_vector_init_real(&quant, nvert,
                            0.3, 1.1, 0.5, 1.0, 0.9,
                            0.8, 0.4, 0.1, 0.7, 0.7);
    /* Known strategies that would be adopted. Thus vec[i] means that in */
    /* game i where we revise the strategy of vertex i, the strategy */
    /* vec[i] would be adopted by i. */
    /*maximum deterministic imitation*/
    igraph_vector_int_init_int(&known_max_v, nvert, 1, 1, 1, 2, 2, 0, 1, 0, 2, 0);
    /*minimum deterministic imitation*/
    igraph_vector_int_init_int(&known_min_v, nvert, 1, 1, 1, 2, 1, 1, 0, 1, 0, 1);
    /* play game and compare resulting updated strategies */
    for (i = 0; i < nvert; i++) {
        /* maximum deterministic imitation */
        igraph_vector_int_init_copy(&stratcopy, &strat);
        igraph_deterministic_optimal_imitation(/*graph*/ &g,
                /*vertex*/ i,
                /*optimality*/ IGRAPH_MAXIMUM,
                /*quantities*/ &quant,
                /*strategies*/ &stratcopy,
                /*neighbours*/ IGRAPH_ALL);
        if (VECTOR(stratcopy)[i] != VECTOR(known_max_v)[i]) {
            printf("Maximum deterministic imitation failed for vertex %" IGRAPH_PRId ".\n", i);
            return IGRAPH_FAILURE;
        }
        igraph_vector_int_destroy(&stratcopy);
        /* minimum deterministic imitation */
        igraph_vector_int_init_copy(&stratcopy, &strat);
        igraph_deterministic_optimal_imitation(/*graph*/ &g,
                /*vertex*/ i,
                /*optimality*/ IGRAPH_MINIMUM,
                /*quantities*/ &quant,
                /*strategies*/ &stratcopy,
                /*neighbours*/ IGRAPH_ALL);
        if (VECTOR(stratcopy)[i] != VECTOR(known_min_v)[i]) {
            printf("Minimum deterministic imitation failed for vertex %" IGRAPH_PRId ".\n", i);
            return IGRAPH_FAILURE;
        }
        igraph_vector_int_destroy(&stratcopy);
    }
    /* clean up */
    igraph_destroy(&g);
    igraph_vector_int_destroy(&known_max_v);
    igraph_vector_int_destroy(&known_min_v);
    igraph_vector_destroy(&quant);
    igraph_vector_int_destroy(&strat);

    return IGRAPH_SUCCESS;
}

int main(void) {
    igraph_error_t ret;

    igraph_rng_seed(igraph_rng_default(), 648);

    ret = isolated_vertex_test();
    if (ret) {
        return ret;
    }
    ret = petersen_game_test();
    if (ret) {
        return ret;
    }

    return IGRAPH_SUCCESS;
}

1.2. `igraph_moran_process` — The Moran process in a network setting.

igraph_error_t igraph_moran_process(const igraph_t *graph,
                         const igraph_vector_t *weights,
                         igraph_vector_t *quantities,
                         igraph_vector_int_t *strategies,
                         igraph_neimode_t mode);

This is an extension of the classic Moran process to a network setting. The Moran process is a model of haploid (asexual) reproduction within a population having a fixed size. In the network setting, the Moran process operates on a weighted graph. At each time step a vertex a is chosen for reproduction and another vertex b is chosen for death. Vertex a gives birth to an identical clone c, which replaces b. Vertex c is a clone of a in that c inherits both the current quantity (e.g. fitness) and current strategy of a.

The graph G representing the game network is assumed to be simple, i.e. free of loops and without multiple edges. If, on the other hand, G has a loop incident on some vertex v, then it is possible that when v is chosen for reproduction it would forgo this opportunity. In particular, when v is chosen for reproduction and v is also chosen for death, the clone of v would be v itself with its current vertex ID. In effect v forgoes its chance for reproduction.

Arguments:

graph:

The graph object representing the game network. This cannot be the empty or trivial graph, but must have at least two vertices and one edge. The Moran process will not take place in each of the following cases: (1) If graph has one vertex. (2) If graph has at least two vertices but zero edges.

weights:

A vector of all edge weights for graph. Thus weights[i] means the weight of the edge with edge ID i. For the purpose of the Moran process, each weight is assumed to be positive; it is your responsibility to ensure this condition holds. The length of this vector must be the same as the number of edges in graph.

quantities:

A vector of quantities providing the quantity of each vertex in graph. The quantity of the new clone will be stored here. Think of each entry of the vector as being generated by a function such as the fitness function for the game. So if the vector represents fitness quantities, then each vector entry is the fitness of some vertex. The length of this vector must be the same as the number of vertices in the vertex set of graph. For the purpose of the Moran process, each vector entry is assumed to be nonnegative; no checks will be performed for this. It is your responsibility to ensure that at least one entry is positive. Furthermore, this vector cannot be a vector of zeros; this condition will be checked.

strategies:

A vector of the current strategies for the vertex population. The strategy of the new clone will be stored here. Each strategy is identified with a nonnegative integer, whose interpretation depends on the payoff matrix of the game. Generally we use the strategy ID as a row or column index of the payoff matrix. The length of this vector must be the same as the number of vertices in the vertex set of graph.

mode:

Defines the sort of neighbourhood to consider for the vertex a chosen for reproduction. This is only relevant if graph is directed. If graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

`IGRAPH_OUT`	Use the out-neighbours of a. This option is only relevant when `graph` is directed.
`IGRAPH_IN`	Use the in-neighbours of a. Again this option is only relevant when `graph` is directed.
`IGRAPH_ALL`	Use both the in- and out-neighbours of a. This option is only relevant if `graph` is directed. Also use this value if `graph` is undirected.

Returns:

The error code IGRAPH_EINVAL is returned in each of the following cases: (1) Any of the parameters graph, weights, quantities or strategies is a null pointer. (2) The vector quantities or strategies has a length different from the number of vertices in graph. (3) The vector weights has a length different from the number of edges in graph. (4) The parameter graph is the empty or null graph, i.e. the graph with zero vertices and edges. (5) The vector weights, or the combination of interest, sums to zero. (6) The vector quantities, or the combination of interest, sums to zero.

Time complexity: depends on the random number generator, but is usually O(n) where n is the number of vertices in graph.

References:

`(Lieberman et al. 2005)`	E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312--316, 2005.
`(Moran 1958)`	P. A. P. Moran. Random processes in genetics. Mathematical Proceedings of the Cambridge Philosophical Society, 54(1):60--71, 1958.

1.3. `igraph_roulette_wheel_imitation` — Adopt a strategy via roulette wheel selection.

igraph_error_t igraph_roulette_wheel_imitation(const igraph_t *graph,
                                    igraph_integer_t vid,
                                    igraph_bool_t islocal,
                                    const igraph_vector_t *quantities,
                                    igraph_vector_int_t *strategies,
                                    igraph_neimode_t mode);

A simple stochastic imitation strategy where a vertex revises its strategy to that of a vertex u chosen proportionate to u's quantity (e.g. fitness). This is a special case of stochastic imitation, where a candidate is not chosen uniformly at random but proportionate to its quantity.

Arguments:

graph:

vid:

islocal:

Boolean; this flag controls which perspective to use in computing the relative quantity. If true then we use the local perspective; otherwise we use the global perspective. The local perspective for vid is the set of all immediate neighbours of vid. In contrast, the global perspective for vid is the vertex set of graph.

quantities:

A vector of quantities providing the quantity of each vertex in graph. Think of each entry of the vector as being generated by a function such as the fitness function for the game. So if the vector represents fitness quantities, then each vector entry is the fitness of some vertex. The length of this vector must be the same as the number of vertices in the vertex set of graph. For the purpose of roulette wheel selection, each vector entry is assumed to be nonnegative; no checks will be performed for this. It is your responsibility to ensure that at least one entry is nonzero. Furthermore, this vector cannot be a vector of zeros; this condition will be checked.

strategies:

mode:

Defines the sort of neighbourhood to consider for vid. This is only relevant if we are considering the local perspective, i.e. if islocal is true. If we are considering the global perspective, then it is safe to pass the value IGRAPH_ALL here. If graph is undirected, then we use all the immediate neighbours of vid. Thus if you know that graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

`IGRAPH_OUT`	Use the out-neighbours of `vid`. This option is only relevant when `graph` is a digraph and we are considering the local perspective.
`IGRAPH_IN`	Use the in-neighbours of `vid`. Again this option is only relevant when `graph` is a directed graph and we are considering the local perspective.
`IGRAPH_ALL`	Use both the in- and out-neighbours of `vid`. This option is only relevant if `graph` is a digraph. Also use this value if `graph` is undirected or we are considering the global perspective.

Returns:

Time complexity: O(n) where n is the number of vertices in the perspective to consider. If we consider the global perspective, then n is the number of vertices in the vertex set of graph. On the other hand, for the local perspective n is the degree of vid, excluding loops.

Reference:

(Yu & Gen 2010)

X. Yu and M. Gen. Introduction to Evolutionary Algorithms. Springer, 2010, pages 18--20.

Example 10.2. File examples/simple/igraph_roulette_wheel_imitation.c

#include <igraph.h>
#include <stdio.h>

#define R_INTEGER(a,b) (igraph_rng_get_integer(igraph_rng_default(), (a), (b)))

/* test parameters structure */
typedef struct {
    igraph_t *graph;
    igraph_integer_t vertex;
    igraph_bool_t islocal;
    igraph_vector_t *quantities;
    igraph_vector_int_t *strategies;
    igraph_vector_int_t *known_strats;
    igraph_neimode_t mode;
    igraph_error_t retval;
} strategy_test_t;

/* A game on a graph with 5 vertices and 7 edges. Use roulette wheel selection
 * to update strategies. This example also illustrates how a choice of
 * perspective (whether local or global) could affect the range of
 * possible strategies a vertex could adopt.
 */
igraph_error_t roulette_test(void) {
    igraph_t g;
    igraph_bool_t success;
    igraph_vector_t quant;
    igraph_vector_int_t *known, strat, stratcopy;
    igraph_vector_int_t known0, known1, known2, known3, known4, known5;
    igraph_integer_t i, k, n, nvert;
    igraph_error_t ret;
    strategy_test_t *test;

    /* the game network */
    igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED,
                 0, 3, 0, 4, 1, 2, 1, 4, 1, 5, 2, 3, 2, 4, 3, 4, -1);
    nvert = igraph_vcount(&g);
    /* strategies vector; the strategy space is {0, 1, 2, 3} */
    /* V[i] is strategy of vertex i */
    igraph_vector_int_init_int(&strat, nvert, 1, 0, 1, 2, 0, 3);
    /* quantities vector; V[i] is quantity of vertex i */
    igraph_vector_init_real(&quant, nvert, 0.56, 0.13, 0.26, 0.73, 0.67, 0.82);
    /* possible strategies each vertex can adopt */
    igraph_vector_int_init_int(&known0, /*n=*/ 3, 0, 1, 2);       /* local */
    igraph_vector_int_init_int(&known1, /*n=*/ 3, 0, 1, 3);       /* local */
    igraph_vector_int_init_int(&known2, /*n=*/ 3, 0, 1, 2);       /* local */
    igraph_vector_int_init_int(&known3, /*n=*/ 3, 0, 1, 2);       /* local */
    igraph_vector_int_init_int(&known4, /*n=*/ 3, 0, 1, 2);       /* local */
    igraph_vector_int_init_int(&known5, /*n=*/ 4, 0, 1, 2, 3);    /* global */

    /* test parameters */
    /*graph--vert--islocal--quantities--strategies--known_strats--mode-retval*/
    strategy_test_t game0 = {&g, 0, 1, &quant, NULL, &known0, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t game1 = {&g, 1, 1, &quant, NULL, &known1, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t game2 = {&g, 2, 1, &quant, NULL, &known2, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t game3 = {&g, 3, 1, &quant, NULL, &known3, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t game4 = {&g, 4, 1, &quant, NULL, &known4, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t game5 = {&g, 5, 0, &quant, NULL, &known5, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t *all_checks[] = {/* 1 */ &game0,
                                             /* 2 */ &game1,
                                             /* 3 */ &game2,
                                             /* 4 */ &game3,
                                             /* 5 */ &game4,
                                             /* 6 */ &game5
                                    };

    /* play game */
    n = 6;
    i = 0;
    while (i < n) {
        test = all_checks[i];
        igraph_vector_int_init_copy(&stratcopy, &strat);
        ret = igraph_roulette_wheel_imitation(test->graph, test->vertex,
                                              test->islocal, test->quantities,
                                              &stratcopy, test->mode);
        if (ret != test->retval) {
            printf("Test no. %" IGRAPH_PRId " failed.\n", i + 1);
            return IGRAPH_FAILURE;
        }
        /* If the revised strategy s matches one of the candidate strategies, */
        /* then success. If s doesn't match any of the possible strategies, then */
        /* failure. Default to failure. */
        success = 0;
        known = test->known_strats;
        for (k = 0; k < igraph_vector_int_size(known); k++) {
            if (VECTOR(*known)[k] == VECTOR(stratcopy)[test->vertex]) {
                success = 1;
                break;
            }
        }
        if (!success) {
            printf("Roulette wheel imitation failed for vertex %" IGRAPH_PRId ".\n", test->vertex);
            return IGRAPH_FAILURE;
        }
        igraph_vector_int_destroy(&stratcopy);
        i++;
    }
    /* game finished; pack up */
    igraph_destroy(&g);
    igraph_vector_int_destroy(&known0);
    igraph_vector_int_destroy(&known1);
    igraph_vector_int_destroy(&known2);
    igraph_vector_int_destroy(&known3);
    igraph_vector_int_destroy(&known4);
    igraph_vector_int_destroy(&known5);
    igraph_vector_destroy(&quant);
    igraph_vector_int_destroy(&strat);

    return IGRAPH_SUCCESS;
}

/* It is possible for a vertex to retain its current strategy. This can
 * happen both in the local and global perspectives.
 */
igraph_error_t retain_strategy_test(void) {
    igraph_t g;
    igraph_integer_t max, min, v;
    igraph_vector_t quant;
    igraph_vector_int_t strat, stratcp;
    igraph_integer_t i, ntry, nvert;

    /* the game network */
    igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED,
                 0, 3, 0, 4, 1, 2, 1, 4, 1, 5, 2, 3, 2, 4, 3, 4, -1);
    nvert = igraph_vcount(&g);
    /* strategies vector; the strategy space is {0, 1, 2, 3} */
    /* V[i] is strategy of vertex i */
    igraph_vector_int_init_int(&strat, nvert, 1, 0, 1, 2, 0, 3);
    /* quantities vector; V[i] is quantity of vertex i */
    igraph_vector_init_real(&quant, nvert, 0.56, 0.13, 0.26, 0.73, 0.67, 0.82);

    /* random vertex */
    min = 0;
    max = 5;
    igraph_rng_seed(igraph_rng_default(), 42); /* make tests deterministic */
    v = R_INTEGER(min, max);  /* min <= v <= max */
    /* Ensure that it is possible for v to retain its current strategy. We */
    /* will try to do this at most ntry times. As there are at most 6 vertices */
    /* to choose from, it shouldn't take long before we encounter a strategy */
    /* revision round where v retains its current strategy. */
    /* With local perspective. */
    i = 0;
    ntry = 100;
    igraph_vector_int_init(&stratcp, 0);
    do {
        i++;
        if (i > ntry) {
            return IGRAPH_FAILURE;    /* ideally this should never happen */
        }
        igraph_vector_int_destroy(&stratcp);
        igraph_vector_int_init_copy(&stratcp, &strat);
        igraph_roulette_wheel_imitation(&g, v, /*is local?*/ 1, &quant, &stratcp,
                                        IGRAPH_ALL);
    } while (VECTOR(stratcp)[v] != VECTOR(strat)[v]);
    /* If we get to this point, we know that there was an update round */
    /* i <= ntry as a result of which v retains its current strategy. */
    /* Now try again, but this time with the global perspective. */
    i = 0;
    do {
        i++;
        if (i > ntry) {
            return IGRAPH_FAILURE;    /* ideally this should never happen */
        }
        igraph_vector_int_destroy(&stratcp);
        igraph_vector_int_init_copy(&stratcp, &strat);
        igraph_roulette_wheel_imitation(&g, v, /*is local?*/ 0, &quant, &stratcp,
                                        IGRAPH_ALL);
    } while (VECTOR(stratcp)[v] != VECTOR(strat)[v]);
    /* nothing further to do, but housekeeping */
    igraph_destroy(&g);
    igraph_vector_destroy(&quant);
    igraph_vector_int_destroy(&strat);
    igraph_vector_int_destroy(&stratcp);

    return IGRAPH_SUCCESS;
}

int main(void) {
    igraph_error_t ret;

    igraph_rng_seed(igraph_rng_default(), 3241);

    ret = roulette_test();
    if (ret) {
        return IGRAPH_FAILURE;
    }
    ret = retain_strategy_test();
    if (ret) {
        return IGRAPH_FAILURE;
    }

    return IGRAPH_SUCCESS;
}

1.4. `igraph_stochastic_imitation` — Adopt a strategy via stochastic imitation with uniform selection.

igraph_error_t igraph_stochastic_imitation(const igraph_t *graph,
                                igraph_integer_t vid,
                                igraph_imitate_algorithm_t algo,
                                const igraph_vector_t *quantities,
                                igraph_vector_int_t *strategies,
                                igraph_neimode_t mode);

A simple stochastic imitation strategy where a vertex revises its strategy to that of a vertex chosen uniformly at random from its local neighbourhood. This is called stochastic imitation via uniform selection, where the strategy to imitate is chosen via some random process. For the purposes of this function, we use uniform selection from a pool of candidates.

Arguments:

graph:

vid:

algo:

This flag controls which algorithm to use in stochastic imitation. Supported values are:

`IGRAPH_IMITATE_AUGMENTED`	Augmented imitation. Vertex `vid` imitates the strategy of the chosen vertex u provided that doing so would increase the quantity (e.g. fitness) of `vid`. Augmented imitation can be thought of as "imitate if better".
`IGRAPH_IMITATE_BLIND`	Blind imitation. Vertex `vid` blindly imitates the strategy of the chosen vertex u, regardless of whether doing so would increase or decrease the quantity of `vid`.
`IGRAPH_IMITATE_CONTRACTED`	Contracted imitation. Here vertex `vid` imitates the strategy of the chosen vertex u if doing so would decrease the quantity of `vid`. Think of contracted imitation as "imitate if worse".

quantities:

strategies:

mode:

`IGRAPH_OUT`	Use the out-neighbours of `vid`. This option is only relevant when `graph` is a directed graph.
`IGRAPH_IN`	Use the in-neighbours of `vid`. Again this option is only relevant when `graph` is a directed graph.
`IGRAPH_ALL`	Use both the in- and out-neighbours of `vid`. This option is only relevant if `graph` is a digraph. Also use this value if `graph` is undirected.

Returns:

Time complexity: depends on the uniform random number generator, but should usually be O(1).

Example 10.3. File examples/simple/igraph_stochastic_imitation.c

#include <igraph.h>
#include <stdio.h>

/* test parameters structure */
typedef struct {
    igraph_t *graph;
    igraph_integer_t vertex;
    igraph_imitate_algorithm_t algo;
    igraph_vector_t *quantities;
    igraph_vector_int_t *strategies;
    igraph_vector_int_t *known_strats;
    igraph_neimode_t mode;
    igraph_integer_t retval;
} strategy_test_t;

/* Updating the strategy of an isolated vertex. In this case, the strategies
 * vector should not change at all.
 */
igraph_error_t isolated_vertex_test(void) {
    igraph_t g;
    igraph_vector_t quant;
    igraph_vector_int_t strat, v;
    igraph_integer_t i;
    igraph_error_t ret;

    /* graph with one isolated vertex */
    igraph_small(&g, /*n vertices*/ 0, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, -1);
    igraph_add_vertices(&g, 1, 0);  /* new vertex 3 is isolated */
    /* quantities vector: all vertices have the same fitness */
    igraph_vector_init_real(&quant, 4, 0.25, 0.25, 0.25, 0.25);
    /* strategies vector: 0 means aggressive strategy; 1 means passive */
    igraph_vector_int_init_int(&strat, 4, 1, 0, 1, 0);
    /* make a copy of the original strategies vector for comparison later on */
    igraph_vector_int_init_copy(&v, &strat);
    /* Now update strategy of vertex 3. Since this vertex is isolated, no */
    /* strategy update would take place. The resulting strategies vector */
    /* would be the same as it was originally. */
    ret = igraph_stochastic_imitation(/*graph*/ &g,
            /*vertex*/ 3,
            /*algorithm*/ IGRAPH_IMITATE_BLIND,
            /*quantities*/ &quant,
            /*strategies*/ &strat,
            /*mode*/ IGRAPH_ALL);
    if (ret) {
        printf("Isolated vertex test failed.\n");
        return IGRAPH_FAILURE;
    }
    for (i = 0; i < igraph_vector_int_size(&strat); i++) {
        if (VECTOR(strat)[i] != VECTOR(v)[i]) {
            printf("Isolated vertex test failed.\n");
            return IGRAPH_FAILURE;
        }
    }
    /* clean up */
    igraph_destroy(&g);
    igraph_vector_destroy(&quant);
    igraph_vector_int_destroy(&strat);
    igraph_vector_int_destroy(&v);

    return IGRAPH_SUCCESS;
}

/* A game on the Petersen graph. This graph has 10 vertices and 15 edges. The
 * Petersen graph is initialized with a default quantities vector and a
 * default strategies vector. Some vertices are chosen for strategy revision,
 * each one via a different stochastic imitation rule.
 */
igraph_error_t petersen_game_test(void) {
    igraph_t g;
    igraph_bool_t success;
    igraph_vector_t quant;
    igraph_vector_int_t strat, stratcopy, *knownstrats;
    igraph_vector_int_t known0, known2, known4;
    igraph_integer_t i, k, n;
    igraph_error_t ret;
    int nvert;
    strategy_test_t *test;

    /* the Petersen graph */
    igraph_small(&g, /*n vertices*/ 0, IGRAPH_UNDIRECTED,
                 0, 1, 0, 4, 0, 5, 1, 2, 1, 6, 2, 3, 2, 7, 3, 4, 3, 8, 4, 9,
                 5, 7, 5, 8, 6, 8, 6, 9, 7, 9, -1);
    nvert = igraph_vcount(&g);
    /* Strategies vector, one strategy for each vertex. Thus vec[i] is the */
    /* strategy of vertex i. The strategy space is: {0, 1, 2, 3}. */
    /* Each strategy should be an integer. */
    igraph_vector_int_init_int(&strat, nvert, 1, 1, 2, 2, 0, 0, 0, 1, 2, 3);
    /* Quantities vector, one quantity per vertex. Thus vec[i] is the */
    /* quantity for vertex i. */
    igraph_vector_init_real(&quant, nvert,
                            0.3, 1.1, 0.5, 1.0, 0.9,
                            0.8, 0.4, 0.1, 0.7, 0.7);
    /* parameter settings and known results */
    igraph_vector_int_init_int(&known0, 2, 0, 1);
    igraph_vector_int_init_int(&known2, 2, 1, 2);
    igraph_vector_int_init_int(&known4, 2, 0, 2);
    /*graph--vertex--algo--quantities--strategies--known_strats--mode--retval*/
    strategy_test_t blind0 = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, NULL, &known0, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t augmented4 = {&g, 4, IGRAPH_IMITATE_AUGMENTED, &quant, NULL, &known4, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t contracted2 = {&g, 2, IGRAPH_IMITATE_CONTRACTED, &quant, NULL, &known2, IGRAPH_ALL, IGRAPH_SUCCESS};
    strategy_test_t *all_checks[] = {/* 1 */ &blind0,
                                             /* 2 */ &augmented4,
                                             /* 3 */ &contracted2
                                    };
    /* run the tests */
    n = 3;
    i = 0;
    while (i < n) {
        test = all_checks[i];
        igraph_vector_int_init_copy(&stratcopy, &strat);
        ret = igraph_stochastic_imitation(test->graph, test->vertex, test->algo,
                                          test->quantities, &stratcopy,
                                          test->mode);
        if (ret) {
            printf("Stochastic imitation failed for vertex %" IGRAPH_PRId ".\n", test->vertex);
            return IGRAPH_FAILURE;
        }
        /* If the updated strategy for the vertex matches one of the known */
        /* strategies, then success. Default to failure. */
        success = 0;
        knownstrats = test->known_strats;
        for (k = 0; k < igraph_vector_int_size(knownstrats); k++) {
            if (VECTOR(*knownstrats)[k] == VECTOR(stratcopy)[test->vertex]) {
                success = 1;
                break;
            }
        }
        if (!success) {
            printf("Stochastic imitation failed for vertex %" IGRAPH_PRId ".\n", test->vertex);
            return IGRAPH_FAILURE;
        }
        igraph_vector_int_destroy(&stratcopy);
        i++;
    }
    /* clean up */
    igraph_destroy(&g);
    igraph_vector_int_destroy(&known0);
    igraph_vector_int_destroy(&known2);
    igraph_vector_int_destroy(&known4);
    igraph_vector_destroy(&quant);
    igraph_vector_int_destroy(&strat);

    return IGRAPH_SUCCESS;
}

int main(void) {
    igraph_error_t ret;

    igraph_rng_seed(igraph_rng_default(), 547612);

    ret = isolated_vertex_test();
    if (ret) {
        return ret;
    }
    ret = petersen_game_test();
    if (ret) {
        return ret;
    }

    return IGRAPH_SUCCESS;
}

2. Epidemic models

2.1. igraph_sir — Performs a number of SIR epidemics model runs on a graph.
2.2. igraph_sir_t — The result of one SIR model simulation.
2.3. igraph_sir_destroy — Deallocates memory associated with a SIR simulation run.

2.1. `igraph_sir` — Performs a number of SIR epidemics model runs on a graph.

igraph_error_t igraph_sir(const igraph_t *graph, igraph_real_t beta,
               igraph_real_t gamma, igraph_integer_t no_sim,
               igraph_vector_ptr_t *result);

The SIR model is a simple model from epidemiology. The individuals of the population might be in three states: susceptible, infected and recovered. Recovered people are assumed to be immune to the disease. Susceptibles become infected with a rate that depends on their number of infected neighbors. Infected people become recovered with a constant rate. See these parameters below.

This function runs multiple simulations, all starting with a single uniformly randomly chosen infected individual. A simulation is stopped when no infected individuals are left.

Arguments:

`graph`:	The graph to perform the model on. For directed graphs edge directions are ignored and a warning is given.
`beta`:	The rate of infection of an individual that is susceptible and has a single infected neighbor. The infection rate of a susceptible individual with n infected neighbors is n times beta. Formally this is the rate parameter of an exponential distribution.
`gamma`:	The rate of recovery of an infected individual. Formally, this is the rate parameter of an exponential distribution.
`no_sim`:	The number of simulation runs to perform.
`result`:	The result of the simulation is stored here, in a list of `igraph_sir_t` objects. To deallocate memory, the user needs to call `igraph_sir_destroy` on each element, before destroying the pointer vector itself using `igraph_vector_ptr_destroy_all()`.

Returns:

Error code.

Time complexity: O(no_sim * (|V| + |E| log(|V|))).

2.2. `igraph_sir_t` — The result of one SIR model simulation.

typedef struct igraph_sir_t {
    igraph_vector_t times;
    igraph_vector_int_t no_s, no_i, no_r;
} igraph_sir_t;

Data structure to store the results of one simulation of the SIR (susceptible-infected-recovered) model on a graph. It has the following members. They are all (real or integer) vectors, and they are of the same length.

Values:

`times`:	A vector, the times of the events are stored here.
`no_s`:	An integer vector, the number of susceptibles in each time step is stored here.
`no_i`:	An integer vector, the number of infected individuals at each time step, is stored here.
`no_r`:	An integer vector, the number of recovered individuals is stored here at each time step.

2.3. `igraph_sir_destroy` — Deallocates memory associated with a SIR simulation run.

void igraph_sir_destroy(igraph_sir_t *sir);

Arguments:

sir:

The igraph_sir_t object storing the simulation.

igraph Reference Manual

Chapter 10. Games on graphs

1. Microscopic update rules

1.1. igraph_deterministic_optimal_imitation — Adopt a strategy via deterministic optimal imitation.

1.2. igraph_moran_process — The Moran process in a network setting.

1.3. igraph_roulette_wheel_imitation — Adopt a strategy via roulette wheel selection.

1.4. igraph_stochastic_imitation — Adopt a strategy via stochastic imitation with uniform selection.

2. Epidemic models

2.1. igraph_sir — Performs a number of SIR epidemics model runs on a graph.

2.2. igraph_sir_t — The result of one SIR model simulation.

2.3. igraph_sir_destroy — Deallocates memory associated with a SIR simulation run.

1.1. `igraph_deterministic_optimal_imitation` — Adopt a strategy via deterministic optimal imitation.

1.2. `igraph_moran_process` — The Moran process in a network setting.

1.3. `igraph_roulette_wheel_imitation` — Adopt a strategy via roulette wheel selection.

1.4. `igraph_stochastic_imitation` — Adopt a strategy via stochastic imitation with uniform selection.

2.1. `igraph_sir` — Performs a number of SIR epidemics model runs on a graph.

2.2. `igraph_sir_t` — The result of one SIR model simulation.

2.3. `igraph_sir_destroy` — Deallocates memory associated with a SIR simulation run.