igraph_deterministic_optimal_imitation — Adopt a strategy via deterministic optimal imitation.igraph_moran_process — The Moran process in a network setting.igraph_roulette_wheel_imitation — Adopt a strategy via roulette wheel selection.igraph_stochastic_imitation — Adopt a strategy via stochastic imitation with uniform selection.
int igraph_deterministic_optimal_imitation(const igraph_t *graph,
igraph_integer_t vid,
igraph_optimal_t optimality,
const igraph_vector_t *quantities,
igraph_vector_t *strategies,
igraph_neimode_t mode);
A simple deterministic imitation strategy where a vertex revises its strategy to that which yields a local optimal. 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:
|
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 |
||||||
|
The vertex whose strategy is to be updated. It is assumed that
|
||||||
|
Logical; controls the type of optimality to be used. Supported values are:
|
||||||
|
A vector of quantities providing the quantity of each
vertex in |
||||||
|
A vector of the current strategies for the vertex
population. The updated strategy for |
||||||
|
Defines the sort of neighbourhood to consider for
|
Returns:
The error code |
Time complexity: O(2d), where d is the degree of the vertex vid.
Example 10.1. File examples/simple/igraph_deterministic_optimal_imitation.c
/* -*- mode: C -*- */ /* Test suite for deterministic optimal imitation. Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #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_t *strategies; igraph_neimode_t mode; int retval; } strategy_test_t; /* Error tests. That is, we expect error codes to be returned from such tests. */ int error_tests() { igraph_t g, h; igraph_vector_t quant, strat; int i, n, ret; strategy_test_t *test; /* nonempty graph */ igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, -1); igraph_empty(&h, 0, 0); /* empty graph */ igraph_vector_init(&quant, 1); /* quantities vector */ igraph_vector_init(&strat, 2); /* strategies vector */ { /* test parameters */ /*--graph--vertex--optimality--quantities--strategies--mode--retval--*/ /* null pointer for graph */ strategy_test_t null_graph = { NULL, 0, 0, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL }; /* null pointer for quantities vector */ strategy_test_t null_quant = { &g, 0, 0, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL }; /* null pointer for strategies vector */ strategy_test_t null_strat = { &g, 0, 0, &quant, NULL, IGRAPH_ALL, IGRAPH_EINVAL }; /* empty graph */ strategy_test_t empty_graph = {&h, 0, 0, &quant, &strat, IGRAPH_ALL, IGRAPH_EINVAL }; /* length of quantities vector different from number of vertices */ strategy_test_t qdiff_length = {&g, 0, 0, &quant, &strat, IGRAPH_ALL, IGRAPH_EINVAL }; /* length of strategies vector different from number of vertices */ strategy_test_t sdiff_length = {&g, 0, 0, &quant, &strat, IGRAPH_ALL, IGRAPH_EINVAL }; strategy_test_t *all_checks[] = {/* 1 */ &null_graph, /* 2 */ &null_quant, /* 3 */ &null_strat, /* 4 */ &empty_graph, /* 5 */ &qdiff_length, /* 6 */ &sdiff_length }; n = 6; /* Run the error tests. We expect an error to be raised for each test. */ igraph_set_error_handler(igraph_error_handler_ignore); i = 0; while (i < n) { test = all_checks[i]; ret = igraph_deterministic_optimal_imitation(test->graph, test->vertex, test->optimality, test->quantities, test->strategies, test->mode); if (ret != test->retval) { printf("Error test no. %d failed.\n", (int)(i + 1)); return IGRAPH_FAILURE; } i++; } } /* clean up */ igraph_destroy(&g); igraph_destroy(&h); igraph_vector_destroy(&quant); igraph_vector_destroy(&strat); return IGRAPH_SUCCESS; } /* Updating the strategy of an isolated vertex. In this case, the strategies * vector should not change at all. */ int isolated_vertex_test() { igraph_t g; igraph_vector_t quant, strat, v; int i, 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_init_real(&strat, 4, 1., 0., 1., 0.); /* make a copy of the original strategies vector for comparison later on */ igraph_vector_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_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_destroy(&strat); igraph_vector_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. */ int petersen_game_test() { igraph_t g; igraph_vector_t known_max_v, known_min_v, quant, strat, stratcopy; int 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_init_real(&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_init_real(&known_max_v, nvert, 1., 1., 1., 2., 2., 0., 1., 0., 2., 0.); /*minimum deterministic imitation*/ igraph_vector_init_real(&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_copy(&stratcopy, &strat); igraph_deterministic_optimal_imitation(/*graph*/ &g, /*vertex*/ (igraph_integer_t)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 %d.\n", i); return IGRAPH_FAILURE; } igraph_vector_destroy(&stratcopy); /* minimum deterministic imitation */ igraph_vector_copy(&stratcopy, &strat); igraph_deterministic_optimal_imitation(/*graph*/ &g, /*vertex*/ (igraph_integer_t)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 %d.\n", i); return IGRAPH_FAILURE; } igraph_vector_destroy(&stratcopy); } /* clean up */ igraph_destroy(&g); igraph_vector_destroy(&known_max_v); igraph_vector_destroy(&known_min_v); igraph_vector_destroy(&quant); igraph_vector_destroy(&strat); return IGRAPH_SUCCESS; } int main() { int ret; igraph_rng_seed(igraph_rng_default(), 648); ret = error_tests(); if (ret) { return ret; } ret = isolated_vertex_test(); if (ret) { return ret; } ret = petersen_game_test(); if (ret) { return ret; } return IGRAPH_SUCCESS; }
int igraph_moran_process(const igraph_t *graph,
const igraph_vector_t *weights,
igraph_vector_t *quantities,
igraph_vector_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:
|
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 |
||||||
|
A vector of all edge weights for |
||||||
|
A vector of quantities providing the quantity of each
vertex in |
||||||
|
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 |
||||||
|
Defines the sort of neighbourhood to consider for the vertex a
chosen for reproduction. This is only relevant if
|
Returns:
The error code |
Time complexity: depends on the random number generator, but is usually
O(n) where n is the number of vertices in graph.
References:
|
E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312--316, 2005. |
|
P. A. P. Moran. Random processes in genetics. Mathematical Proceedings of the Cambridge Philosophical Society, 54(1):60--71, 1958. |
int igraph_roulette_wheel_imitation(const igraph_t *graph,
igraph_integer_t vid,
igraph_bool_t islocal,
const igraph_vector_t *quantities,
igraph_vector_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:
|
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 |
||||||
|
The vertex whose strategy is to be updated. It is assumed that
|
||||||
|
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 |
||||||
|
A vector of quantities providing the quantity of each
vertex in |
||||||
|
A vector of the current strategies for the vertex
population. The updated strategy for |
||||||
|
Defines the sort of neighbourhood to consider for
|
Returns:
The error code |
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:
|
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
/* -*- mode: C -*- */ /* Test suite for stochastic imitation via roulette wheel selection. Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #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_t *strategies; igraph_vector_t *known_strats; igraph_neimode_t mode; int retval; } strategy_test_t; /* Error tests. That is, we expect error codes to be returned from such tests. */ int error_tests() { igraph_t g, gzero, h; igraph_vector_t quant, quantzero, strat, stratzero; int i, n, nvert, ret; strategy_test_t *test; /* nonempty graph */ igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, -1); igraph_empty(&h, 0, 0); /* empty graph */ igraph_vector_init(&quant, 1); /* quantities vector */ igraph_vector_init(&strat, 2); /* strategies vector */ igraph_small(&gzero, /*nvert=*/ 0, IGRAPH_UNDIRECTED, 0, 3, 0, 4, 1, 2, 1, 4, 1, 5, 2, 3, 2, 4, 3, 4, -1); nvert = igraph_vcount(&gzero); igraph_vector_init_real(&stratzero, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0); igraph_vector_init(&quantzero, nvert); /* vector of zeros */ /* test parameters */ /*graph--vert--islocal--quantities--strategies--known_strats--mode--retval*/ /* null pointer for graph */ strategy_test_t null_graph = {NULL, 0, 1, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* null pointer for quantities vector */ strategy_test_t null_quant = {&g, 0, 1, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* null pointer for strategies vector */ strategy_test_t null_strat = {&g, 0, 1, &quant, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* empty graph */ strategy_test_t empty_graph = {&h, 0, 1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* length of quantities vector different from number of vertices */ strategy_test_t qdiff_length = {&g, 0, 1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* length of strategies vector different from number of vertices */ strategy_test_t sdiff_length = {&g, 0, 1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* quantities vector contains all zeros */ strategy_test_t zero_quant = {&gzero, 4, 1, &quantzero, &stratzero, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; strategy_test_t *all_checks[] = {/* 1 */ &null_graph, /* 2 */ &null_quant, /* 3 */ &null_strat, /* 4 */ &empty_graph, /* 5 */ &qdiff_length, /* 6 */ &sdiff_length, /* 7 */ &zero_quant }; /* Run the error tests. We expect error to be raised for each test. */ igraph_set_error_handler(igraph_error_handler_ignore); n = 7; i = 0; while (i < n) { test = all_checks[i]; ret = igraph_roulette_wheel_imitation(test->graph, test->vertex, test->islocal, test->quantities, test->strategies, test->mode); if (ret != test->retval) { printf("Error test no. %d failed.\n", (int)(i + 1)); return IGRAPH_FAILURE; } i++; } /* clean up */ igraph_destroy(&g); igraph_destroy(&gzero); igraph_destroy(&h); igraph_vector_destroy(&quant); igraph_vector_destroy(&quantzero); igraph_vector_destroy(&strat); igraph_vector_destroy(&stratzero); return IGRAPH_SUCCESS; } /* 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. */ int roulette_test() { igraph_t g; igraph_bool_t success; igraph_vector_t *known, quant, strat, stratcopy; igraph_vector_t known0, known1, known2, known3, known4, known5; int i, k, n, nvert, 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_init_real(&strat, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0); /* 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_init_real(&known0, /*n=*/ 3, 0.0, 1.0, 2.0); /* local */ igraph_vector_init_real(&known1, /*n=*/ 3, 0.0, 1.0, 3.0); /* local */ igraph_vector_init_real(&known2, /*n=*/ 3, 0.0, 1.0, 2.0); /* local */ igraph_vector_init_real(&known3, /*n=*/ 3, 0.0, 1.0, 2.0); /* local */ igraph_vector_init_real(&known4, /*n=*/ 3, 0.0, 1.0, 2.0); /* local */ igraph_vector_init_real(&known5, /*n=*/ 4, 0.0, 1.0, 2.0, 3.0); /* 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_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. %d 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_size(known); k++) { if (VECTOR(*known)[k] == VECTOR(stratcopy)[test->vertex]) { success = 1; break; } } if (!success) { printf("Roulette wheel imitation failed for vertex %d.\n", (int)test->vertex); return IGRAPH_FAILURE; } igraph_vector_destroy(&stratcopy); i++; } /* game finished; pack up */ igraph_destroy(&g); igraph_vector_destroy(&known0); igraph_vector_destroy(&known1); igraph_vector_destroy(&known2); igraph_vector_destroy(&known3); igraph_vector_destroy(&known4); igraph_vector_destroy(&known5); igraph_vector_destroy(&quant); igraph_vector_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. */ int retain_strategy_test() { igraph_t g; igraph_integer_t max, min, v; igraph_vector_t quant, strat, stratcp; int 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_init_real(&strat, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0); /* 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_init(&stratcp, 0); do { i++; if (i > ntry) { return IGRAPH_FAILURE; /* ideally this should never happen */ } igraph_vector_destroy(&stratcp); igraph_vector_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_destroy(&stratcp); igraph_vector_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_destroy(&strat); igraph_vector_destroy(&stratcp); return IGRAPH_SUCCESS; } int main() { int ret; igraph_rng_seed(igraph_rng_default(), 3241); ret = error_tests(); if (ret) { return IGRAPH_FAILURE; } ret = roulette_test(); if (ret) { return IGRAPH_FAILURE; } ret = retain_strategy_test(); if (ret) { return IGRAPH_FAILURE; } return IGRAPH_SUCCESS; }
int igraph_stochastic_imitation(const igraph_t *graph,
igraph_integer_t vid,
igraph_imitate_algorithm_t algo,
const igraph_vector_t *quantities,
igraph_vector_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:
|
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 |
||||||
|
The vertex whose strategy is to be updated. It is assumed that
|
||||||
|
This flag controls which algorithm to use in stochastic imitation. Supported values are:
|
||||||
|
A vector of quantities providing the quantity of each
vertex in |
||||||
|
A vector of the current strategies for the vertex
population. The updated strategy for |
||||||
|
Defines the sort of neighbourhood to consider for
|
Returns:
The error code |
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
/* -*- mode: C -*- */ /* Test suite for stochastic imitation via uniform selection. Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #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_t *strategies; igraph_vector_t *known_strats; igraph_neimode_t mode; int retval; } strategy_test_t; /* Error tests. That is, we expect error codes to be returned from such tests. */ int error_tests() { igraph_t g, h; igraph_vector_t quant, strat; int i, n, ret; strategy_test_t *test; /* nonempty graph */ igraph_small(&g, /*n vertices*/ 0, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, -1); igraph_empty(&h, 0, 0); /* empty graph */ igraph_vector_init(&quant, 1); /* quantities vector */ igraph_vector_init(&strat, 2); /* strategies vector */ /* test parameters */ /*graph--vertex--algo--quantities--strategies--known_strats--mode--retval*/ /* null pointer for graph */ strategy_test_t null_graph = {NULL, 0, IGRAPH_IMITATE_BLIND, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* null pointer for quantities vector */ strategy_test_t null_quant = {&g, 0, IGRAPH_IMITATE_BLIND, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* null pointer for strategies vector */ strategy_test_t null_strat = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* empty graph */ strategy_test_t empty_graph = {&h, 0, IGRAPH_IMITATE_BLIND, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* length of quantities vector different from number of vertices */ strategy_test_t qdiff_length = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; /* length of strategies vector different from number of vertices */ strategy_test_t sdiff_length = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; strategy_test_t unknown_algo = {&g, 0, -1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL}; strategy_test_t *all_checks[] = {/* 1 */ &null_graph, /* 2 */ &null_quant, /* 3 */ &null_strat, /* 4 */ &empty_graph, /* 5 */ &qdiff_length, /* 6 */ &sdiff_length, /* 7 */ &unknown_algo }; /* Run the error tests. We expect error to be raised for each test. */ igraph_set_error_handler(igraph_error_handler_ignore); n = 7; i = 0; while (i < n) { test = all_checks[i]; ret = igraph_stochastic_imitation(test->graph, test->vertex, test->algo, test->quantities, test->strategies, test->mode); if (ret != test->retval) { printf("Error test no. %d failed.\n", (int)(i + 1)); return IGRAPH_FAILURE; } i++; } /* clean up */ igraph_destroy(&g); igraph_destroy(&h); igraph_vector_destroy(&quant); igraph_vector_destroy(&strat); return IGRAPH_SUCCESS; } /* Updating the strategy of an isolated vertex. In this case, the strategies * vector should not change at all. */ int isolated_vertex_test() { igraph_t g; igraph_vector_t quant, strat, v; int i, 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_init_real(&strat, 4, 1.0, 0.0, 1.0, 0.0); /* make a copy of the original strategies vector for comparison later on */ igraph_vector_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_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_destroy(&strat); igraph_vector_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. */ int petersen_game_test() { igraph_t g; igraph_bool_t success; igraph_vector_t quant, strat, stratcopy, *knownstrats; igraph_vector_t known0, known2, known4; int i, k, n, nvert, ret; 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_init_real(&strat, nvert, 1.0, 1.0, 2.0, 2.0, 0.0, 0.0, 0.0, 1.0, 2.0, 3.0); /* 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_init_real(&known0, 2, 0.0, 1.0); igraph_vector_init_real(&known2, 2, 1.0, 2.0); igraph_vector_init_real(&known4, 2, 0.0, 2.0); /*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_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 %d.\n", (int)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_size(knownstrats); k++) { if (VECTOR(*knownstrats)[k] == VECTOR(stratcopy)[test->vertex]) { success = 1; break; } } if (!success) { printf("Stochastic imitation failed for vertex %d.\n", (int)test->vertex); return IGRAPH_FAILURE; } igraph_vector_destroy(&stratcopy); i++; } /* clean up */ igraph_destroy(&g); igraph_vector_destroy(&known0); igraph_vector_destroy(&known2); igraph_vector_destroy(&known4); igraph_vector_destroy(&quant); igraph_vector_destroy(&strat); return IGRAPH_SUCCESS; } int main() { int ret; igraph_rng_seed(igraph_rng_default(), 547612); ret = error_tests(); if (ret) { return ret; } ret = isolated_vertex_test(); if (ret) { return ret; } ret = petersen_game_test(); if (ret) { return ret; } return IGRAPH_SUCCESS; }
int 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 neigbors. 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:
|
The graph to perform the model on. For directed graphs edge directions are ignored and a warning is given. |
|
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. |
|
The rate of recovery of an infected individual. Formally, this is the rate parameter of an exponential distribution. |
|
The number of simulation runs to perform. |
|
The result of the simulation is stored here,
in a list of |
Returns:
Error code. |
Time complexity: O(no_sim * (|V| + |E| log(|V|))).
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:
|
A vector, the times of the events are stored here. |
|
An integer vector, the number of susceptibles in each time step is stored here. |
|
An integer vector, the number of infected individuals at each time step, is stored here. |
|
An integer vector, the number of recovered individuals is stored here at each time step. |
void igraph_sir_destroy(igraph_sir_t *sir);
Arguments:
|
The |
| ← Chapter 9. Graph generators | Chapter 11. Vertex and edge selectors and sequences, iterators → |