## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/closeness.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 """ | |

2 Closeness centrality measures. | |

3 """ | |

4 import functools | |

5 import networkx as nx | |

6 from networkx.exception import NetworkXError | |

7 from networkx.utils.decorators import not_implemented_for | |

8 | |

9 __all__ = ["closeness_centrality", "incremental_closeness_centrality"] | |

10 | |

11 | |

12 def closeness_centrality(G, u=None, distance=None, wf_improved=True): | |

13 r"""Compute closeness centrality for nodes. | |

14 | |

15 Closeness centrality [1]_ of a node `u` is the reciprocal of the | |

16 average shortest path distance to `u` over all `n-1` reachable nodes. | |

17 | |

18 .. math:: | |

19 | |

20 C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}, | |

21 | |

22 where `d(v, u)` is the shortest-path distance between `v` and `u`, | |

23 and `n` is the number of nodes that can reach `u`. Notice that the | |

24 closeness distance function computes the incoming distance to `u` | |

25 for directed graphs. To use outward distance, act on `G.reverse()`. | |

26 | |

27 Notice that higher values of closeness indicate higher centrality. | |

28 | |

29 Wasserman and Faust propose an improved formula for graphs with | |

30 more than one connected component. The result is "a ratio of the | |

31 fraction of actors in the group who are reachable, to the average | |

32 distance" from the reachable actors [2]_. You might think this | |

33 scale factor is inverted but it is not. As is, nodes from small | |

34 components receive a smaller closeness value. Letting `N` denote | |

35 the number of nodes in the graph, | |

36 | |

37 .. math:: | |

38 | |

39 C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}, | |

40 | |

41 Parameters | |

42 ---------- | |

43 G : graph | |

44 A NetworkX graph | |

45 | |

46 u : node, optional | |

47 Return only the value for node u | |

48 | |

49 distance : edge attribute key, optional (default=None) | |

50 Use the specified edge attribute as the edge distance in shortest | |

51 path calculations | |

52 | |

53 wf_improved : bool, optional (default=True) | |

54 If True, scale by the fraction of nodes reachable. This gives the | |

55 Wasserman and Faust improved formula. For single component graphs | |

56 it is the same as the original formula. | |

57 | |

58 Returns | |

59 ------- | |

60 nodes : dictionary | |

61 Dictionary of nodes with closeness centrality as the value. | |

62 | |

63 See Also | |

64 -------- | |

65 betweenness_centrality, load_centrality, eigenvector_centrality, | |

66 degree_centrality, incremental_closeness_centrality | |

67 | |

68 Notes | |

69 ----- | |

70 The closeness centrality is normalized to `(n-1)/(|G|-1)` where | |

71 `n` is the number of nodes in the connected part of graph | |

72 containing the node. If the graph is not completely connected, | |

73 this algorithm computes the closeness centrality for each | |

74 connected part separately scaled by that parts size. | |

75 | |

76 If the 'distance' keyword is set to an edge attribute key then the | |

77 shortest-path length will be computed using Dijkstra's algorithm with | |

78 that edge attribute as the edge weight. | |

79 | |

80 The closeness centrality uses *inward* distance to a node, not outward. | |

81 If you want to use outword distances apply the function to `G.reverse()` | |

82 | |

83 In NetworkX 2.2 and earlier a bug caused Dijkstra's algorithm to use the | |

84 outward distance rather than the inward distance. If you use a 'distance' | |

85 keyword and a DiGraph, your results will change between v2.2 and v2.3. | |

86 | |

87 References | |

88 ---------- | |

89 .. [1] Linton C. Freeman: Centrality in networks: I. | |

90 Conceptual clarification. Social Networks 1:215-239, 1979. | |

91 http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | |

92 .. [2] pg. 201 of Wasserman, S. and Faust, K., | |

93 Social Network Analysis: Methods and Applications, 1994, | |

94 Cambridge University Press. | |

95 """ | |

96 if G.is_directed(): | |

97 G = G.reverse() # create a reversed graph view | |

98 | |

99 if distance is not None: | |

100 # use Dijkstra's algorithm with specified attribute as edge weight | |

101 path_length = functools.partial( | |

102 nx.single_source_dijkstra_path_length, weight=distance | |

103 ) | |

104 else: | |

105 path_length = nx.single_source_shortest_path_length | |

106 | |

107 if u is None: | |

108 nodes = G.nodes | |

109 else: | |

110 nodes = [u] | |

111 closeness_centrality = {} | |

112 for n in nodes: | |

113 sp = path_length(G, n) | |

114 totsp = sum(sp.values()) | |

115 len_G = len(G) | |

116 _closeness_centrality = 0.0 | |

117 if totsp > 0.0 and len_G > 1: | |

118 _closeness_centrality = (len(sp) - 1.0) / totsp | |

119 # normalize to number of nodes-1 in connected part | |

120 if wf_improved: | |

121 s = (len(sp) - 1.0) / (len_G - 1) | |

122 _closeness_centrality *= s | |

123 closeness_centrality[n] = _closeness_centrality | |

124 if u is not None: | |

125 return closeness_centrality[u] | |

126 else: | |

127 return closeness_centrality | |

128 | |

129 | |

130 @not_implemented_for("directed") | |

131 def incremental_closeness_centrality( | |

132 G, edge, prev_cc=None, insertion=True, wf_improved=True | |

133 ): | |

134 r"""Incremental closeness centrality for nodes. | |

135 | |

136 Compute closeness centrality for nodes using level-based work filtering | |

137 as described in Incremental Algorithms for Closeness Centrality by Sariyuce et al. | |

138 | |

139 Level-based work filtering detects unnecessary updates to the closeness | |

140 centrality and filters them out. | |

141 | |

142 --- | |

143 From "Incremental Algorithms for Closeness Centrality": | |

144 | |

145 Theorem 1: Let :math:`G = (V, E)` be a graph and u and v be two vertices in V | |

146 such that there is no edge (u, v) in E. Let :math:`G' = (V, E \cup uv)` | |

147 Then :math:`cc[s] = cc'[s]` if and only if :math:`\left|dG(s, u) - dG(s, v)\right| \leq 1`. | |

148 | |

149 Where :math:`dG(u, v)` denotes the length of the shortest path between | |

150 two vertices u, v in a graph G, cc[s] is the closeness centrality for a | |

151 vertex s in V, and cc'[s] is the closeness centrality for a | |

152 vertex s in V, with the (u, v) edge added. | |

153 --- | |

154 | |

155 We use Theorem 1 to filter out updates when adding or removing an edge. | |

156 When adding an edge (u, v), we compute the shortest path lengths from all | |

157 other nodes to u and to v before the node is added. When removing an edge, | |

158 we compute the shortest path lengths after the edge is removed. Then we | |

159 apply Theorem 1 to use previously computed closeness centrality for nodes | |

160 where :math:`\left|dG(s, u) - dG(s, v)\right| \leq 1`. This works only for | |

161 undirected, unweighted graphs; the distance argument is not supported. | |

162 | |

163 Closeness centrality [1]_ of a node `u` is the reciprocal of the | |

164 sum of the shortest path distances from `u` to all `n-1` other nodes. | |

165 Since the sum of distances depends on the number of nodes in the | |

166 graph, closeness is normalized by the sum of minimum possible | |

167 distances `n-1`. | |

168 | |

169 .. math:: | |

170 | |

171 C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}, | |

172 | |

173 where `d(v, u)` is the shortest-path distance between `v` and `u`, | |

174 and `n` is the number of nodes in the graph. | |

175 | |

176 Notice that higher values of closeness indicate higher centrality. | |

177 | |

178 Parameters | |

179 ---------- | |

180 G : graph | |

181 A NetworkX graph | |

182 | |

183 edge : tuple | |

184 The modified edge (u, v) in the graph. | |

185 | |

186 prev_cc : dictionary | |

187 The previous closeness centrality for all nodes in the graph. | |

188 | |

189 insertion : bool, optional | |

190 If True (default) the edge was inserted, otherwise it was deleted from the graph. | |

191 | |

192 wf_improved : bool, optional (default=True) | |

193 If True, scale by the fraction of nodes reachable. This gives the | |

194 Wasserman and Faust improved formula. For single component graphs | |

195 it is the same as the original formula. | |

196 | |

197 Returns | |

198 ------- | |

199 nodes : dictionary | |

200 Dictionary of nodes with closeness centrality as the value. | |

201 | |

202 See Also | |

203 -------- | |

204 betweenness_centrality, load_centrality, eigenvector_centrality, | |

205 degree_centrality, closeness_centrality | |

206 | |

207 Notes | |

208 ----- | |

209 The closeness centrality is normalized to `(n-1)/(|G|-1)` where | |

210 `n` is the number of nodes in the connected part of graph | |

211 containing the node. If the graph is not completely connected, | |

212 this algorithm computes the closeness centrality for each | |

213 connected part separately. | |

214 | |

215 References | |

216 ---------- | |

217 .. [1] Freeman, L.C., 1979. Centrality in networks: I. | |

218 Conceptual clarification. Social Networks 1, 215--239. | |

219 http://www.soc.ucsb.edu/faculty/friedkin/Syllabi/Soc146/Freeman78.PDF | |

220 .. [2] Sariyuce, A.E. ; Kaya, K. ; Saule, E. ; Catalyiirek, U.V. Incremental | |

221 Algorithms for Closeness Centrality. 2013 IEEE International Conference on Big Data | |

222 http://sariyuce.com/papers/bigdata13.pdf | |

223 """ | |

224 if prev_cc is not None and set(prev_cc.keys()) != set(G.nodes()): | |

225 raise NetworkXError("prev_cc and G do not have the same nodes") | |

226 | |

227 # Unpack edge | |

228 (u, v) = edge | |

229 path_length = nx.single_source_shortest_path_length | |

230 | |

231 if insertion: | |

232 # For edge insertion, we want shortest paths before the edge is inserted | |

233 du = path_length(G, u) | |

234 dv = path_length(G, v) | |

235 | |

236 G.add_edge(u, v) | |

237 else: | |

238 G.remove_edge(u, v) | |

239 | |

240 # For edge removal, we want shortest paths after the edge is removed | |

241 du = path_length(G, u) | |

242 dv = path_length(G, v) | |

243 | |

244 if prev_cc is None: | |

245 return nx.closeness_centrality(G) | |

246 | |

247 nodes = G.nodes() | |

248 closeness_centrality = {} | |

249 for n in nodes: | |

250 if n in du and n in dv and abs(du[n] - dv[n]) <= 1: | |

251 closeness_centrality[n] = prev_cc[n] | |

252 else: | |

253 sp = path_length(G, n) | |

254 totsp = sum(sp.values()) | |

255 len_G = len(G) | |

256 _closeness_centrality = 0.0 | |

257 if totsp > 0.0 and len_G > 1: | |

258 _closeness_centrality = (len(sp) - 1.0) / totsp | |

259 # normalize to number of nodes-1 in connected part | |

260 if wf_improved: | |

261 s = (len(sp) - 1.0) / (len_G - 1) | |

262 _closeness_centrality *= s | |

263 closeness_centrality[n] = _closeness_centrality | |

264 | |

265 # Leave the graph as we found it | |

266 if insertion: | |

267 G.remove_edge(u, v) | |

268 else: | |

269 G.add_edge(u, v) | |

270 | |

271 return closeness_centrality |