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