ioftools / networkxMiCe / networkxmaster / networkx / algorithms / structuralholes.py @ 5cef0f13
History  View  Annotate  Download (9.18 KB)
1 
# * encoding: utf8 *


2 
#

3 
# Copyright 20082019 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 
from __future__ import division 
11  
12 
import networkx as nx 
13  
14 
__all__ = ['constraint', 'local_constraint', 'effective_size'] 
15  
16  
17 
def mutual_weight(G, u, v, weight=None): 
18 
"""Returns the sum of the weights of the edge from `u` to `v` and

19 
the edge from `v` to `u` in `G`.

20 

21 
`weight` is the edge data key that represents the edge weight. If

22 
the specified key is `None` or is not in the edge data for an edge,

23 
that edge is assumed to have weight 1.

24 

25 
Preconditions: `u` and `v` must both be in `G`.

26 

27 
"""

28 
try:

29 
a_uv = G[u][v].get(weight, 1)

30 
except KeyError: 
31 
a_uv = 0

32 
try:

33 
a_vu = G[v][u].get(weight, 1)

34 
except KeyError: 
35 
a_vu = 0

36 
return a_uv + a_vu

37  
38  
39 
def normalized_mutual_weight(G, u, v, norm=sum, weight=None): 
40 
"""Returns normalized mutual weight of the edges from `u` to `v`

41 
with respect to the mutual weights of the neighbors of `u` in `G`.

42 

43 
`norm` specifies how the normalization factor is computed. It must

44 
be a function that takes a single argument and returns a number.

45 
The argument will be an iterable of mutual weights

46 
of pairs ``(u, w)``, where ``w`` ranges over each (in and

47 
out)neighbor of ``u``. Commons values for `normalization` are

48 
``sum`` and ``max``.

49 

50 
`weight` can be ``None`` or a string, if None, all edge weights

51 
are considered equal. Otherwise holds the name of the edge

52 
attribute used as weight.

53 

54 
"""

55 
scale = norm(mutual_weight(G, u, w, weight) 
56 
for w in set(nx.all_neighbors(G, u))) 
57 
return 0 if scale == 0 else mutual_weight(G, u, v, weight) / scale 
58  
59  
60 
def effective_size(G, nodes=None, weight=None): 
61 
r"""Returns the effective size of all nodes in the graph ``G``.

62 

63 
The *effective size* of a node's ego network is based on the concept

64 
of redundancy. A person's ego network has redundancy to the extent

65 
that her contacts are connected to each other as well. The

66 
nonredundant part of a person's relationships it's the effective

67 
size of her ego network [1]_. Formally, the effective size of a

68 
node $u$, denoted $e(u)$, is defined by

69 

70 
.. math::

71 

72 
e(u) = \sum_{v \in N(u) \setminus \{u\}}

73 
\left(1  \sum_{w \in N(v)} p_{uw} m_{vw}\right)

74 

75 
where $N(u)$ is the set of neighbors of $u$ and $p_{uw}$ is the

76 
normalized mutual weight of the (directed or undirected) edges

77 
joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. And $m_{vw}$

78 
is the mutual weight of $v$ and $w$ divided by $v$ highest mutual

79 
weight with any of its neighbors. The *mutual weight* of $u$ and $v$

80 
is the sum of the weights of edges joining them (edge weights are

81 
assumed to be one if the graph is unweighted).

82 

83 
For the case of unweighted and undirected graphs, Borgatti proposed

84 
a simplified formula to compute effective size [2]_

85 

86 
.. math::

87 

88 
e(u) = n  \frac{2t}{n}

89 

90 
where `t` is the number of ties in the ego network (not including

91 
ties to ego) and `n` is the number of nodes (excluding ego).

92 

93 
Parameters

94 


95 
G : NetworkX graph

96 
The graph containing ``v``. Directed graphs are treated like

97 
undirected graphs when computing neighbors of ``v``.

98 

99 
nodes : container, optional

100 
Container of nodes in the graph ``G`` to compute the effective size.

101 
If None, the effective size of every node is computed.

102 

103 
weight : None or string, optional

104 
If None, all edge weights are considered equal.

105 
Otherwise holds the name of the edge attribute used as weight.

106 

107 
Returns

108 


109 
dict

110 
Dictionary with nodes as keys and the constraint on the node as values.

111 

112 
Notes

113 


114 
Burt also defined the related concept of *efficiency* of a node's ego

115 
network, which is its effective size divided by the degree of that

116 
node [1]_. So you can easily compute efficiency:

117 

118 
>>> G = nx.DiGraph()

119 
>>> G.add_edges_from([(0, 1), (0, 2), (1, 0), (2, 1)])

120 
>>> esize = nx.effective_size(G)

121 
>>> efficiency = {n: v / G.degree(n) for n, v in esize.items()}

122 

123 
See also

124 


125 
constraint

126 

127 
References

128 


129 
.. [1] Burt, Ronald S.

130 
*Structural Holes: The Social Structure of Competition.*

131 
Cambridge: Harvard University Press, 1995.

132 

133 
.. [2] Borgatti, S.

134 
"Structural Holes: Unpacking Burt's Redundancy Measures"

135 
CONNECTIONS 20(1):3538.

136 
http://www.analytictech.com/connections/v20(1)/holes.htm

137 

138 
"""

139 
def redundancy(G, u, v, weight=None): 
140 
nmw = normalized_mutual_weight 
141 
r = sum(nmw(G, u, w, weight=weight) * nmw(G, v, w, norm=max, weight=weight) 
142 
for w in set(nx.all_neighbors(G, u))) 
143 
return 1  r 
144 
effective_size = {} 
145 
if nodes is None: 
146 
nodes = G 
147 
# Use Borgatti's simplified formula for unweighted and undirected graphs

148 
if not G.is_directed() and weight is None: 
149 
for v in nodes: 
150 
# Effective size is not defined for isolated nodes

151 
if len(G[v]) == 0: 
152 
effective_size[v] = float('nan') 
153 
continue

154 
E = nx.ego_graph(G, v, center=False, undirected=True) 
155 
effective_size[v] = len(E)  (2 * E.size()) / len(E) 
156 
else:

157 
for v in nodes: 
158 
# Effective size is not defined for isolated nodes

159 
if len(G[v]) == 0: 
160 
effective_size[v] = float('nan') 
161 
continue

162 
effective_size[v] = sum(redundancy(G, v, u, weight)

163 
for u in set(nx.all_neighbors(G, v))) 
164 
return effective_size

165  
166  
167 
def constraint(G, nodes=None, weight=None): 
168 
r"""Returns the constraint on all nodes in the graph ``G``.

169 

170 
The *constraint* is a measure of the extent to which a node *v* is

171 
invested in those nodes that are themselves invested in the

172 
neighbors of *v*. Formally, the *constraint on v*, denoted `c(v)`,

173 
is defined by

174 

175 
.. math::

176 

177 
c(v) = \sum_{w \in N(v) \setminus \{v\}} \ell(v, w)

178 

179 
where `N(v)` is the subset of the neighbors of `v` that are either

180 
predecessors or successors of `v` and `\ell(v, w)` is the local

181 
constraint on `v` with respect to `w` [1]_. For the definition of local

182 
constraint, see :func:`local_constraint`.

183 

184 
Parameters

185 


186 
G : NetworkX graph

187 
The graph containing ``v``. This can be either directed or undirected.

188 

189 
nodes : container, optional

190 
Container of nodes in the graph ``G`` to compute the constraint. If

191 
None, the constraint of every node is computed.

192 

193 
weight : None or string, optional

194 
If None, all edge weights are considered equal.

195 
Otherwise holds the name of the edge attribute used as weight.

196 

197 
Returns

198 


199 
dict

200 
Dictionary with nodes as keys and the constraint on the node as values.

201 

202 
See also

203 


204 
local_constraint

205 

206 
References

207 


208 
.. [1] Burt, Ronald S.

209 
"Structural holes and good ideas".

210 
American Journal of Sociology (110): 349–399.

211 

212 
"""

213 
if nodes is None: 
214 
nodes = G 
215 
constraint = {} 
216 
for v in nodes: 
217 
# Constraint is not defined for isolated nodes

218 
if len(G[v]) == 0: 
219 
constraint[v] = float('nan') 
220 
continue

221 
constraint[v] = sum(local_constraint(G, v, n, weight)

222 
for n in set(nx.all_neighbors(G, v))) 
223 
return constraint

224  
225  
226 
def local_constraint(G, u, v, weight=None): 
227 
r"""Returns the local constraint on the node ``u`` with respect to

228 
the node ``v`` in the graph ``G``.

229 

230 
Formally, the *local constraint on u with respect to v*, denoted

231 
$\ell(v)$, is defined by

232 

233 
.. math::

234 

235 
\ell(u, v) = \left(p_{uv} + \sum_{w \in N(v)} p_{uw} p{wv}\right)^2,

236 

237 
where $N(v)$ is the set of neighbors of $v$ and $p_{uv}$ is the

238 
normalized mutual weight of the (directed or undirected) edges

239 
joining $u$ and $v$, for each vertex $u$ and $v$ [1]_. The *mutual

240 
weight* of $u$ and $v$ is the sum of the weights of edges joining

241 
them (edge weights are assumed to be one if the graph is

242 
unweighted).

243 

244 
Parameters

245 


246 
G : NetworkX graph

247 
The graph containing ``u`` and ``v``. This can be either

248 
directed or undirected.

249 

250 
u : node

251 
A node in the graph ``G``.

252 

253 
v : node

254 
A node in the graph ``G``.

255 

256 
weight : None or string, optional

257 
If None, all edge weights are considered equal.

258 
Otherwise holds the name of the edge attribute used as weight.

259 

260 
Returns

261 


262 
float

263 
The constraint of the node ``v`` in the graph ``G``.

264 

265 
See also

266 


267 
constraint

268 

269 
References

270 


271 
.. [1] Burt, Ronald S.

272 
"Structural holes and good ideas".

273 
American Journal of Sociology (110): 349–399.

274 

275 
"""

276 
nmw = normalized_mutual_weight 
277 
direct = nmw(G, u, v, weight=weight) 
278 
indirect = sum(nmw(G, u, w, weight=weight) * nmw(G, w, v, weight=weight)

279 
for w in set(nx.all_neighbors(G, u))) 
280 
return (direct + indirect) ** 2 