1 /* -*- mode: C -*- */
2 /* vim:set ts=4 sw=4 sts=4 et: */
3 /*
4 IGraph library.
5 Copyright (C) 2005-2021 The igraph development team
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_centrality.h"
25
26 #include "igraph_interface.h"
27
28 /**
29 * \function igraph_constraint
30 * \brief Burt's constraint scores.
31 *
32 * </para><para>
33 * This function calculates Burt's constraint scores for the given
34 * vertices, also known as structural holes.
35 *
36 * </para><para>
37 * Burt's constraint is higher if ego has less, or mutually stronger
38 * related (i.e. more redundant) contacts. Burt's measure of
39 * constraint, C[i], of vertex i's ego network V[i], is defined for
40 * directed and valued graphs,
41 * <blockquote><para>
42 * C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in
43 * V[], j != i)
44 * </para></blockquote>
45 * for a graph of order (i.e. number of vertices) N, where proportional
46 * tie strengths are defined as
47 * <blockquote><para>
48 * p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i),
49 * </para></blockquote>
50 * a[i,j] are elements of A and
51 * the latter being the graph adjacency matrix. For isolated vertices,
52 * constraint is undefined.
53 *
54 * </para><para>
55 * Burt, R.S. (2004). Structural holes and good ideas. American
56 * Journal of Sociology 110, 349-399.
57 *
58 * </para><para>
59 * The first R version of this function was contributed by Jeroen
60 * Bruggeman.
61 * \param graph A graph object.
62 * \param res Pointer to an initialized vector, the result will be
63 * stored here. The vector will be resized to have the
64 * appropriate size for holding the result.
65 * \param vids Vertex selector containing the vertices for which the
66 * constraint should be calculated.
67 * \param weights Vector giving the weights of the edges. If it is
68 * \c NULL then each edge is supposed to have the same weight.
69 * \return Error code.
70 *
71 * Time complexity: O(|V|+E|+n*d^2), n is the number of vertices for
72 * which the constraint is calculated and d is the average degree, |V|
73 * is the number of vertices, |E| the number of edges in the
74 * graph. If the weights argument is \c NULL then the time complexity
75 * is O(|V|+n*d^2).
76 */
igraph_constraint(const igraph_t * graph,igraph_vector_t * res,igraph_vs_t vids,const igraph_vector_t * weights)77 int igraph_constraint(const igraph_t *graph, igraph_vector_t *res,
78 igraph_vs_t vids, const igraph_vector_t *weights) {
79
80 long int no_of_nodes = igraph_vcount(graph);
81 long int no_of_edges = igraph_ecount(graph);
82 igraph_vit_t vit;
83 long int nodes_to_calc;
84 long int a, b, c, i, j, q, vsize, vsize2;
85 igraph_integer_t edge, from, to, edge2;
86
87 igraph_vector_t contrib;
88 igraph_vector_t degree;
89 igraph_vector_t ineis_in, ineis_out, jneis_in, jneis_out;
90
91 if (weights != 0 && igraph_vector_size(weights) != no_of_edges) {
92 IGRAPH_ERROR("Invalid length of weight vector", IGRAPH_EINVAL);
93 }
94
95 IGRAPH_VECTOR_INIT_FINALLY(&contrib, no_of_nodes);
96 IGRAPH_VECTOR_INIT_FINALLY(°ree, no_of_nodes);
97 IGRAPH_VECTOR_INIT_FINALLY(&ineis_in, 0);
98 IGRAPH_VECTOR_INIT_FINALLY(&ineis_out, 0);
99 IGRAPH_VECTOR_INIT_FINALLY(&jneis_in, 0);
100 IGRAPH_VECTOR_INIT_FINALLY(&jneis_out, 0);
101
102 IGRAPH_CHECK(igraph_vit_create(graph, vids, &vit));
103 IGRAPH_FINALLY(igraph_vit_destroy, &vit);
104 nodes_to_calc = IGRAPH_VIT_SIZE(vit);
105
106 if (weights == 0) {
107 IGRAPH_CHECK(igraph_degree(graph, °ree, igraph_vss_all(),
108 IGRAPH_ALL, IGRAPH_NO_LOOPS));
109 } else {
110 for (a = 0; a < no_of_edges; a++) {
111 igraph_edge(graph, (igraph_integer_t) a, &from, &to);
112 if (from != to) {
113 VECTOR(degree)[(long int) from] += VECTOR(*weights)[a];
114 VECTOR(degree)[(long int) to ] += VECTOR(*weights)[a];
115 }
116 }
117 }
118
119 IGRAPH_CHECK(igraph_vector_resize(res, nodes_to_calc));
120 igraph_vector_null(res);
121
122 for (a = 0; a < nodes_to_calc; a++, IGRAPH_VIT_NEXT(vit)) {
123 i = IGRAPH_VIT_GET(vit);
124
125 /* get neighbors of i */
126 IGRAPH_CHECK(igraph_incident(graph, &ineis_in, (igraph_integer_t) i,
127 IGRAPH_IN));
128 IGRAPH_CHECK(igraph_incident(graph, &ineis_out, (igraph_integer_t) i,
129 IGRAPH_OUT));
130
131 /* NaN for isolates */
132 if (igraph_vector_size(&ineis_in) == 0 &&
133 igraph_vector_size(&ineis_out) == 0) {
134 VECTOR(*res)[a] = IGRAPH_NAN;
135 }
136
137 /* zero their contribution */
138 vsize = igraph_vector_size(&ineis_in);
139 for (b = 0; b < vsize; b++) {
140 edge = (igraph_integer_t) VECTOR(ineis_in)[b];
141 j = (long int) IGRAPH_OTHER(graph, edge, i);
142 VECTOR(contrib)[j] = 0.0;
143 }
144 vsize = igraph_vector_size(&ineis_out);
145 for (b = 0; b < vsize; b++) {
146 edge = (igraph_integer_t) VECTOR(ineis_out)[b];
147 j = (long int) IGRAPH_OTHER(graph, edge, i);
148 VECTOR(contrib)[j] = 0.0;
149 }
150
151 /* add the direct contributions, in-neighbors and out-neighbors */
152 vsize = igraph_vector_size(&ineis_in);
153 for (b = 0; b < vsize; b++) {
154 edge = (igraph_integer_t) VECTOR(ineis_in)[b];
155 j = (long int) IGRAPH_OTHER(graph, edge, i);
156 if (i != j) { /* excluding loops */
157 if (weights) {
158 VECTOR(contrib)[j] +=
159 VECTOR(*weights)[(long int)edge] / VECTOR(degree)[i];
160 } else {
161 VECTOR(contrib)[j] += 1.0 / VECTOR(degree)[i];
162 }
163 }
164 }
165 if (igraph_is_directed(graph)) {
166 vsize = igraph_vector_size(&ineis_out);
167 for (b = 0; b < vsize; b++) {
168 edge = (igraph_integer_t) VECTOR(ineis_out)[b];
169 j = (long int) IGRAPH_OTHER(graph, edge, i);
170 if (i != j) {
171 if (weights) {
172 VECTOR(contrib)[j] +=
173 VECTOR(*weights)[(long int)edge] / VECTOR(degree)[i];
174 } else {
175 VECTOR(contrib)[j] += 1.0 / VECTOR(degree)[i];
176 }
177 }
178 }
179 }
180
181 /* add the indirect contributions, in-in, in-out, out-in, out-out */
182 vsize = igraph_vector_size(&ineis_in);
183 for (b = 0; b < vsize; b++) {
184 edge = (igraph_integer_t) VECTOR(ineis_in)[b];
185 j = (long int) IGRAPH_OTHER(graph, edge, i);
186 if (i == j) {
187 continue;
188 }
189 IGRAPH_CHECK(igraph_incident(graph, &jneis_in, (igraph_integer_t) j,
190 IGRAPH_IN));
191 IGRAPH_CHECK(igraph_incident(graph, &jneis_out, (igraph_integer_t) j,
192 IGRAPH_OUT));
193 vsize2 = igraph_vector_size(&jneis_in);
194 for (c = 0; c < vsize2; c++) {
195 edge2 = (igraph_integer_t) VECTOR(jneis_in)[c];
196 q = (long int) IGRAPH_OTHER(graph, edge2, j);
197 if (j != q) {
198 if (weights) {
199 VECTOR(contrib)[q] +=
200 VECTOR(*weights)[(long int)edge] *
201 VECTOR(*weights)[(long int)edge2] /
202 VECTOR(degree)[i] / VECTOR(degree)[j];
203 } else {
204 VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
205 }
206 }
207 }
208 if (igraph_is_directed(graph)) {
209 vsize2 = igraph_vector_size(&jneis_out);
210 for (c = 0; c < vsize2; c++) {
211 edge2 = (igraph_integer_t) VECTOR(jneis_out)[c];
212 q = (long int) IGRAPH_OTHER(graph, edge2, j);
213 if (j != q) {
214 if (weights) {
215 VECTOR(contrib)[q] +=
216 VECTOR(*weights)[(long int)edge] *
217 VECTOR(*weights)[(long int)edge2] /
218 VECTOR(degree)[i] / VECTOR(degree)[j];
219 } else {
220 VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
221 }
222 }
223 }
224 }
225 }
226 if (igraph_is_directed(graph)) {
227 vsize = igraph_vector_size(&ineis_out);
228 for (b = 0; b < vsize; b++) {
229 edge = (igraph_integer_t) VECTOR(ineis_out)[b];
230 j = (long int) IGRAPH_OTHER(graph, edge, i);
231 if (i == j) {
232 continue;
233 }
234 IGRAPH_CHECK(igraph_incident(graph, &jneis_in, (igraph_integer_t) j,
235 IGRAPH_IN));
236 IGRAPH_CHECK(igraph_incident(graph, &jneis_out, (igraph_integer_t) j,
237 IGRAPH_OUT));
238 vsize2 = igraph_vector_size(&jneis_in);
239 for (c = 0; c < vsize2; c++) {
240 edge2 = (igraph_integer_t) VECTOR(jneis_in)[c];
241 q = (long int) IGRAPH_OTHER(graph, edge2, j);
242 if (j != q) {
243 if (weights) {
244 VECTOR(contrib)[q] +=
245 VECTOR(*weights)[(long int)edge] *
246 VECTOR(*weights)[(long int)edge2] /
247 VECTOR(degree)[i] / VECTOR(degree)[j];
248 } else {
249 VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
250 }
251 }
252 }
253 vsize2 = igraph_vector_size(&jneis_out);
254 for (c = 0; c < vsize2; c++) {
255 edge2 = (igraph_integer_t) VECTOR(jneis_out)[c];
256 q = (long int) IGRAPH_OTHER(graph, edge2, j);
257 if (j != q) {
258 if (weights) {
259 VECTOR(contrib)[q] +=
260 VECTOR(*weights)[(long int)edge] *
261 VECTOR(*weights)[(long int)edge2] /
262 VECTOR(degree)[i] / VECTOR(degree)[j];
263 } else {
264 VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
265 }
266 }
267 }
268 }
269 }
270
271 /* squared sum of the contributions */
272 vsize = igraph_vector_size(&ineis_in);
273 for (b = 0; b < vsize; b++) {
274 edge = (igraph_integer_t) VECTOR(ineis_in)[b];
275 j = (long int) IGRAPH_OTHER(graph, edge, i);
276 if (i == j) {
277 continue;
278 }
279 VECTOR(*res)[a] += VECTOR(contrib)[j] * VECTOR(contrib)[j];
280 VECTOR(contrib)[j] = 0.0;
281 }
282 if (igraph_is_directed(graph)) {
283 vsize = igraph_vector_size(&ineis_out);
284 for (b = 0; b < vsize; b++) {
285 edge = (igraph_integer_t) VECTOR(ineis_out)[b];
286 j = (long int) IGRAPH_OTHER(graph, edge, i);
287 if (i == j) {
288 continue;
289 }
290 VECTOR(*res)[a] += VECTOR(contrib)[j] * VECTOR(contrib)[j];
291 VECTOR(contrib)[j] = 0.0;
292 }
293 }
294 }
295
296 igraph_vit_destroy(&vit);
297 igraph_vector_destroy(&jneis_out);
298 igraph_vector_destroy(&jneis_in);
299 igraph_vector_destroy(&ineis_out);
300 igraph_vector_destroy(&ineis_in);
301 igraph_vector_destroy(°ree);
302 igraph_vector_destroy(&contrib);
303 IGRAPH_FINALLY_CLEAN(7);
304
305 return 0;
306 }
307