### comparison env/lib/python3.9/site-packages/networkx/algorithms/structuralholes.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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
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
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
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