## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/algorithms/structuralholes.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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 |