1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com>
5 334 Harvard street, Cambridge, MA 02139 USA
6
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.
11
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.
16
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
20 02110-1301 USA
21
22 */
23
24 #include "igraph_mixing.h"
25 #include "igraph_interface.h"
26
27 /**
28 * \function igraph_assortativity_nominal
29 * Assortativity of a graph based on vertex categories
30 *
31 * Assuming the vertices of the input graph belong to different
32 * categories, this function calculates the assortativity coefficient of
33 * the graph. The assortativity coefficient is between minus one and one
34 * and it is one if all connections stay within categories, it is
35 * minus one, if the network is perfectly disassortative. For a
36 * randomly connected network it is (asymptotically) zero.
37 *
38 * </para><para>See equation (2) in M. E. J. Newman: Mixing patterns
39 * in networks, Phys. Rev. E 67, 026126 (2003)
40 * (http://arxiv.org/abs/cond-mat/0209450) for the proper
41 * definition.
42 *
43 * \param graph The input graph, it can be directed or undirected.
44 * \param types Vector giving the vertex types. They are assumed to be
45 * integer numbers, starting with zero.
46 * \param res Pointer to a real variable, the result is stored here.
47 * \param directed Boolean, it gives whether to consider edge
48 * directions in a directed graph. It is ignored for undirected
49 * graphs.
50 * \return Error code.
51 *
52 * Time complexity: O(|E|+t), |E| is the number of edges, t is the
53 * number of vertex types.
54 *
55 * \sa \ref igraph_assortativity if the vertex types are defines by
56 * numeric values (e.g. vertex degree), instead of categories.
57 *
58 * \example examples/simple/assortativity.c
59 */
60
igraph_assortativity_nominal(const igraph_t * graph,const igraph_vector_t * types,igraph_real_t * res,igraph_bool_t directed)61 int igraph_assortativity_nominal(const igraph_t *graph,
62 const igraph_vector_t *types,
63 igraph_real_t *res,
64 igraph_bool_t directed) {
65
66 long int no_of_nodes = igraph_vcount(graph);
67 long int no_of_edges = igraph_ecount(graph);
68 long int no_of_types;
69 igraph_vector_t ai, bi, eii;
70 long int e, i;
71 igraph_real_t sumaibi = 0.0, sumeii = 0.0;
72
73 if (igraph_vector_size(types) != no_of_nodes) {
74 IGRAPH_ERROR("Invalid `types' vector length", IGRAPH_EINVAL);
75 }
76
77 if (igraph_vector_min(types) < 0) {
78 IGRAPH_ERROR("Invalid `types' vector", IGRAPH_EINVAL);
79 }
80
81 directed = directed && igraph_is_directed(graph);
82
83 no_of_types = (long int) igraph_vector_max(types) + 1;
84 IGRAPH_VECTOR_INIT_FINALLY(&ai, no_of_types);
85 IGRAPH_VECTOR_INIT_FINALLY(&bi, no_of_types);
86 IGRAPH_VECTOR_INIT_FINALLY(&eii, no_of_types);
87
88 for (e = 0; e < no_of_edges; e++) {
89 long int from = IGRAPH_FROM(graph, e);
90 long int to = IGRAPH_TO(graph, e);
91 long int from_type = (long int) VECTOR(*types)[from];
92 long int to_type = (long int) VECTOR(*types)[to];
93
94 VECTOR(ai)[from_type] += 1;
95 VECTOR(bi)[to_type] += 1;
96 if (from_type == to_type) {
97 VECTOR(eii)[from_type] += 1;
98 }
99 if (!directed) {
100 if (from_type == to_type) {
101 VECTOR(eii)[from_type] += 1;
102 }
103 VECTOR(ai)[to_type] += 1;
104 VECTOR(bi)[from_type] += 1;
105 }
106 }
107
108 for (i = 0; i < no_of_types; i++) {
109 sumaibi += (VECTOR(ai)[i] / no_of_edges) * (VECTOR(bi)[i] / no_of_edges);
110 sumeii += (VECTOR(eii)[i] / no_of_edges);
111 }
112
113 if (!directed) {
114 sumaibi /= 4.0;
115 sumeii /= 2.0;
116 }
117
118 *res = (sumeii - sumaibi) / (1.0 - sumaibi);
119
120 igraph_vector_destroy(&eii);
121 igraph_vector_destroy(&bi);
122 igraph_vector_destroy(&ai);
123 IGRAPH_FINALLY_CLEAN(3);
124
125 return 0;
126 }
127
128 /**
129 * \function igraph_assortativity
130 * Assortativity based on numeric properties of vertices
131 *
132 * This function calculates the assortativity coefficient of the input
133 * graph. This coefficient is basically the correlation between the
134 * actual connectivity patterns of the vertices and the pattern
135 * expected from the distribution of the vertex types.
136 *
137 * </para><para>See equation (21) in M. E. J. Newman: Mixing patterns
138 * in networks, Phys. Rev. E 67, 026126 (2003)
139 * (http://arxiv.org/abs/cond-mat/0209450) for the proper
140 * definition. The actual calculation is performed using equation (26)
141 * in the same paper for directed graphs, and equation (4) in
142 * M. E. J. Newman: Assortative mixing in networks,
143 * Phys. Rev. Lett. 89, 208701 (2002)
144 * (http://arxiv.org/abs/cond-mat/0205405/) for undirected graphs.
145 *
146 * \param graph The input graph, it can be directed or undirected.
147 * \param types1 The vertex values, these can be arbitrary numeric
148 * values.
149 * \param types2 A second value vector to be using for the incoming
150 * edges when calculating assortativity for a directed graph.
151 * Supply a null pointer here if you want to use the same values
152 * for outgoing and incoming edges. This argument is ignored
153 * (with a warning) if it is not a null pointer and undirected
154 * assortativity coefficient is being calculated.
155 * \param res Pointer to a real variable, the result is stored here.
156 * \param directed Boolean, whether to consider edge directions for
157 * directed graphs. It is ignored for undirected graphs.
158 * \return Error code.
159 *
160 * Time complexity: O(|E|), linear in the number of edges of the
161 * graph.
162 *
163 * \sa \ref igraph_assortativity_nominal() if you have discrete vertex
164 * categories instead of numeric labels, and \ref
165 * igraph_assortativity_degree() for the special case of assortativity
166 * based on vertex degree.
167 *
168 * \example examples/simple/assortativity.c
169 */
170
igraph_assortativity(const igraph_t * graph,const igraph_vector_t * types1,const igraph_vector_t * types2,igraph_real_t * res,igraph_bool_t directed)171 int igraph_assortativity(const igraph_t *graph,
172 const igraph_vector_t *types1,
173 const igraph_vector_t *types2,
174 igraph_real_t *res,
175 igraph_bool_t directed) {
176
177 long int no_of_nodes = igraph_vcount(graph);
178 long int no_of_edges = igraph_ecount(graph);
179 long int e;
180
181 directed = directed && igraph_is_directed(graph);
182
183 if (!directed && types2) {
184 IGRAPH_WARNING("Only `types1' is used for undirected case");
185 }
186
187 if (igraph_vector_size(types1) != no_of_nodes) {
188 IGRAPH_ERROR("Invalid `types1' vector length", IGRAPH_EINVAL);
189 }
190
191 if (types2 && igraph_vector_size(types2) != no_of_nodes) {
192 IGRAPH_ERROR("Invalid `types2' vector length", IGRAPH_EINVAL);
193 }
194
195 if (!directed) {
196 igraph_real_t num1 = 0.0, num2 = 0.0, den1 = 0.0;
197
198 for (e = 0; e < no_of_edges; e++) {
199 long int from = IGRAPH_FROM(graph, e);
200 long int to = IGRAPH_TO(graph, e);
201 igraph_real_t from_type = VECTOR(*types1)[from];
202 igraph_real_t to_type = VECTOR(*types1)[to];
203
204 num1 += from_type * to_type;
205 num2 += from_type + to_type;
206 den1 += from_type * from_type + to_type * to_type;
207 }
208
209 num1 /= no_of_edges;
210 den1 /= no_of_edges * 2;
211 num2 /= no_of_edges * 2;
212 num2 = num2 * num2;
213
214 *res = (num1 - num2) / (den1 - num2);
215
216 } else {
217 igraph_real_t num1 = 0.0, num2 = 0.0, num3 = 0.0,
218 den1 = 0.0, den2 = 0.0;
219 igraph_real_t num, den;
220
221 if (!types2) {
222 types2 = types1;
223 }
224
225 for (e = 0; e < no_of_edges; e++) {
226 long int from = IGRAPH_FROM(graph, e);
227 long int to = IGRAPH_TO(graph, e);
228 igraph_real_t from_type = VECTOR(*types1)[from];
229 igraph_real_t to_type = VECTOR(*types2)[to];
230
231 num1 += from_type * to_type;
232 num2 += from_type;
233 num3 += to_type;
234 den1 += from_type * from_type;
235 den2 += to_type * to_type;
236 }
237
238 num = num1 - num2 * num3 / no_of_edges;
239 den = sqrt(den1 - num2 * num2 / no_of_edges) *
240 sqrt(den2 - num3 * num3 / no_of_edges);
241
242 *res = num / den;
243 }
244
245 return 0;
246 }
247
248 /**
249 * \function igraph_assortativity_degree
250 * Assortativity of a graph based on vertex degree
251 *
252 * Assortativity based on vertex degree, please see the discussion at
253 * the documentation of \ref igraph_assortativity() for details.
254 *
255 * \param graph The input graph, it can be directed or undirected.
256 * \param res Pointer to a real variable, the result is stored here.
257 * \param directed Boolean, whether to consider edge directions for
258 * directed graphs. This argument is ignored for undirected
259 * graphs. Supply 1 (=TRUE) here to do the natural thing, i.e. use
260 * directed version of the measure for directed graphs and the
261 * undirected version for undirected graphs.
262 * \return Error code.
263 *
264 * Time complexity: O(|E|+|V|), |E| is the number of edges, |V| is
265 * the number of vertices.
266 *
267 * \sa \ref igraph_assortativity() for the general function
268 * calculating assortativity for any kind of numeric vertex values.
269 *
270 * \example examples/simple/assortativity.c
271 */
272
igraph_assortativity_degree(const igraph_t * graph,igraph_real_t * res,igraph_bool_t directed)273 int igraph_assortativity_degree(const igraph_t *graph,
274 igraph_real_t *res,
275 igraph_bool_t directed) {
276
277 directed = directed && igraph_is_directed(graph);
278
279 if (directed) {
280 igraph_vector_t indegree, outdegree;
281 igraph_vector_init(&indegree, 0);
282 igraph_vector_init(&outdegree, 0);
283 igraph_degree(graph, &indegree, igraph_vss_all(), IGRAPH_IN, /*loops=*/ 1);
284 igraph_degree(graph, &outdegree, igraph_vss_all(), IGRAPH_OUT, /*loops=*/ 1);
285 igraph_vector_add_constant(&indegree, -1);
286 igraph_vector_add_constant(&outdegree, -1);
287 igraph_assortativity(graph, &outdegree, &indegree, res, /*directed=*/ 1);
288 igraph_vector_destroy(&indegree);
289 igraph_vector_destroy(&outdegree);
290 } else {
291 igraph_vector_t degree;
292 igraph_vector_init(°ree, 0);
293 igraph_degree(graph, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1);
294 igraph_vector_add_constant(°ree, -1);
295 igraph_assortativity(graph, °ree, 0, res, /*directed=*/ 0);
296 igraph_vector_destroy(°ree);
297 }
298
299 return 0;
300 }
301