Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for computing measures of structural holes."""
3import networkx as nx
5__all__ = ["constraint", "local_constraint", "effective_size"]
8@nx._dispatchable(edge_attrs="weight")
9def mutual_weight(G, u, v, weight=None):
10 """Returns the sum of the weights of the edge from `u` to `v` and
11 the edge from `v` to `u` in `G`.
13 `weight` is the edge data key that represents the edge weight. If
14 the specified key is `None` or is not in the edge data for an edge,
15 that edge is assumed to have weight 1.
17 Pre-conditions: `u` and `v` must both be in `G`.
19 """
20 try:
21 a_uv = G[u][v].get(weight, 1)
22 except KeyError:
23 a_uv = 0
24 try:
25 a_vu = G[v][u].get(weight, 1)
26 except KeyError:
27 a_vu = 0
28 return a_uv + a_vu
31@nx._dispatchable(edge_attrs="weight")
32def normalized_mutual_weight(G, u, v, norm=sum, weight=None):
33 """Returns normalized mutual weight of the edges from `u` to `v`
34 with respect to the mutual weights of the neighbors of `u` in `G`.
36 `norm` specifies how the normalization factor is computed. It must
37 be a function that takes a single argument and returns a number.
38 The argument will be an iterable of mutual weights
39 of pairs ``(u, w)``, where ``w`` ranges over each (in- and
40 out-)neighbor of ``u``. Commons values for `normalization` are
41 ``sum`` and ``max``.
43 `weight` can be ``None`` or a string, if None, all edge weights
44 are considered equal. Otherwise holds the name of the edge
45 attribute used as weight.
47 """
48 scale = norm(mutual_weight(G, u, w, weight) for w in set(nx.all_neighbors(G, u)))
49 return 0 if scale == 0 else mutual_weight(G, u, v, weight) / scale
52@nx._dispatchable(edge_attrs="weight")
53def effective_size(G, nodes=None, weight=None):
54 r"""Returns the effective size of all nodes in the graph ``G``.
56 The *effective size* of a node's ego network is based on the concept
57 of redundancy. A person's ego network has redundancy to the extent
58 that her contacts are connected to each other as well. The
59 nonredundant part of a person's relationships is the effective
60 size of her ego network [1]_. Formally, the effective size of a
61 node $u$, denoted $e(u)$, is defined by
63 .. math::
65 e(u) = \sum_{v \in N(u) \setminus \{u\}}
66 \left(1 - \sum_{w \in N(v)} p_{uw} m_{vw}\right)
68 where $N(u)$ is the set of neighbors of $u$ and $p_{uw}$ is the
69 normalized mutual weight of the (directed or undirected) edges
70 joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. And $m_{vw}$
71 is the mutual weight of $v$ and $w$ divided by $v$ highest mutual
72 weight with any of its neighbors. The *mutual weight* of $u$ and $v$
73 is the sum of the weights of edges joining them (edge weights are
74 assumed to be one if the graph is unweighted).
76 For the case of unweighted and undirected graphs, Borgatti proposed
77 a simplified formula to compute effective size [2]_
79 .. math::
81 e(u) = n - \frac{2t}{n}
83 where `t` is the number of ties in the ego network (not including
84 ties to ego) and `n` is the number of nodes (excluding ego).
86 Parameters
87 ----------
88 G : NetworkX graph
89 The graph containing ``v``. Directed graphs are treated like
90 undirected graphs when computing neighbors of ``v``.
92 nodes : container, optional
93 Container of nodes in the graph ``G`` to compute the effective size.
94 If None, the effective size of every node is computed.
96 weight : None or string, optional
97 If None, all edge weights are considered equal.
98 Otherwise holds the name of the edge attribute used as weight.
100 Returns
101 -------
102 dict
103 Dictionary with nodes as keys and the effective size of the node as values.
105 Notes
106 -----
107 Isolated nodes, including nodes which only have self-loop edges, do not
108 have a well-defined effective size::
110 >>> G = nx.path_graph(3)
111 >>> G.add_edge(4, 4)
112 >>> nx.effective_size(G)
113 {0: 1.0, 1: 2.0, 2: 1.0, 4: nan}
115 Burt also defined the related concept of *efficiency* of a node's ego
116 network, which is its effective size divided by the degree of that
117 node [1]_. So you can easily compute efficiency:
119 >>> G = nx.DiGraph()
120 >>> G.add_edges_from([(0, 1), (0, 2), (1, 0), (2, 1)])
121 >>> esize = nx.effective_size(G)
122 >>> efficiency = {n: v / G.degree(n) for n, v in esize.items()}
124 See also
125 --------
126 constraint
128 References
129 ----------
130 .. [1] Burt, Ronald S.
131 *Structural Holes: The Social Structure of Competition.*
132 Cambridge: Harvard University Press, 1995.
134 .. [2] Borgatti, S.
135 "Structural Holes: Unpacking Burt's Redundancy Measures"
136 CONNECTIONS 20(1):35-38.
137 http://www.analytictech.com/connections/v20(1)/holes.htm
139 """
141 def redundancy(G, u, v, weight=None):
142 nmw = normalized_mutual_weight
143 r = sum(
144 nmw(G, u, w, weight=weight) * nmw(G, v, w, norm=max, weight=weight)
145 for w in set(nx.all_neighbors(G, u))
146 )
147 return 1 - r
149 # Check if scipy is available
150 try:
151 # Needed for errstate
152 import numpy as np
154 # make sure nx.adjacency_matrix will not raise
155 import scipy as sp
157 has_scipy = True
158 except:
159 has_scipy = False
161 if nodes is None and has_scipy:
162 # In order to compute constraint of all nodes,
163 # algorithms based on sparse matrices can be much faster
165 # Obtain the adjacency matrix
166 P = nx.adjacency_matrix(G, weight=weight)
168 # Calculate mutual weights
169 mutual_weights1 = P + P.T
170 mutual_weights2 = mutual_weights1.copy()
172 with np.errstate(divide="ignore"):
173 # Mutual_weights1 = Normalize mutual weights by row sums
174 mutual_weights1 /= mutual_weights1.sum(axis=1)[:, np.newaxis]
176 # Mutual_weights2 = Normalize mutual weights by row max
177 mutual_weights2 /= mutual_weights2.max(axis=1).toarray()
179 # Calculate effective sizes
180 r = 1 - (mutual_weights1 @ mutual_weights2.T).toarray()
181 effective_size = ((mutual_weights1 > 0) * r).sum(axis=1)
183 # Special treatment: isolated nodes (ignoring selfloops) marked with "nan"
184 sum_mutual_weights = mutual_weights1.sum(axis=1) - mutual_weights1.diagonal()
185 isolated_nodes = sum_mutual_weights == 0
186 effective_size[isolated_nodes] = float("nan")
187 # Use tolist() to automatically convert numpy scalars -> Python scalars
188 return dict(zip(G, effective_size.tolist()))
190 # Results for only requested nodes
191 effective_size = {}
192 if nodes is None:
193 nodes = G
194 # Use Borgatti's simplified formula for unweighted and undirected graphs
195 if not G.is_directed() and weight is None:
196 for v in nodes:
197 # Effective size is not defined for isolated nodes, including nodes
198 # with only self-edges
199 if all(u == v for u in G[v]):
200 effective_size[v] = float("nan")
201 continue
202 E = nx.ego_graph(G, v, center=False, undirected=True)
203 effective_size[v] = len(E) - (2 * E.size()) / len(E)
204 else:
205 for v in nodes:
206 # Effective size is not defined for isolated nodes, including nodes
207 # with only self-edges
208 if all(u == v for u in G[v]):
209 effective_size[v] = float("nan")
210 continue
211 effective_size[v] = sum(
212 redundancy(G, v, u, weight) for u in set(nx.all_neighbors(G, v))
213 )
214 return effective_size
217@nx._dispatchable(edge_attrs="weight")
218def constraint(G, nodes=None, weight=None):
219 r"""Returns the constraint on all nodes in the graph ``G``.
221 The *constraint* is a measure of the extent to which a node *v* is
222 invested in those nodes that are themselves invested in the
223 neighbors of *v*. Formally, the *constraint on v*, denoted `c(v)`,
224 is defined by
226 .. math::
228 c(v) = \sum_{w \in N(v) \setminus \{v\}} \ell(v, w)
230 where $N(v)$ is the subset of the neighbors of `v` that are either
231 predecessors or successors of `v` and $\ell(v, w)$ is the local
232 constraint on `v` with respect to `w` [1]_. For the definition of local
233 constraint, see :func:`local_constraint`.
235 Parameters
236 ----------
237 G : NetworkX graph
238 The graph containing ``v``. This can be either directed or undirected.
240 nodes : container, optional
241 Container of nodes in the graph ``G`` to compute the constraint. If
242 None, the constraint of every node is computed.
244 weight : None or string, optional
245 If None, all edge weights are considered equal.
246 Otherwise holds the name of the edge attribute used as weight.
248 Returns
249 -------
250 dict
251 Dictionary with nodes as keys and the constraint on the node as values.
253 See also
254 --------
255 local_constraint
257 References
258 ----------
259 .. [1] Burt, Ronald S.
260 "Structural holes and good ideas".
261 American Journal of Sociology (110): 349–399.
263 """
265 # Check if scipy is available
266 try:
267 # Needed for errstate
268 import numpy as np
270 # make sure nx.adjacency_matrix will not raise
271 import scipy as sp
273 has_scipy = True
274 except:
275 has_scipy = False
277 if nodes is None and has_scipy:
278 # In order to compute constraint of all nodes,
279 # algorithms based on sparse matrices can be much faster
281 # Obtain the adjacency matrix
282 P = nx.adjacency_matrix(G, weight=weight)
284 # Calculate mutual weights
285 mutual_weights = P + P.T
287 # Normalize mutual weights by row sums
288 sum_mutual_weights = mutual_weights.sum(axis=1)
289 with np.errstate(divide="ignore"):
290 mutual_weights /= sum_mutual_weights[:, np.newaxis]
292 # Calculate local constraints and constraints
293 local_constraints = (mutual_weights + mutual_weights @ mutual_weights) ** 2
294 constraints = ((mutual_weights > 0) * local_constraints).sum(axis=1)
296 # Special treatment: isolated nodes marked with "nan"
297 isolated_nodes = sum_mutual_weights - 2 * mutual_weights.diagonal() == 0
298 constraints[isolated_nodes] = float("nan")
299 # Use tolist() to automatically convert numpy scalars -> Python scalars
300 return dict(zip(G, constraints.tolist()))
302 # Result for only requested nodes
303 constraint = {}
304 if nodes is None:
305 nodes = G
306 for v in nodes:
307 # Constraint is not defined for isolated nodes
308 if len(G[v]) == 0:
309 constraint[v] = float("nan")
310 continue
311 constraint[v] = sum(
312 local_constraint(G, v, n, weight) for n in set(nx.all_neighbors(G, v))
313 )
314 return constraint
317@nx._dispatchable(edge_attrs="weight")
318def local_constraint(G, u, v, weight=None):
319 r"""Returns the local constraint on the node ``u`` with respect to
320 the node ``v`` in the graph ``G``.
322 Formally, the *local constraint on u with respect to v*, denoted
323 $\ell(u, v)$, is defined by
325 .. math::
327 \ell(u, v) = \left(p_{uv} + \sum_{w \in N(v)} p_{uw} p_{wv}\right)^2,
329 where $N(v)$ is the set of neighbors of $v$ and $p_{uv}$ is the
330 normalized mutual weight of the (directed or undirected) edges
331 joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. The *mutual
332 weight* of $u$ and $v$ is the sum of the weights of edges joining
333 them (edge weights are assumed to be one if the graph is
334 unweighted).
336 Parameters
337 ----------
338 G : NetworkX graph
339 The graph containing ``u`` and ``v``. This can be either
340 directed or undirected.
342 u : node
343 A node in the graph ``G``.
345 v : node
346 A node in the graph ``G``.
348 weight : None or string, optional
349 If None, all edge weights are considered equal.
350 Otherwise holds the name of the edge attribute used as weight.
352 Returns
353 -------
354 float
355 The constraint of the node ``v`` in the graph ``G``.
357 See also
358 --------
359 constraint
361 References
362 ----------
363 .. [1] Burt, Ronald S.
364 "Structural holes and good ideas".
365 American Journal of Sociology (110): 349–399.
367 """
368 nmw = normalized_mutual_weight
369 direct = nmw(G, u, v, weight=weight)
370 indirect = sum(
371 nmw(G, u, w, weight=weight) * nmw(G, w, v, weight=weight)
372 for w in set(nx.all_neighbors(G, u))
373 )
374 return (direct + indirect) ** 2