/src/igraph/src/properties/constraint.c

Source
/*
   igraph library.
   Copyright (C) 2005-2021 The igraph development team

   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_centrality.h"

#include "igraph_interface.h"
#include "igraph_structural.h"

/**
 * \function igraph_constraint
 * \brief Burt's constraint scores.
 *
 * </para><para>
 * This function calculates Burt's constraint scores for the given
 * vertices, also known as structural holes.
 *
 * </para><para>
 * Burt's constraint is higher if ego has less, or mutually stronger
 * related (i.e. more redundant) contacts. Burt's measure of
 * constraint, C[i], of vertex i's ego network V[i], is defined for
 * directed and valued graphs,
 * <blockquote><para>
 * C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in
 * V[], j != i)
 * </para></blockquote>
 * for a graph of order (i.e. number of vertices) N, where proportional
 * tie strengths are defined as
 * <blockquote><para>
 * p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i),
 * </para></blockquote>
 * a[i,j] are elements of A and
 * the latter being the graph adjacency matrix. For isolated vertices,
 * constraint is undefined.
 *
 * </para><para>
 * Burt, R.S. (2004). Structural holes and good ideas. American
 * Journal of Sociology 110, 349-399.
 *
 * </para><para>
 * The first R version of this function was contributed by Jeroen
 * Bruggeman.
 * \param graph A graph object.
 * \param res Pointer to an initialized vector, the result will be
 *        stored here. The vector will be resized to have the
 *        appropriate size for holding the result.
 * \param vids Vertex selector containing the vertices for which the
 *        constraint should be calculated.
 * \param weights Vector giving the weights of the edges. If it is
 *        \c NULL then each edge is supposed to have the same weight.
 * \return Error code.
 *
 * Time complexity: O(|V|+E|+n*d^2), n is the number of vertices for
 * which the constraint is calculated and d is the average degree, |V|
 * is the number of vertices, |E| the number of edges in the
 * graph. If the weights argument is \c NULL then the time complexity
 * is O(|V|+n*d^2).
 */
igraph_error_t igraph_constraint(const igraph_t *graph, igraph_vector_t *res,
                      igraph_vs_t vids, const igraph_vector_t *weights) {

    igraph_int_t no_of_nodes = igraph_vcount(graph);
    igraph_int_t no_of_edges = igraph_ecount(graph);
    igraph_vit_t vit;
    igraph_int_t nodes_to_calc;
    igraph_int_t a, b, c, i, j, q, vsize, vsize2;
    igraph_int_t edge, edge2;

    igraph_vector_t contrib;
    igraph_vector_t degree;
    igraph_vector_int_t ineis_in, ineis_out, jneis_in, jneis_out;

    if (weights != 0 && igraph_vector_size(weights) != no_of_edges) {
        IGRAPH_ERROR("Invalid length of weight vector", IGRAPH_EINVAL);
    }

    IGRAPH_VECTOR_INIT_FINALLY(&contrib, no_of_nodes);
    IGRAPH_VECTOR_INIT_FINALLY(&degree, no_of_nodes);
    IGRAPH_VECTOR_INT_INIT_FINALLY(&ineis_in, 0);
    IGRAPH_VECTOR_INT_INIT_FINALLY(&ineis_out, 0);
    IGRAPH_VECTOR_INT_INIT_FINALLY(&jneis_in, 0);
    IGRAPH_VECTOR_INT_INIT_FINALLY(&jneis_out, 0);

    IGRAPH_CHECK(igraph_vit_create(graph, vids, &vit));
    IGRAPH_FINALLY(igraph_vit_destroy, &vit);
    nodes_to_calc = IGRAPH_VIT_SIZE(vit);

    IGRAPH_CHECK(igraph_strength(graph, &degree, igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS, weights));

    IGRAPH_CHECK(igraph_vector_resize(res, nodes_to_calc));
    igraph_vector_null(res);

    for (a = 0; a < nodes_to_calc; a++, IGRAPH_VIT_NEXT(vit)) {
        i = IGRAPH_VIT_GET(vit);

        /* get neighbors of i */
        IGRAPH_CHECK(igraph_incident(graph, &ineis_in, i, IGRAPH_IN, IGRAPH_LOOPS));
        IGRAPH_CHECK(igraph_incident(graph, &ineis_out, i, IGRAPH_OUT, IGRAPH_LOOPS));

        /* NaN for isolates */
        if (igraph_vector_int_size(&ineis_in) == 0 &&
            igraph_vector_int_size(&ineis_out) == 0) {
            VECTOR(*res)[a] = IGRAPH_NAN;
        }

        /* zero their contribution */
        vsize = igraph_vector_int_size(&ineis_in);
        for (b = 0; b < vsize; b++) {
            edge = VECTOR(ineis_in)[b];
            j = IGRAPH_OTHER(graph, edge, i);
            VECTOR(contrib)[j] = 0.0;
        }
        vsize = igraph_vector_int_size(&ineis_out);
        for (b = 0; b < vsize; b++) {
            edge = VECTOR(ineis_out)[b];
            j = IGRAPH_OTHER(graph, edge, i);
            VECTOR(contrib)[j] = 0.0;
        }

        /* add the direct contributions, in-neighbors and out-neighbors */
        vsize = igraph_vector_int_size(&ineis_in);
        for (b = 0; b < vsize; b++) {
            edge = VECTOR(ineis_in)[b];
            j = IGRAPH_OTHER(graph, edge, i);
            if (i != j) {     /* excluding loops */
                if (weights) {
                    VECTOR(contrib)[j] +=
                        VECTOR(*weights)[edge] / VECTOR(degree)[i];
                } else {
                    VECTOR(contrib)[j] += 1.0 / VECTOR(degree)[i];
                }
            }
        }
        if (igraph_is_directed(graph)) {
            vsize = igraph_vector_int_size(&ineis_out);
            for (b = 0; b < vsize; b++) {
                edge = VECTOR(ineis_out)[b];
                j = IGRAPH_OTHER(graph, edge, i);
                if (i != j) {
                    if (weights) {
                        VECTOR(contrib)[j] +=
                            VECTOR(*weights)[edge] / VECTOR(degree)[i];
                    } else {
                        VECTOR(contrib)[j] += 1.0 / VECTOR(degree)[i];
                    }
                }
            }
        }

        /* add the indirect contributions, in-in, in-out, out-in, out-out */
        vsize = igraph_vector_int_size(&ineis_in);
        for (b = 0; b < vsize; b++) {
            edge = VECTOR(ineis_in)[b];
            j = IGRAPH_OTHER(graph, edge, i);
            if (i == j) {
                continue;
            }
            IGRAPH_CHECK(igraph_incident(graph, &jneis_in, j, IGRAPH_IN, IGRAPH_LOOPS));
            IGRAPH_CHECK(igraph_incident(graph, &jneis_out, j, IGRAPH_OUT, IGRAPH_LOOPS));
            vsize2 = igraph_vector_int_size(&jneis_in);
            for (c = 0; c < vsize2; c++) {
                edge2 = VECTOR(jneis_in)[c];
                q = IGRAPH_OTHER(graph, edge2, j);
                if (j != q) {
                    if (weights) {
                        VECTOR(contrib)[q] +=
                            VECTOR(*weights)[edge] *
                            VECTOR(*weights)[edge2] /
                            VECTOR(degree)[i] / VECTOR(degree)[j];
                    } else {
                        VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
                    }
                }
            }
            if (igraph_is_directed(graph)) {
                vsize2 = igraph_vector_int_size(&jneis_out);
                for (c = 0; c < vsize2; c++) {
                    edge2 = VECTOR(jneis_out)[c];
                    q = IGRAPH_OTHER(graph, edge2, j);
                    if (j != q) {
                        if (weights) {
                            VECTOR(contrib)[q] +=
                                VECTOR(*weights)[edge] *
                                VECTOR(*weights)[edge2] /
                                VECTOR(degree)[i] / VECTOR(degree)[j];
                        } else {
                            VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
                        }
                    }
                }
            }
        }
        if (igraph_is_directed(graph)) {
            vsize = igraph_vector_int_size(&ineis_out);
            for (b = 0; b < vsize; b++) {
                edge = VECTOR(ineis_out)[b];
                j = IGRAPH_OTHER(graph, edge, i);
                if (i == j) {
                    continue;
                }
                IGRAPH_CHECK(igraph_incident(graph, &jneis_in, j, IGRAPH_IN, IGRAPH_LOOPS));
                IGRAPH_CHECK(igraph_incident(graph, &jneis_out, j, IGRAPH_OUT, IGRAPH_LOOPS));
                vsize2 = igraph_vector_int_size(&jneis_in);
                for (c = 0; c < vsize2; c++) {
                    edge2 = VECTOR(jneis_in)[c];
                    q = IGRAPH_OTHER(graph, edge2, j);
                    if (j != q) {
                        if (weights) {
                            VECTOR(contrib)[q] +=
                                VECTOR(*weights)[edge] *
                                VECTOR(*weights)[edge2] /
                                VECTOR(degree)[i] / VECTOR(degree)[j];
                        } else {
                            VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
                        }
                    }
                }
                vsize2 = igraph_vector_int_size(&jneis_out);
                for (c = 0; c < vsize2; c++) {
                    edge2 = VECTOR(jneis_out)[c];
                    q = IGRAPH_OTHER(graph, edge2, j);
                    if (j != q) {
                        if (weights) {
                            VECTOR(contrib)[q] +=
                                VECTOR(*weights)[edge] *
                                VECTOR(*weights)[edge2] /
                                VECTOR(degree)[i] / VECTOR(degree)[j];
                        } else {
                            VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
                        }
                    }
                }
            }
        }

        /* squared sum of the contributions */
        vsize = igraph_vector_int_size(&ineis_in);
        for (b = 0; b < vsize; b++) {
            edge = VECTOR(ineis_in)[b];
            j = IGRAPH_OTHER(graph, edge, i);
            if (i == j) {
                continue;
            }
            VECTOR(*res)[a] += VECTOR(contrib)[j] * VECTOR(contrib)[j];
            VECTOR(contrib)[j] = 0.0;
        }
        if (igraph_is_directed(graph)) {
            vsize =  igraph_vector_int_size(&ineis_out);
            for (b = 0; b < vsize; b++) {
                edge = VECTOR(ineis_out)[b];
                j = IGRAPH_OTHER(graph, edge, i);
                if (i == j) {
                    continue;
                }
                VECTOR(*res)[a] += VECTOR(contrib)[j] * VECTOR(contrib)[j];
                VECTOR(contrib)[j] = 0.0;
            }
        }
    }

    igraph_vit_destroy(&vit);
    igraph_vector_int_destroy(&jneis_out);
    igraph_vector_int_destroy(&jneis_in);
    igraph_vector_int_destroy(&ineis_out);
    igraph_vector_int_destroy(&ineis_in);
    igraph_vector_destroy(&degree);
    igraph_vector_destroy(&contrib);
    IGRAPH_FINALLY_CLEAN(7);

    return IGRAPH_SUCCESS;
}

Coverage Report

Created: 2025-10-10 06:07

Line	Count	Source
1		/*
2		igraph library.
3		Copyright (C) 2005-2021 The igraph development team
4
5		This program is free software; you can redistribute it and/or modify
6		it under the terms of the GNU General Public License as published by
7		the Free Software Foundation; either version 2 of the License, or
8		(at your option) any later version.
9
10		This program is distributed in the hope that it will be useful,
11		but WITHOUT ANY WARRANTY; without even the implied warranty of
12		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13		GNU General Public License for more details.
14
15		You should have received a copy of the GNU General Public License
16		along with this program; if not, write to the Free Software
17		Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18		02110-1301 USA
19
20		*/
21
22		#include "igraph_centrality.h"
23
24		#include "igraph_interface.h"
25		#include "igraph_structural.h"
26
27		/**
28		* \function igraph_constraint
29		* \brief Burt's constraint scores.
30		*
31		* </para><para>
32		* This function calculates Burt's constraint scores for the given
33		* vertices, also known as structural holes.
34		*
35		* </para><para>
36		* Burt's constraint is higher if ego has less, or mutually stronger
37		* related (i.e. more redundant) contacts. Burt's measure of
38		* constraint, C[i], of vertex i's ego network V[i], is defined for
39		* directed and valued graphs,
40		* <blockquote><para>
41		* C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in
42		* V[], j != i)
43		* </para></blockquote>
44		* for a graph of order (i.e. number of vertices) N, where proportional
45		* tie strengths are defined as
46		* <blockquote><para>
47		* p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i),
48		* </para></blockquote>
49		* a[i,j] are elements of A and
50		* the latter being the graph adjacency matrix. For isolated vertices,
51		* constraint is undefined.
52		*
53		* </para><para>
54		* Burt, R.S. (2004). Structural holes and good ideas. American
55		* Journal of Sociology 110, 349-399.
56		*
57		* </para><para>
58		* The first R version of this function was contributed by Jeroen
59		* Bruggeman.
60		* \param graph A graph object.
61		* \param res Pointer to an initialized vector, the result will be
62		* stored here. The vector will be resized to have the
63		* appropriate size for holding the result.
64		* \param vids Vertex selector containing the vertices for which the
65		* constraint should be calculated.
66		* \param weights Vector giving the weights of the edges. If it is
67		* \c NULL then each edge is supposed to have the same weight.
68		* \return Error code.
69		*
70		* Time complexity: O(\|V\|+E\|+n*d^2), n is the number of vertices for
71		* which the constraint is calculated and d is the average degree, \|V\|
72		* is the number of vertices, \|E\| the number of edges in the
73		* graph. If the weights argument is \c NULL then the time complexity
74		* is O(\|V\|+n*d^2).
75		*/
76		igraph_error_t igraph_constraint(const igraph_t graph, igraph_vector_t res,
77	1.26k	igraph_vs_t vids, const igraph_vector_t *weights) {
78
79	1.26k	igraph_int_t no_of_nodes = igraph_vcount(graph);
80	1.26k	igraph_int_t no_of_edges = igraph_ecount(graph);
81	1.26k	igraph_vit_t vit;
82	1.26k	igraph_int_t nodes_to_calc;
83	1.26k	igraph_int_t a, b, c, i, j, q, vsize, vsize2;
84	1.26k	igraph_int_t edge, edge2;
85
86	1.26k	igraph_vector_t contrib;
87	1.26k	igraph_vector_t degree;
88	1.26k	igraph_vector_int_t ineis_in, ineis_out, jneis_in, jneis_out;
89
90	1.26k	if (weights != 0 && igraph_vector_size(weights) != no_of_edges) {
91	0	IGRAPH_ERROR("Invalid length of weight vector", IGRAPH_EINVAL);
92	0	}
93
94	1.26k	IGRAPH_VECTOR_INIT_FINALLY(&contrib, no_of_nodes);
95	1.26k	IGRAPH_VECTOR_INIT_FINALLY(&degree, no_of_nodes);
96	1.26k	IGRAPH_VECTOR_INT_INIT_FINALLY(&ineis_in, 0);
97	1.26k	IGRAPH_VECTOR_INT_INIT_FINALLY(&ineis_out, 0);
98	1.26k	IGRAPH_VECTOR_INT_INIT_FINALLY(&jneis_in, 0);
99	1.26k	IGRAPH_VECTOR_INT_INIT_FINALLY(&jneis_out, 0);
100
101	1.26k	IGRAPH_CHECK(igraph_vit_create(graph, vids, &vit));
102	1.26k	IGRAPH_FINALLY(igraph_vit_destroy, &vit);
103	1.26k	nodes_to_calc = IGRAPH_VIT_SIZE(vit);
104
105	1.26k	IGRAPH_CHECK(igraph_strength(graph, &degree, igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS, weights));
106
107	1.26k	IGRAPH_CHECK(igraph_vector_resize(res, nodes_to_calc));
108	1.26k	igraph_vector_null(res);
109
110	56.7k	for (a = 0; a < nodes_to_calc; a++, IGRAPH_VIT_NEXT(vit)) {
111	55.4k	i = IGRAPH_VIT_GET(vit);
112
113		/* get neighbors of i */
114	55.4k	IGRAPH_CHECK(igraph_incident(graph, &ineis_in, i, IGRAPH_IN, IGRAPH_LOOPS));
115	55.4k	IGRAPH_CHECK(igraph_incident(graph, &ineis_out, i, IGRAPH_OUT, IGRAPH_LOOPS));
116
117		/* NaN for isolates */
118	55.4k	if (igraph_vector_int_size(&ineis_in) == 0 &&
119	42.4k	igraph_vector_int_size(&ineis_out) == 0) {
120	38.0k	VECTOR(*res)[a] = IGRAPH_NAN;
121	38.0k	}
122
123		/* zero their contribution */
124	55.4k	vsize = igraph_vector_int_size(&ineis_in);
125	95.7k	for (b = 0; b < vsize; b++) {
126	40.2k	edge = VECTOR(ineis_in)[b];
127	40.2k	j = IGRAPH_OTHER(graph, edge, i);
128	40.2k	VECTOR(contrib)[j] = 0.0;
129	40.2k	}
130	55.4k	vsize = igraph_vector_int_size(&ineis_out);
131	95.7k	for (b = 0; b < vsize; b++) {
132	40.2k	edge = VECTOR(ineis_out)[b];
133	40.2k	j = IGRAPH_OTHER(graph, edge, i);
134	40.2k	VECTOR(contrib)[j] = 0.0;
135	40.2k	}
136
137		/* add the direct contributions, in-neighbors and out-neighbors */
138	55.4k	vsize = igraph_vector_int_size(&ineis_in);
139	95.7k	for (b = 0; b < vsize; b++) {
140	40.2k	edge = VECTOR(ineis_in)[b];
141	40.2k	j = IGRAPH_OTHER(graph, edge, i);
142	40.2k	if (i != j) { /* excluding loops */
143	36.5k	if (weights) {
144	0	VECTOR(contrib)[j] +=
145	0	VECTOR(*weights)[edge] / VECTOR(degree)[i];
146	36.5k	} else {
147	36.5k	VECTOR(contrib)[j] += 1.0 / VECTOR(degree)[i];
148	36.5k	}
149	36.5k	}
150	40.2k	}
151	55.4k	if (igraph_is_directed(graph)) {
152	55.4k	vsize = igraph_vector_int_size(&ineis_out);
153	95.7k	for (b = 0; b < vsize; b++) {
154	40.2k	edge = VECTOR(ineis_out)[b];
155	40.2k	j = IGRAPH_OTHER(graph, edge, i);
156	40.2k	if (i != j) {
157	36.5k	if (weights) {
158	0	VECTOR(contrib)[j] +=
159	0	VECTOR(*weights)[edge] / VECTOR(degree)[i];
160	36.5k	} else {
161	36.5k	VECTOR(contrib)[j] += 1.0 / VECTOR(degree)[i];
162	36.5k	}
163	36.5k	}
164	40.2k	}
165	55.4k	}
166
167		/* add the indirect contributions, in-in, in-out, out-in, out-out */
168	55.4k	vsize = igraph_vector_int_size(&ineis_in);
169	95.7k	for (b = 0; b < vsize; b++) {
170	40.2k	edge = VECTOR(ineis_in)[b];
171	40.2k	j = IGRAPH_OTHER(graph, edge, i);
172	40.2k	if (i == j) {
173	3.76k	continue;
174	3.76k	}
175	36.5k	IGRAPH_CHECK(igraph_incident(graph, &jneis_in, j, IGRAPH_IN, IGRAPH_LOOPS));
176	36.5k	IGRAPH_CHECK(igraph_incident(graph, &jneis_out, j, IGRAPH_OUT, IGRAPH_LOOPS));
177	36.5k	vsize2 = igraph_vector_int_size(&jneis_in);
178	222k	for (c = 0; c < vsize2; c++) {
179	186k	edge2 = VECTOR(jneis_in)[c];
180	186k	q = IGRAPH_OTHER(graph, edge2, j);
181	186k	if (j != q) {
182	166k	if (weights) {
183	0	VECTOR(contrib)[q] +=
184	0	VECTOR(weights)[edge]
185	0	VECTOR(*weights)[edge2] /
186	0	VECTOR(degree)[i] / VECTOR(degree)[j];
187	166k	} else {
188	166k	VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
189	166k	}
190	166k	}
191	186k	}
192	36.5k	if (igraph_is_directed(graph)) {
193	36.5k	vsize2 = igraph_vector_int_size(&jneis_out);
194	1.27M	for (c = 0; c < vsize2; c++) {
195	1.23M	edge2 = VECTOR(jneis_out)[c];
196	1.23M	q = IGRAPH_OTHER(graph, edge2, j);
197	1.23M	if (j != q) {
198	1.21M	if (weights) {
199	0	VECTOR(contrib)[q] +=
200	0	VECTOR(weights)[edge]
201	0	VECTOR(*weights)[edge2] /
202	0	VECTOR(degree)[i] / VECTOR(degree)[j];
203	1.21M	} else {
204	1.21M	VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
205	1.21M	}
206	1.21M	}
207	1.23M	}
208	36.5k	}
209	36.5k	}
210	55.4k	if (igraph_is_directed(graph)) {
211	55.4k	vsize = igraph_vector_int_size(&ineis_out);
212	95.7k	for (b = 0; b < vsize; b++) {
213	40.2k	edge = VECTOR(ineis_out)[b];
214	40.2k	j = IGRAPH_OTHER(graph, edge, i);
215	40.2k	if (i == j) {
216	3.76k	continue;
217	3.76k	}
218	36.5k	IGRAPH_CHECK(igraph_incident(graph, &jneis_in, j, IGRAPH_IN, IGRAPH_LOOPS));
219	36.5k	IGRAPH_CHECK(igraph_incident(graph, &jneis_out, j, IGRAPH_OUT, IGRAPH_LOOPS));
220	36.5k	vsize2 = igraph_vector_int_size(&jneis_in);
221	1.27M	for (c = 0; c < vsize2; c++) {
222	1.23M	edge2 = VECTOR(jneis_in)[c];
223	1.23M	q = IGRAPH_OTHER(graph, edge2, j);
224	1.23M	if (j != q) {
225	1.21M	if (weights) {
226	0	VECTOR(contrib)[q] +=
227	0	VECTOR(weights)[edge]
228	0	VECTOR(*weights)[edge2] /
229	0	VECTOR(degree)[i] / VECTOR(degree)[j];
230	1.21M	} else {
231	1.21M	VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
232	1.21M	}
233	1.21M	}
234	1.23M	}
235	36.5k	vsize2 = igraph_vector_int_size(&jneis_out);
236	221k	for (c = 0; c < vsize2; c++) {
237	185k	edge2 = VECTOR(jneis_out)[c];
238	185k	q = IGRAPH_OTHER(graph, edge2, j);
239	185k	if (j != q) {
240	166k	if (weights) {
241	0	VECTOR(contrib)[q] +=
242	0	VECTOR(weights)[edge]
243	0	VECTOR(*weights)[edge2] /
244	0	VECTOR(degree)[i] / VECTOR(degree)[j];
245	166k	} else {
246	166k	VECTOR(contrib)[q] += 1 / VECTOR(degree)[i] / VECTOR(degree)[j];
247	166k	}
248	166k	}
249	185k	}
250	36.5k	}
251	55.4k	}
252
253		/* squared sum of the contributions */
254	55.4k	vsize = igraph_vector_int_size(&ineis_in);
255	95.7k	for (b = 0; b < vsize; b++) {
256	40.2k	edge = VECTOR(ineis_in)[b];
257	40.2k	j = IGRAPH_OTHER(graph, edge, i);
258	40.2k	if (i == j) {
259	3.76k	continue;
260	3.76k	}
261	36.5k	VECTOR(res)[a] += VECTOR(contrib)[j] VECTOR(contrib)[j];
262	36.5k	VECTOR(contrib)[j] = 0.0;
263	36.5k	}
264	55.4k	if (igraph_is_directed(graph)) {
265	55.4k	vsize = igraph_vector_int_size(&ineis_out);
266	95.7k	for (b = 0; b < vsize; b++) {
267	40.2k	edge = VECTOR(ineis_out)[b];
268	40.2k	j = IGRAPH_OTHER(graph, edge, i);
269	40.2k	if (i == j) {
270	3.76k	continue;
271	3.76k	}
272	36.5k	VECTOR(res)[a] += VECTOR(contrib)[j] VECTOR(contrib)[j];
273	36.5k	VECTOR(contrib)[j] = 0.0;
274	36.5k	}
275	55.4k	}
276	55.4k	}
277
278	1.26k	igraph_vit_destroy(&vit);
279	1.26k	igraph_vector_int_destroy(&jneis_out);
280	1.26k	igraph_vector_int_destroy(&jneis_in);
281	1.26k	igraph_vector_int_destroy(&ineis_out);
282	1.26k	igraph_vector_int_destroy(&ineis_in);
283	1.26k	igraph_vector_destroy(&degree);
284	1.26k	igraph_vector_destroy(&contrib);
285	1.26k	IGRAPH_FINALLY_CLEAN(7);
286
287	1.26k	return IGRAPH_SUCCESS;
288	1.26k	}