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(&degree, 0);
293         igraph_degree(graph, &degree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1);
294         igraph_vector_add_constant(&degree, -1);
295         igraph_assortativity(graph, &degree, 0, res, /*directed=*/ 0);
296         igraph_vector_destroy(&degree);
297     }
298 
299     return 0;
300 }
301