Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/bipartite/centrality.py: 15%

1import networkx as nx 

2 

3__all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"] 

4 

5 

6@nx._dispatch(name="bipartite_degree_centrality") 

7def degree_centrality(G, nodes): 

8 r"""Compute the degree centrality for nodes in a bipartite network. 

9 

10 The degree centrality for a node `v` is the fraction of nodes 

11 connected to it. 

12 

13 Parameters 

14 ---------- 

15 G : graph 

16 A bipartite network 

17 

18 nodes : list or container 

19 Container with all nodes in one bipartite node set. 

20 

21 Returns 

22 ------- 

23 centrality : dictionary 

24 Dictionary keyed by node with bipartite degree centrality as the value. 

25 

26 Examples 

27 -------- 

28 >>> G = nx.wheel_graph(5) 

29 >>> top_nodes = {0, 1, 2} 

30 >>> nx.bipartite.degree_centrality(G, nodes=top_nodes) 

31 {0: 2.0, 1: 1.5, 2: 1.5, 3: 1.0, 4: 1.0} 

32 

33 See Also 

34 -------- 

35 betweenness_centrality 

36 closeness_centrality 

37 :func:`~networkx.algorithms.bipartite.basic.sets` 

38 :func:`~networkx.algorithms.bipartite.basic.is_bipartite` 

39 

40 Notes 

41 ----- 

42 The nodes input parameter must contain all nodes in one bipartite node set, 

43 but the dictionary returned contains all nodes from both bipartite node 

44 sets. See :mod:`bipartite documentation <networkx.algorithms.bipartite>` 

45 for further details on how bipartite graphs are handled in NetworkX. 

46 

47 For unipartite networks, the degree centrality values are 

48 normalized by dividing by the maximum possible degree (which is 

49 `n-1` where `n` is the number of nodes in G). 

50 

51 In the bipartite case, the maximum possible degree of a node in a 

52 bipartite node set is the number of nodes in the opposite node set 

53 [1]_. The degree centrality for a node `v` in the bipartite 

54 sets `U` with `n` nodes and `V` with `m` nodes is 

55 

56 .. math:: 

57 

58 d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U , 

59 

60 d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V , 

61 

62 

63 where `deg(v)` is the degree of node `v`. 

64 

65 References 

66 ---------- 

67 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation 

68 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook 

69 of Social Network Analysis. Sage Publications. 

70 https://dx.doi.org/10.4135/9781446294413.n28 

71 """ 

72 top = set(nodes) 

73 bottom = set(G) - top 

74 s = 1.0 / len(bottom) 

75 centrality = {n: d * s for n, d in G.degree(top)} 

76 s = 1.0 / len(top) 

77 centrality.update({n: d * s for n, d in G.degree(bottom)}) 

78 return centrality 

79 

80 

81@nx._dispatch(name="bipartite_betweenness_centrality") 

82def betweenness_centrality(G, nodes): 

83 r"""Compute betweenness centrality for nodes in a bipartite network. 

84 

85 Betweenness centrality of a node `v` is the sum of the 

86 fraction of all-pairs shortest paths that pass through `v`. 

87 

88 Values of betweenness are normalized by the maximum possible 

89 value which for bipartite graphs is limited by the relative size 

90 of the two node sets [1]_. 

91 

92 Let `n` be the number of nodes in the node set `U` and 

93 `m` be the number of nodes in the node set `V`, then 

94 nodes in `U` are normalized by dividing by 

95 

96 .. math:: 

97 

98 \frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] , 

99 

100 where 

101 

102 .. math:: 

103 

104 s = (n - 1) \div m , t = (n - 1) \mod m , 

105 

106 and nodes in `V` are normalized by dividing by 

107 

108 .. math:: 

109 

110 \frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] , 

111 

112 where, 

113 

114 .. math:: 

115 

116 p = (m - 1) \div n , r = (m - 1) \mod n . 

117 

118 Parameters 

119 ---------- 

120 G : graph 

121 A bipartite graph 

122 

123 nodes : list or container 

124 Container with all nodes in one bipartite node set. 

125 

126 Returns 

127 ------- 

128 betweenness : dictionary 

129 Dictionary keyed by node with bipartite betweenness centrality 

130 as the value. 

131 

132 Examples 

133 -------- 

134 >>> G = nx.cycle_graph(4) 

135 >>> top_nodes = {1, 2} 

136 >>> nx.bipartite.betweenness_centrality(G, nodes=top_nodes) 

137 {0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25} 

138 

139 See Also 

140 -------- 

141 degree_centrality 

142 closeness_centrality 

143 :func:`~networkx.algorithms.bipartite.basic.sets` 

144 :func:`~networkx.algorithms.bipartite.basic.is_bipartite` 

145 

146 Notes 

147 ----- 

148 The nodes input parameter must contain all nodes in one bipartite node set, 

149 but the dictionary returned contains all nodes from both node sets. 

150 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` 

151 for further details on how bipartite graphs are handled in NetworkX. 

152 

153 

154 References 

155 ---------- 

156 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation 

157 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook 

158 of Social Network Analysis. Sage Publications. 

159 https://dx.doi.org/10.4135/9781446294413.n28 

160 """ 

161 top = set(nodes) 

162 bottom = set(G) - top 

163 n = len(top) 

164 m = len(bottom) 

165 s, t = divmod(n - 1, m) 

166 bet_max_top = ( 

167 ((m**2) * ((s + 1) ** 2)) 

168 + (m * (s + 1) * (2 * t - s - 1)) 

169 - (t * ((2 * s) - t + 3)) 

170 ) / 2.0 

171 p, r = divmod(m - 1, n) 

172 bet_max_bot = ( 

173 ((n**2) * ((p + 1) ** 2)) 

174 + (n * (p + 1) * (2 * r - p - 1)) 

175 - (r * ((2 * p) - r + 3)) 

176 ) / 2.0 

177 betweenness = nx.betweenness_centrality(G, normalized=False, weight=None) 

178 for node in top: 

179 betweenness[node] /= bet_max_top 

180 for node in bottom: 

181 betweenness[node] /= bet_max_bot 

182 return betweenness 

183 

184 

185@nx._dispatch(name="bipartite_closeness_centrality") 

186def closeness_centrality(G, nodes, normalized=True): 

187 r"""Compute the closeness centrality for nodes in a bipartite network. 

188 

189 The closeness of a node is the distance to all other nodes in the 

190 graph or in the case that the graph is not connected to all other nodes 

191 in the connected component containing that node. 

192 

193 Parameters 

194 ---------- 

195 G : graph 

196 A bipartite network 

197 

198 nodes : list or container 

199 Container with all nodes in one bipartite node set. 

200 

201 normalized : bool, optional 

202 If True (default) normalize by connected component size. 

203 

204 Returns 

205 ------- 

206 closeness : dictionary 

207 Dictionary keyed by node with bipartite closeness centrality 

208 as the value. 

209 

210 Examples 

211 -------- 

212 >>> G = nx.wheel_graph(5) 

213 >>> top_nodes = {0, 1, 2} 

214 >>> nx.bipartite.closeness_centrality(G, nodes=top_nodes) 

215 {0: 1.5, 1: 1.2, 2: 1.2, 3: 1.0, 4: 1.0} 

216 

217 See Also 

218 -------- 

219 betweenness_centrality 

220 degree_centrality 

221 :func:`~networkx.algorithms.bipartite.basic.sets` 

222 :func:`~networkx.algorithms.bipartite.basic.is_bipartite` 

223 

224 Notes 

225 ----- 

226 The nodes input parameter must contain all nodes in one bipartite node set, 

227 but the dictionary returned contains all nodes from both node sets. 

228 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` 

229 for further details on how bipartite graphs are handled in NetworkX. 

230 

231 

232 Closeness centrality is normalized by the minimum distance possible. 

233 In the bipartite case the minimum distance for a node in one bipartite 

234 node set is 1 from all nodes in the other node set and 2 from all 

235 other nodes in its own set [1]_. Thus the closeness centrality 

236 for node `v` in the two bipartite sets `U` with 

237 `n` nodes and `V` with `m` nodes is 

238 

239 .. math:: 

240 

241 c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U, 

242 

243 c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V, 

244 

245 where `d` is the sum of the distances from `v` to all 

246 other nodes. 

247 

248 Higher values of closeness indicate higher centrality. 

249 

250 As in the unipartite case, setting normalized=True causes the 

251 values to normalized further to n-1 / size(G)-1 where n is the 

252 number of nodes in the connected part of graph containing the 

253 node. If the graph is not completely connected, this algorithm 

254 computes the closeness centrality for each connected part 

255 separately. 

256 

257 References 

258 ---------- 

259 .. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation 

260 Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook 

261 of Social Network Analysis. Sage Publications. 

262 https://dx.doi.org/10.4135/9781446294413.n28 

263 """ 

264 closeness = {} 

265 path_length = nx.single_source_shortest_path_length 

266 top = set(nodes) 

267 bottom = set(G) - top 

268 n = len(top) 

269 m = len(bottom) 

270 for node in top: 

271 sp = dict(path_length(G, node)) 

272 totsp = sum(sp.values()) 

273 if totsp > 0.0 and len(G) > 1: 

274 closeness[node] = (m + 2 * (n - 1)) / totsp 

275 if normalized: 

276 s = (len(sp) - 1) / (len(G) - 1) 

277 closeness[node] *= s 

278 else: 

279 closeness[node] = 0.0 

280 for node in bottom: 

281 sp = dict(path_length(G, node)) 

282 totsp = sum(sp.values()) 

283 if totsp > 0.0 and len(G) > 1: 

284 closeness[node] = (n + 2 * (m - 1)) / totsp 

285 if normalized: 

286 s = (len(sp) - 1) / (len(G) - 1) 

287 closeness[node] *= s 

288 else: 

289 closeness[node] = 0.0 

290 return closeness