Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Closeness centrality measures.
3"""
5import functools
7import networkx as nx
8from networkx.exception import NetworkXError
9from networkx.utils.decorators import not_implemented_for
11__all__ = ["closeness_centrality", "incremental_closeness_centrality"]
14@nx._dispatchable(edge_attrs="distance")
15def closeness_centrality(G, u=None, distance=None, wf_improved=True):
16 r"""Compute closeness centrality for nodes.
18 Closeness centrality [1]_ of a node `u` is the reciprocal of the
19 average shortest path distance to `u` over all `n-1` reachable nodes.
21 .. math::
23 C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
25 where `d(v, u)` is the shortest-path distance between `v` and `u`,
26 and `n-1` is the number of nodes reachable from `u`. Notice that the
27 closeness distance function computes the incoming distance to `u`
28 for directed graphs. To use outward distance, act on `G.reverse()`.
30 Notice that higher values of closeness indicate higher centrality.
32 Wasserman and Faust propose an improved formula for graphs with
33 more than one connected component. The result is "a ratio of the
34 fraction of actors in the group who are reachable, to the average
35 distance" from the reachable actors [2]_. You might think this
36 scale factor is inverted but it is not. As is, nodes from small
37 components receive a smaller closeness value. Letting `N` denote
38 the number of nodes in the graph,
40 .. math::
42 C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
44 Parameters
45 ----------
46 G : graph
47 A NetworkX graph
49 u : node, optional
50 Return only the value for node u
52 distance : edge attribute key, optional (default=None)
53 Use the specified edge attribute as the edge distance in shortest
54 path calculations. If `None` (the default) all edges have a distance of 1.
55 Absent edge attributes are assigned a distance of 1. Note that no check
56 is performed to ensure that edges have the provided attribute.
58 wf_improved : bool, optional (default=True)
59 If True, scale by the fraction of nodes reachable. This gives the
60 Wasserman and Faust improved formula. For single component graphs
61 it is the same as the original formula.
63 Returns
64 -------
65 nodes : dictionary
66 Dictionary of nodes with closeness centrality as the value.
68 Examples
69 --------
70 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
71 >>> nx.closeness_centrality(G)
72 {0: 1.0, 1: 1.0, 2: 0.75, 3: 0.75}
74 See Also
75 --------
76 betweenness_centrality, load_centrality, eigenvector_centrality,
77 degree_centrality, incremental_closeness_centrality
79 Notes
80 -----
81 The closeness centrality is normalized to `(n-1)/(|G|-1)` where
82 `n` is the number of nodes in the connected part of graph
83 containing the node. If the graph is not completely connected,
84 this algorithm computes the closeness centrality for each
85 connected part separately scaled by that parts size.
87 If the 'distance' keyword is set to an edge attribute key then the
88 shortest-path length will be computed using Dijkstra's algorithm with
89 that edge attribute as the edge weight.
91 The closeness centrality uses *inward* distance to a node, not outward.
92 If you want to use outword distances apply the function to `G.reverse()`
94 In NetworkX 2.2 and earlier a bug caused Dijkstra's algorithm to use the
95 outward distance rather than the inward distance. If you use a 'distance'
96 keyword and a DiGraph, your results will change between v2.2 and v2.3.
98 References
99 ----------
100 .. [1] Linton C. Freeman: Centrality in networks: I.
101 Conceptual clarification. Social Networks 1:215-239, 1979.
102 https://doi.org/10.1016/0378-8733(78)90021-7
103 .. [2] pg. 201 of Wasserman, S. and Faust, K.,
104 Social Network Analysis: Methods and Applications, 1994,
105 Cambridge University Press.
106 """
107 if G.is_directed():
108 G = G.reverse() # create a reversed graph view
110 if distance is not None:
111 # use Dijkstra's algorithm with specified attribute as edge weight
112 path_length = functools.partial(
113 nx.single_source_dijkstra_path_length, weight=distance
114 )
115 else:
116 path_length = nx.single_source_shortest_path_length
118 if u is None:
119 nodes = G.nodes
120 else:
121 nodes = [u]
122 closeness_dict = {}
123 for n in nodes:
124 sp = path_length(G, n)
125 totsp = sum(sp.values())
126 len_G = len(G)
127 _closeness_centrality = 0.0
128 if totsp > 0.0 and len_G > 1:
129 _closeness_centrality = (len(sp) - 1.0) / totsp
130 # normalize to number of nodes-1 in connected part
131 if wf_improved:
132 s = (len(sp) - 1.0) / (len_G - 1)
133 _closeness_centrality *= s
134 closeness_dict[n] = _closeness_centrality
135 if u is not None:
136 return closeness_dict[u]
137 return closeness_dict
140@not_implemented_for("directed")
141@nx._dispatchable(mutates_input=True)
142def incremental_closeness_centrality(
143 G, edge, prev_cc=None, insertion=True, wf_improved=True
144):
145 r"""Incremental closeness centrality for nodes.
147 Compute closeness centrality for nodes using level-based work filtering
148 as described in Incremental Algorithms for Closeness Centrality by Sariyuce et al.
150 Level-based work filtering detects unnecessary updates to the closeness
151 centrality and filters them out.
153 ---
154 From "Incremental Algorithms for Closeness Centrality":
156 Theorem 1: Let :math:`G = (V, E)` be a graph and u and v be two vertices in V
157 such that there is no edge (u, v) in E. Let :math:`G' = (V, E \cup uv)`
158 Then :math:`cc[s] = cc'[s]` if and only if :math:`\left|dG(s, u) - dG(s, v)\right| \leq 1`.
160 Where :math:`dG(u, v)` denotes the length of the shortest path between
161 two vertices u, v in a graph G, cc[s] is the closeness centrality for a
162 vertex s in V, and cc'[s] is the closeness centrality for a
163 vertex s in V, with the (u, v) edge added.
164 ---
166 We use Theorem 1 to filter out updates when adding or removing an edge.
167 When adding an edge (u, v), we compute the shortest path lengths from all
168 other nodes to u and to v before the node is added. When removing an edge,
169 we compute the shortest path lengths after the edge is removed. Then we
170 apply Theorem 1 to use previously computed closeness centrality for nodes
171 where :math:`\left|dG(s, u) - dG(s, v)\right| \leq 1`. This works only for
172 undirected, unweighted graphs; the distance argument is not supported.
174 Closeness centrality [1]_ of a node `u` is the reciprocal of the
175 sum of the shortest path distances from `u` to all `n-1` other nodes.
176 Since the sum of distances depends on the number of nodes in the
177 graph, closeness is normalized by the sum of minimum possible
178 distances `n-1`.
180 .. math::
182 C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},
184 where `d(v, u)` is the shortest-path distance between `v` and `u`,
185 and `n` is the number of nodes in the graph.
187 Notice that higher values of closeness indicate higher centrality.
189 Parameters
190 ----------
191 G : graph
192 A NetworkX graph
194 edge : tuple
195 The modified edge (u, v) in the graph.
197 prev_cc : dictionary
198 The previous closeness centrality for all nodes in the graph.
200 insertion : bool, optional
201 If True (default) the edge was inserted, otherwise it was deleted from the graph.
203 wf_improved : bool, optional (default=True)
204 If True, scale by the fraction of nodes reachable. This gives the
205 Wasserman and Faust improved formula. For single component graphs
206 it is the same as the original formula.
208 Returns
209 -------
210 nodes : dictionary
211 Dictionary of nodes with closeness centrality as the value.
213 See Also
214 --------
215 betweenness_centrality, load_centrality, eigenvector_centrality,
216 degree_centrality, closeness_centrality
218 Notes
219 -----
220 The closeness centrality is normalized to `(n-1)/(|G|-1)` where
221 `n` is the number of nodes in the connected part of graph
222 containing the node. If the graph is not completely connected,
223 this algorithm computes the closeness centrality for each
224 connected part separately.
226 References
227 ----------
228 .. [1] Freeman, L.C., 1979. Centrality in networks: I.
229 Conceptual clarification. Social Networks 1, 215--239.
230 https://doi.org/10.1016/0378-8733(78)90021-7
231 .. [2] Sariyuce, A.E. ; Kaya, K. ; Saule, E. ; Catalyiirek, U.V. Incremental
232 Algorithms for Closeness Centrality. 2013 IEEE International Conference on Big Data
233 http://sariyuce.com/papers/bigdata13.pdf
234 """
235 if prev_cc is not None and set(prev_cc.keys()) != set(G.nodes()):
236 raise NetworkXError("prev_cc and G do not have the same nodes")
238 # Unpack edge
239 (u, v) = edge
240 path_length = nx.single_source_shortest_path_length
242 if insertion:
243 # For edge insertion, we want shortest paths before the edge is inserted
244 du = path_length(G, u)
245 dv = path_length(G, v)
247 G.add_edge(u, v)
248 else:
249 G.remove_edge(u, v)
251 # For edge removal, we want shortest paths after the edge is removed
252 du = path_length(G, u)
253 dv = path_length(G, v)
255 if prev_cc is None:
256 return nx.closeness_centrality(G)
258 nodes = G.nodes()
259 closeness_dict = {}
260 for n in nodes:
261 if n in du and n in dv and abs(du[n] - dv[n]) <= 1:
262 closeness_dict[n] = prev_cc[n]
263 else:
264 sp = path_length(G, n)
265 totsp = sum(sp.values())
266 len_G = len(G)
267 _closeness_centrality = 0.0
268 if totsp > 0.0 and len_G > 1:
269 _closeness_centrality = (len(sp) - 1.0) / totsp
270 # normalize to number of nodes-1 in connected part
271 if wf_improved:
272 s = (len(sp) - 1.0) / (len_G - 1)
273 _closeness_centrality *= s
274 closeness_dict[n] = _closeness_centrality
276 # Leave the graph as we found it
277 if insertion:
278 G.remove_edge(u, v)
279 else:
280 G.add_edge(u, v)
282 return closeness_dict