Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/structuralholes.py: 21%
56 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions for computing measures of structural holes."""
3import networkx as nx
5__all__ = ["constraint", "local_constraint", "effective_size"]
8@nx._dispatch(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._dispatch(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._dispatch(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 Burt also defined the related concept of *efficiency* of a node's ego
108 network, which is its effective size divided by the degree of that
109 node [1]_. So you can easily compute efficiency:
111 >>> G = nx.DiGraph()
112 >>> G.add_edges_from([(0, 1), (0, 2), (1, 0), (2, 1)])
113 >>> esize = nx.effective_size(G)
114 >>> efficiency = {n: v / G.degree(n) for n, v in esize.items()}
116 See also
117 --------
118 constraint
120 References
121 ----------
122 .. [1] Burt, Ronald S.
123 *Structural Holes: The Social Structure of Competition.*
124 Cambridge: Harvard University Press, 1995.
126 .. [2] Borgatti, S.
127 "Structural Holes: Unpacking Burt's Redundancy Measures"
128 CONNECTIONS 20(1):35-38.
129 http://www.analytictech.com/connections/v20(1)/holes.htm
131 """
133 def redundancy(G, u, v, weight=None):
134 nmw = normalized_mutual_weight
135 r = sum(
136 nmw(G, u, w, weight=weight) * nmw(G, v, w, norm=max, weight=weight)
137 for w in set(nx.all_neighbors(G, u))
138 )
139 return 1 - r
141 effective_size = {}
142 if nodes is None:
143 nodes = G
144 # Use Borgatti's simplified formula for unweighted and undirected graphs
145 if not G.is_directed() and weight is None:
146 for v in nodes:
147 # Effective size is not defined for isolated nodes
148 if len(G[v]) == 0:
149 effective_size[v] = float("nan")
150 continue
151 E = nx.ego_graph(G, v, center=False, undirected=True)
152 effective_size[v] = len(E) - (2 * E.size()) / len(E)
153 else:
154 for v in nodes:
155 # Effective size is not defined for isolated nodes
156 if len(G[v]) == 0:
157 effective_size[v] = float("nan")
158 continue
159 effective_size[v] = sum(
160 redundancy(G, v, u, weight) for u in set(nx.all_neighbors(G, v))
161 )
162 return effective_size
165@nx._dispatch(edge_attrs="weight")
166def constraint(G, nodes=None, weight=None):
167 r"""Returns the constraint on all nodes in the graph ``G``.
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
174 .. math::
176 c(v) = \sum_{w \in N(v) \setminus \{v\}} \ell(v, w)
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`.
183 Parameters
184 ----------
185 G : NetworkX graph
186 The graph containing ``v``. This can be either directed or undirected.
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.
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.
196 Returns
197 -------
198 dict
199 Dictionary with nodes as keys and the constraint on the node as values.
201 See also
202 --------
203 local_constraint
205 References
206 ----------
207 .. [1] Burt, Ronald S.
208 "Structural holes and good ideas".
209 American Journal of Sociology (110): 349–399.
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(
221 local_constraint(G, v, n, weight) for n in set(nx.all_neighbors(G, v))
222 )
223 return constraint
226@nx._dispatch(edge_attrs="weight")
227def local_constraint(G, u, v, weight=None):
228 r"""Returns the local constraint on the node ``u`` with respect to
229 the node ``v`` in the graph ``G``.
231 Formally, the *local constraint on u with respect to v*, denoted
232 $\ell(v)$, is defined by
234 .. math::
236 \ell(u, v) = \left(p_{uv} + \sum_{w \in N(v)} p_{uw} p_{wv}\right)^2,
238 where $N(v)$ is the set of neighbors of $v$ and $p_{uv}$ is the
239 normalized mutual weight of the (directed or undirected) edges
240 joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. The *mutual
241 weight* of $u$ and $v$ is the sum of the weights of edges joining
242 them (edge weights are assumed to be one if the graph is
243 unweighted).
245 Parameters
246 ----------
247 G : NetworkX graph
248 The graph containing ``u`` and ``v``. This can be either
249 directed or undirected.
251 u : node
252 A node in the graph ``G``.
254 v : node
255 A node in the graph ``G``.
257 weight : None or string, optional
258 If None, all edge weights are considered equal.
259 Otherwise holds the name of the edge attribute used as weight.
261 Returns
262 -------
263 float
264 The constraint of the node ``v`` in the graph ``G``.
266 See also
267 --------
268 constraint
270 References
271 ----------
272 .. [1] Burt, Ronald S.
273 "Structural holes and good ideas".
274 American Journal of Sociology (110): 349–399.
276 """
277 nmw = normalized_mutual_weight
278 direct = nmw(G, u, v, weight=weight)
279 indirect = sum(
280 nmw(G, u, w, weight=weight) * nmw(G, w, v, weight=weight)
281 for w in set(nx.all_neighbors(G, u))
282 )
283 return (direct + indirect) ** 2