Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/structuralholes.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- encoding: utf-8 -*-
2 #
3 # Copyright 2008-2019 NetworkX developers.
4 # Aric Hagberg <hagberg@lanl.gov>
5 # Dan Schult <dschult@colgate.edu>
6 # Pieter Swart <swart@lanl.gov>
7 # All rights reserved.
8 # BSD license.
9 """Functions for computing measures of structural holes."""
10
11 import networkx as nx
12
13 __all__ = ['constraint', 'local_constraint', 'effective_size']
14
15
16 def mutual_weight(G, u, v, weight=None):
17 """Returns the sum of the weights of the edge from `u` to `v` and
18 the edge from `v` to `u` in `G`.
19
20 `weight` is the edge data key that represents the edge weight. If
21 the specified key is `None` or is not in the edge data for an edge,
22 that edge is assumed to have weight 1.
23
24 Pre-conditions: `u` and `v` must both be in `G`.
25
26 """
27 try:
28 a_uv = G[u][v].get(weight, 1)
29 except KeyError:
30 a_uv = 0
31 try:
32 a_vu = G[v][u].get(weight, 1)
33 except KeyError:
34 a_vu = 0
35 return a_uv + a_vu
36
37
38 def normalized_mutual_weight(G, u, v, norm=sum, weight=None):
39 """Returns normalized mutual weight of the edges from `u` to `v`
40 with respect to the mutual weights of the neighbors of `u` in `G`.
41
42 `norm` specifies how the normalization factor is computed. It must
43 be a function that takes a single argument and returns a number.
44 The argument will be an iterable of mutual weights
45 of pairs ``(u, w)``, where ``w`` ranges over each (in- and
46 out-)neighbor of ``u``. Commons values for `normalization` are
47 ``sum`` and ``max``.
48
49 `weight` can be ``None`` or a string, if None, all edge weights
50 are considered equal. Otherwise holds the name of the edge
51 attribute used as weight.
52
53 """
54 scale = norm(mutual_weight(G, u, w, weight)
55 for w in set(nx.all_neighbors(G, u)))
56 return 0 if scale == 0 else mutual_weight(G, u, v, weight) / scale
57
58
59 def effective_size(G, nodes=None, weight=None):
60 r"""Returns the effective size of all nodes in the graph ``G``.
61
62 The *effective size* of a node's ego network is based on the concept
63 of redundancy. A person's ego network has redundancy to the extent
64 that her contacts are connected to each other as well. The
65 nonredundant part of a person's relationships it's the effective
66 size of her ego network [1]_. Formally, the effective size of a
67 node $u$, denoted $e(u)$, is defined by
68
69 .. math::
70
71 e(u) = \sum_{v \in N(u) \setminus \{u\}}
72 \left(1 - \sum_{w \in N(v)} p_{uw} m_{vw}\right)
73
74 where $N(u)$ is the set of neighbors of $u$ and $p_{uw}$ is the
75 normalized mutual weight of the (directed or undirected) edges
76 joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. And $m_{vw}$
77 is the mutual weight of $v$ and $w$ divided by $v$ highest mutual
78 weight with any of its neighbors. The *mutual weight* of $u$ and $v$
79 is the sum of the weights of edges joining them (edge weights are
80 assumed to be one if the graph is unweighted).
81
82 For the case of unweighted and undirected graphs, Borgatti proposed
83 a simplified formula to compute effective size [2]_
84
85 .. math::
86
87 e(u) = n - \frac{2t}{n}
88
89 where `t` is the number of ties in the ego network (not including
90 ties to ego) and `n` is the number of nodes (excluding ego).
91
92 Parameters
93 ----------
94 G : NetworkX graph
95 The graph containing ``v``. Directed graphs are treated like
96 undirected graphs when computing neighbors of ``v``.
97
98 nodes : container, optional
99 Container of nodes in the graph ``G`` to compute the effective size.
100 If None, the effective size of every node is computed.
101
102 weight : None or string, optional
103 If None, all edge weights are considered equal.
104 Otherwise holds the name of the edge attribute used as weight.
105
106 Returns
107 -------
108 dict
109 Dictionary with nodes as keys and the constraint on the node as values.
110
111 Notes
112 -----
113 Burt also defined the related concept of *efficiency* of a node's ego
114 network, which is its effective size divided by the degree of that
115 node [1]_. So you can easily compute efficiency:
116
117 >>> G = nx.DiGraph()
118 >>> G.add_edges_from([(0, 1), (0, 2), (1, 0), (2, 1)])
119 >>> esize = nx.effective_size(G)
120 >>> efficiency = {n: v / G.degree(n) for n, v in esize.items()}
121
122 See also
123 --------
124 constraint
125
126 References
127 ----------
128 .. [1] Burt, Ronald S.
129 *Structural Holes: The Social Structure of Competition.*
130 Cambridge: Harvard University Press, 1995.
131
132 .. [2] Borgatti, S.
133 "Structural Holes: Unpacking Burt's Redundancy Measures"
134 CONNECTIONS 20(1):35-38.
135 http://www.analytictech.com/connections/v20(1)/holes.htm
136
137 """
138 def redundancy(G, u, v, weight=None):
139 nmw = normalized_mutual_weight
140 r = sum(nmw(G, u, w, weight=weight) * nmw(G, v, w, norm=max, weight=weight)
141 for w in set(nx.all_neighbors(G, u)))
142 return 1 - r
143 effective_size = {}
144 if nodes is None:
145 nodes = G
146 # Use Borgatti's simplified formula for unweighted and undirected graphs
147 if not G.is_directed() and weight is None:
148 for v in nodes:
149 # Effective size is not defined for isolated nodes
150 if len(G[v]) == 0:
151 effective_size[v] = float('nan')
152 continue
153 E = nx.ego_graph(G, v, center=False, undirected=True)
154 effective_size[v] = len(E) - (2 * E.size()) / len(E)
155 else:
156 for v in nodes:
157 # Effective size is not defined for isolated nodes
158 if len(G[v]) == 0:
159 effective_size[v] = float('nan')
160 continue
161 effective_size[v] = sum(redundancy(G, v, u, weight)
162 for u in set(nx.all_neighbors(G, v)))
163 return effective_size
164
165
166 def constraint(G, nodes=None, weight=None):
167 r"""Returns the constraint on all nodes in the graph ``G``.
168
169 The *constraint* is a measure of the extent to which a node *v* is
170 invested in those nodes that are themselves invested in the
171 neighbors of *v*. Formally, the *constraint on v*, denoted `c(v)`,
172 is defined by
173
174 .. math::
175
176 c(v) = \sum_{w \in N(v) \setminus \{v\}} \ell(v, w)
177
178 where `N(v)` is the subset of the neighbors of `v` that are either
179 predecessors or successors of `v` and `\ell(v, w)` is the local
180 constraint on `v` with respect to `w` [1]_. For the definition of local
181 constraint, see :func:`local_constraint`.
182
183 Parameters
184 ----------
185 G : NetworkX graph
186 The graph containing ``v``. This can be either directed or undirected.
187
188 nodes : container, optional
189 Container of nodes in the graph ``G`` to compute the constraint. If
190 None, the constraint of every node is computed.
191
192 weight : None or string, optional
193 If None, all edge weights are considered equal.
194 Otherwise holds the name of the edge attribute used as weight.
195
196 Returns
197 -------
198 dict
199 Dictionary with nodes as keys and the constraint on the node as values.
200
201 See also
202 --------
203 local_constraint
204
205 References
206 ----------
207 .. [1] Burt, Ronald S.
208 "Structural holes and good ideas".
209 American Journal of Sociology (110): 349–399.
210
211 """
212 if nodes is None:
213 nodes = G
214 constraint = {}
215 for v in nodes:
216 # Constraint is not defined for isolated nodes
217 if len(G[v]) == 0:
218 constraint[v] = float('nan')
219 continue
220 constraint[v] = sum(local_constraint(G, v, n, weight)
221 for n in set(nx.all_neighbors(G, v)))
222 return constraint
223
224
225 def local_constraint(G, u, v, weight=None):
226 r"""Returns the local constraint on the node ``u`` with respect to
227 the node ``v`` in the graph ``G``.
228
229 Formally, the *local constraint on u with respect to v*, denoted
230 $\ell(v)$, is defined by
231
232 .. math::
233
234 \ell(u, v) = \left(p_{uv} + \sum_{w \in N(v)} p_{uw} p{wv}\right)^2,
235
236 where $N(v)$ is the set of neighbors of $v$ and $p_{uv}$ is the
237 normalized mutual weight of the (directed or undirected) edges
238 joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. The *mutual
239 weight* of $u$ and $v$ is the sum of the weights of edges joining
240 them (edge weights are assumed to be one if the graph is
241 unweighted).
242
243 Parameters
244 ----------
245 G : NetworkX graph
246 The graph containing ``u`` and ``v``. This can be either
247 directed or undirected.
248
249 u : node
250 A node in the graph ``G``.
251
252 v : node
253 A node in the graph ``G``.
254
255 weight : None or string, optional
256 If None, all edge weights are considered equal.
257 Otherwise holds the name of the edge attribute used as weight.
258
259 Returns
260 -------
261 float
262 The constraint of the node ``v`` in the graph ``G``.
263
264 See also
265 --------
266 constraint
267
268 References
269 ----------
270 .. [1] Burt, Ronald S.
271 "Structural holes and good ideas".
272 American Journal of Sociology (110): 349–399.
273
274 """
275 nmw = normalized_mutual_weight
276 direct = nmw(G, u, v, weight=weight)
277 indirect = sum(nmw(G, u, w, weight=weight) * nmw(G, w, v, weight=weight)
278 for w in set(nx.all_neighbors(G, u)))
279 return (direct + indirect) ** 2