Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/centrality/closeness.py: 15%
65 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Closeness centrality measures.
3"""
4import functools
6import networkx as nx
7from networkx.exception import NetworkXError
8from networkx.utils.decorators import not_implemented_for
10__all__ = ["closeness_centrality", "incremental_closeness_centrality"]
13@nx._dispatch(edge_attrs="distance")
14def closeness_centrality(G, u=None, distance=None, wf_improved=True):
15 r"""Compute closeness centrality for nodes.
17 Closeness centrality [1]_ of a node `u` is the reciprocal of the
18 average shortest path distance to `u` over all `n-1` reachable nodes.
20 .. math::
22 C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
24 where `d(v, u)` is the shortest-path distance between `v` and `u`,
25 and `n-1` is the number of nodes reachable from `u`. Notice that the
26 closeness distance function computes the incoming distance to `u`
27 for directed graphs. To use outward distance, act on `G.reverse()`.
29 Notice that higher values of closeness indicate higher centrality.
31 Wasserman and Faust propose an improved formula for graphs with
32 more than one connected component. The result is "a ratio of the
33 fraction of actors in the group who are reachable, to the average
34 distance" from the reachable actors [2]_. You might think this
35 scale factor is inverted but it is not. As is, nodes from small
36 components receive a smaller closeness value. Letting `N` denote
37 the number of nodes in the graph,
39 .. math::
41 C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
43 Parameters
44 ----------
45 G : graph
46 A NetworkX graph
48 u : node, optional
49 Return only the value for node u
51 distance : edge attribute key, optional (default=None)
52 Use the specified edge attribute as the edge distance in shortest
53 path calculations. If `None` (the default) all edges have a distance of 1.
54 Absent edge attributes are assigned a distance of 1. Note that no check
55 is performed to ensure that edges have the provided attribute.
57 wf_improved : bool, optional (default=True)
58 If True, scale by the fraction of nodes reachable. This gives the
59 Wasserman and Faust improved formula. For single component graphs
60 it is the same as the original formula.
62 Returns
63 -------
64 nodes : dictionary
65 Dictionary of nodes with closeness centrality as the value.
67 Examples
68 --------
69 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
70 >>> nx.closeness_centrality(G)
71 {0: 1.0, 1: 1.0, 2: 0.75, 3: 0.75}
73 See Also
74 --------
75 betweenness_centrality, load_centrality, eigenvector_centrality,
76 degree_centrality, incremental_closeness_centrality
78 Notes
79 -----
80 The closeness centrality is normalized to `(n-1)/(|G|-1)` where
81 `n` is the number of nodes in the connected part of graph
82 containing the node. If the graph is not completely connected,
83 this algorithm computes the closeness centrality for each
84 connected part separately scaled by that parts size.
86 If the 'distance' keyword is set to an edge attribute key then the
87 shortest-path length will be computed using Dijkstra's algorithm with
88 that edge attribute as the edge weight.
90 The closeness centrality uses *inward* distance to a node, not outward.
91 If you want to use outword distances apply the function to `G.reverse()`
93 In NetworkX 2.2 and earlier a bug caused Dijkstra's algorithm to use the
94 outward distance rather than the inward distance. If you use a 'distance'
95 keyword and a DiGraph, your results will change between v2.2 and v2.3.
97 References
98 ----------
99 .. [1] Linton C. Freeman: Centrality in networks: I.
100 Conceptual clarification. Social Networks 1:215-239, 1979.
101 https://doi.org/10.1016/0378-8733(78)90021-7
102 .. [2] pg. 201 of Wasserman, S. and Faust, K.,
103 Social Network Analysis: Methods and Applications, 1994,
104 Cambridge University Press.
105 """
106 if G.is_directed():
107 G = G.reverse() # create a reversed graph view
109 if distance is not None:
110 # use Dijkstra's algorithm with specified attribute as edge weight
111 path_length = functools.partial(
112 nx.single_source_dijkstra_path_length, weight=distance
113 )
114 else:
115 path_length = nx.single_source_shortest_path_length
117 if u is None:
118 nodes = G.nodes
119 else:
120 nodes = [u]
121 closeness_dict = {}
122 for n in nodes:
123 sp = path_length(G, n)
124 totsp = sum(sp.values())
125 len_G = len(G)
126 _closeness_centrality = 0.0
127 if totsp > 0.0 and len_G > 1:
128 _closeness_centrality = (len(sp) - 1.0) / totsp
129 # normalize to number of nodes-1 in connected part
130 if wf_improved:
131 s = (len(sp) - 1.0) / (len_G - 1)
132 _closeness_centrality *= s
133 closeness_dict[n] = _closeness_centrality
134 if u is not None:
135 return closeness_dict[u]
136 return closeness_dict
139@not_implemented_for("directed")
140@nx._dispatch
141def incremental_closeness_centrality(
142 G, edge, prev_cc=None, insertion=True, wf_improved=True
143):
144 r"""Incremental closeness centrality for nodes.
146 Compute closeness centrality for nodes using level-based work filtering
147 as described in Incremental Algorithms for Closeness Centrality by Sariyuce et al.
149 Level-based work filtering detects unnecessary updates to the closeness
150 centrality and filters them out.
152 ---
153 From "Incremental Algorithms for Closeness Centrality":
155 Theorem 1: Let :math:`G = (V, E)` be a graph and u and v be two vertices in V
156 such that there is no edge (u, v) in E. Let :math:`G' = (V, E \cup uv)`
157 Then :math:`cc[s] = cc'[s]` if and only if :math:`\left|dG(s, u) - dG(s, v)\right| \leq 1`.
159 Where :math:`dG(u, v)` denotes the length of the shortest path between
160 two vertices u, v in a graph G, cc[s] is the closeness centrality for a
161 vertex s in V, and cc'[s] is the closeness centrality for a
162 vertex s in V, with the (u, v) edge added.
163 ---
165 We use Theorem 1 to filter out updates when adding or removing an edge.
166 When adding an edge (u, v), we compute the shortest path lengths from all
167 other nodes to u and to v before the node is added. When removing an edge,
168 we compute the shortest path lengths after the edge is removed. Then we
169 apply Theorem 1 to use previously computed closeness centrality for nodes
170 where :math:`\left|dG(s, u) - dG(s, v)\right| \leq 1`. This works only for
171 undirected, unweighted graphs; the distance argument is not supported.
173 Closeness centrality [1]_ of a node `u` is the reciprocal of the
174 sum of the shortest path distances from `u` to all `n-1` other nodes.
175 Since the sum of distances depends on the number of nodes in the
176 graph, closeness is normalized by the sum of minimum possible
177 distances `n-1`.
179 .. math::
181 C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
183 where `d(v, u)` is the shortest-path distance between `v` and `u`,
184 and `n` is the number of nodes in the graph.
186 Notice that higher values of closeness indicate higher centrality.
188 Parameters
189 ----------
190 G : graph
191 A NetworkX graph
193 edge : tuple
194 The modified edge (u, v) in the graph.
196 prev_cc : dictionary
197 The previous closeness centrality for all nodes in the graph.
199 insertion : bool, optional
200 If True (default) the edge was inserted, otherwise it was deleted from the graph.
202 wf_improved : bool, optional (default=True)
203 If True, scale by the fraction of nodes reachable. This gives the
204 Wasserman and Faust improved formula. For single component graphs
205 it is the same as the original formula.
207 Returns
208 -------
209 nodes : dictionary
210 Dictionary of nodes with closeness centrality as the value.
212 See Also
213 --------
214 betweenness_centrality, load_centrality, eigenvector_centrality,
215 degree_centrality, closeness_centrality
217 Notes
218 -----
219 The closeness centrality is normalized to `(n-1)/(|G|-1)` where
220 `n` is the number of nodes in the connected part of graph
221 containing the node. If the graph is not completely connected,
222 this algorithm computes the closeness centrality for each
223 connected part separately.
225 References
226 ----------
227 .. [1] Freeman, L.C., 1979. Centrality in networks: I.
228 Conceptual clarification. Social Networks 1, 215--239.
229 https://doi.org/10.1016/0378-8733(78)90021-7
230 .. [2] Sariyuce, A.E. ; Kaya, K. ; Saule, E. ; Catalyiirek, U.V. Incremental
231 Algorithms for Closeness Centrality. 2013 IEEE International Conference on Big Data
232 http://sariyuce.com/papers/bigdata13.pdf
233 """
234 if prev_cc is not None and set(prev_cc.keys()) != set(G.nodes()):
235 raise NetworkXError("prev_cc and G do not have the same nodes")
237 # Unpack edge
238 (u, v) = edge
239 path_length = nx.single_source_shortest_path_length
241 if insertion:
242 # For edge insertion, we want shortest paths before the edge is inserted
243 du = path_length(G, u)
244 dv = path_length(G, v)
246 G.add_edge(u, v)
247 else:
248 G.remove_edge(u, v)
250 # For edge removal, we want shortest paths after the edge is removed
251 du = path_length(G, u)
252 dv = path_length(G, v)
254 if prev_cc is None:
255 return nx.closeness_centrality(G)
257 nodes = G.nodes()
258 closeness_dict = {}
259 for n in nodes:
260 if n in du and n in dv and abs(du[n] - dv[n]) <= 1:
261 closeness_dict[n] = prev_cc[n]
262 else:
263 sp = path_length(G, n)
264 totsp = sum(sp.values())
265 len_G = len(G)
266 _closeness_centrality = 0.0
267 if totsp > 0.0 and len_G > 1:
268 _closeness_centrality = (len(sp) - 1.0) / totsp
269 # normalize to number of nodes-1 in connected part
270 if wf_improved:
271 s = (len(sp) - 1.0) / (len_G - 1)
272 _closeness_centrality *= s
273 closeness_dict[n] = _closeness_centrality
275 # Leave the graph as we found it
276 if insertion:
277 G.remove_edge(u, v)
278 else:
279 G.add_edge(u, v)
281 return closeness_dict