4
Copyright (C) 2007 Gabor Csardi <csardi@rmki.kfki.hu>
5
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
7
This program is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 2 of the License, or
10
(at your option) any later version.
12
This program is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
GNU General Public License for more details.
17
You should have received a copy of the GNU General Public License
18
along with this program; if not, write to the Free Software
19
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
29
typedef struct igraph_i_forest_fire_data_t {
30
igraph_vector_t *inneis;
31
igraph_vector_t *outneis;
33
} igraph_i_forest_fire_data_t;
36
void igraph_i_forest_fire_free(igraph_i_forest_fire_data_t *data) {
38
for (i=0; i<data->no_of_nodes; i++) {
39
igraph_vector_destroy(data->inneis+i);
40
igraph_vector_destroy(data->outneis+i);
45
* \function igraph_forest_fire_game
46
* \brief Generates a network according to the \quote forest fire game \endquote
48
* The forest fire model intends to reproduce the following network
49
* characteristics, observed in real networks:
51
* \ili Heavy-tailed in-degree distribution.
52
* \ili Heavy-tailed out-degree distribution.
54
* \ili Densification power-law. The network is densifying in time,
55
* according to a power-law rule.
56
* \ili Shrinking diameter. The diameter of the network decreases in
61
* The network is generated in the following way. One vertex is added at
62
* a time. This vertex connects to (cites) <code>ambs</code> vertices already
63
* present in the network, chosen uniformly random. Now, for each cited
64
* vertex <code>v</code> we do the following procedure:
66
* \oli We generate two random number, <code>x</code> and <code>y</code>, that are
67
* geometrically distributed with means <code>p/(1-p)</code> and
68
* <code>rp(1-rp)</code>. (<code>p</code> is <code>fw_prob</code>, <code>r</code> is
69
* <code>bw_factor</code>.) The new vertex cites <code>x</code> outgoing neighbors
70
* and <code>y</code> incoming neighbors of <code>v</code>, from those which are
71
* not yet cited by the new vertex. If there are less than <code>x</code> or
72
* <code>y</code> such vertices available then we cite all of them.
73
* \oli The same procedure is applied to all the newly cited
78
* Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time:
79
* densification laws, shrinking diameters and possible explanations.
80
* \emb KDD '05: Proceeding of the eleventh ACM SIGKDD international
81
* conference on Knowledge discovery in data mining \eme, 177--187, 2005.
83
* Note however, that the version of the model in the published paper is incorrect
84
* in the sense that it cannot generate the kind of graphs the authors
85
* claim. A corrected version is available from
86
* http://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf, our
87
* implementation is based on this.
89
* \param graph Pointer to an uninitialized graph object.
90
* \param nodes The number of vertices in the graph.
91
* \param fw_prob The forward burning probability.
92
* \param bw_factor The backward burning ratio. The backward burning
93
probability is calculated as <code>bw.factor*fw.prob</code>.
94
* \param pambs The number of ambassador vertices.
95
* \param directed Whether to create a directed graph.
98
* Time complexity: TODO.
101
int igraph_forest_fire_game(igraph_t *graph, igraph_integer_t nodes,
102
igraph_real_t fw_prob, igraph_real_t bw_factor,
103
igraph_integer_t pambs, igraph_bool_t directed) {
105
igraph_vector_long_t visited;
106
long int no_of_nodes=nodes, actnode, i;
107
igraph_vector_t edges;
108
igraph_vector_t *inneis, *outneis;
109
igraph_i_forest_fire_data_t data;
110
igraph_dqueue_t neiq;
112
igraph_real_t param_geom_out=1-fw_prob;
113
igraph_real_t param_geom_in=1-fw_prob*bw_factor;
116
IGRAPH_ERROR("Forest fire model: 'fw_prob' should be between non-negative",
120
IGRAPH_ERROR("Forest fire model: 'bw_factor' should be non-negative",
124
IGRAPH_ERROR("Number of ambassadors ('ambs') should be non-negative",
128
if (fw_prob == 0 || ambs == 0) {
129
IGRAPH_WARNING("'fw_prob or ambs is zero, creating empty graph");
130
IGRAPH_CHECK(igraph_empty(graph, nodes, directed));
134
IGRAPH_VECTOR_INIT_FINALLY(&edges, 0);
136
inneis=igraph_Calloc(no_of_nodes, igraph_vector_t);
138
IGRAPH_ERROR("Cannot run forest fire model", IGRAPH_ENOMEM);
140
IGRAPH_FINALLY(igraph_free, inneis);
141
outneis=igraph_Calloc(no_of_nodes, igraph_vector_t);
143
IGRAPH_ERROR("Cannot run forest fire model", IGRAPH_ENOMEM);
145
IGRAPH_FINALLY(igraph_free, outneis);
147
data.outneis=outneis;
148
data.no_of_nodes=no_of_nodes;
149
IGRAPH_FINALLY(igraph_i_forest_fire_free, &data);
150
for (i=0; i<no_of_nodes; i++) {
151
IGRAPH_CHECK(igraph_vector_init(inneis+i, 0));
152
IGRAPH_CHECK(igraph_vector_init(outneis+i, 0));
155
IGRAPH_CHECK(igraph_vector_long_init(&visited, no_of_nodes));
156
IGRAPH_FINALLY(igraph_vector_long_destroy, &visited);
157
IGRAPH_DQUEUE_INIT_FINALLY(&neiq, 10);
161
#define ADD_EDGE_TO(nei) \
162
if (VECTOR(visited)[(nei)] != actnode+1) { \
163
VECTOR(visited)[(nei)] = actnode+1; \
164
IGRAPH_CHECK(igraph_dqueue_push(&neiq, nei)); \
165
IGRAPH_CHECK(igraph_vector_push_back(&edges, actnode)); \
166
IGRAPH_CHECK(igraph_vector_push_back(&edges, nei)); \
167
IGRAPH_CHECK(igraph_vector_push_back(outneis+actnode, nei)); \
168
IGRAPH_CHECK(igraph_vector_push_back(inneis+nei, actnode)); \
171
IGRAPH_PROGRESS("Forest fire: ", 0.0, NULL);
173
for (actnode=1; actnode < no_of_nodes; actnode++) {
175
IGRAPH_PROGRESS("Forest fire: ", 100.0*actnode/no_of_nodes, NULL);
177
IGRAPH_ALLOW_INTERRUPTION();
179
/* We don't want to visit the current vertex */
180
VECTOR(visited)[actnode] = actnode+1;
182
/* Choose ambassador(s) */
183
for (i=0; i<ambs; i++) {
184
long int a=RNG_INTEGER(0, actnode-1);
188
while (!igraph_dqueue_empty(&neiq)) {
189
long int actamb=igraph_dqueue_pop(&neiq);
190
igraph_vector_t *outv=outneis+actamb;
191
igraph_vector_t *inv=inneis+actamb;
192
long int no_in=igraph_vector_size(inv);
193
long int no_out=igraph_vector_size(outv);
194
long int neis_out=RNG_GEOM(param_geom_out);
195
long int neis_in=RNG_GEOM(param_geom_in);
196
/* outgoing neighbors */
197
if (neis_out >= no_out) {
198
for (i=0; i<no_out; i++) {
199
long int nei=VECTOR(*outv)[i];
203
long int oleft=no_out;
204
for (i=0; i<neis_out && oleft > 0; ) {
205
long int which=RNG_INTEGER(0, oleft-1);
206
long int nei=VECTOR(*outv)[which];
207
VECTOR(*outv)[which] = VECTOR(*outv)[oleft-1];
208
VECTOR(*outv)[oleft-1] = nei;
209
if (VECTOR(visited)[nei] != actnode+1) {
216
/* incoming neighbors */
217
if (neis_in >= no_in) {
218
for (i=0; i<no_in; i++) {
219
long int nei=VECTOR(*inv)[i];
223
long int ileft=no_in;
224
for (i=0; i<neis_in && ileft > 0; ) {
225
long int which=RNG_INTEGER(0, ileft-1);
226
long int nei=VECTOR(*inv)[which];
227
VECTOR(*inv)[which] = VECTOR(*inv)[ileft-1];
228
VECTOR(*inv)[ileft-1] = which;
229
if (VECTOR(visited)[nei] != actnode+1) {
237
} /* while neiq not empty */
239
} /* actnode < no_of_nodes */
245
IGRAPH_PROGRESS("Forest fire: ", 100.0, NULL);
247
igraph_dqueue_destroy(&neiq);
248
igraph_vector_long_destroy(&visited);
249
igraph_i_forest_fire_free(&data);
250
igraph_free(outneis);
252
IGRAPH_FINALLY_CLEAN(5);
254
IGRAPH_CHECK(igraph_create(graph, &edges, nodes, directed));
255
igraph_vector_destroy(&edges);
256
IGRAPH_FINALLY_CLEAN(1);
added
removed
src/forestfire.c
