### comparison env/lib/python3.9/site-packages/networkx/algorithms/centrality/closeness.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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
64 --------
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
203 --------
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
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: