networkx.algorithms.centrality.closeness_centrality¶
- closeness_centrality(G, u=None, distance=None, wf_improved=True)[source]¶
Compute closeness centrality for nodes.
Closeness centrality [1] of a node
u
is the reciprocal of the average shortest path distance tou
over alln-1
reachable nodes.\[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},\]where
d(v, u)
is the shortest-path distance betweenv
andu
, andn
is the number of nodes that can reachu
. Notice that the closeness distance function computes the incoming distance tou
for directed graphs. To use outward distance, act onG.reverse()
.Notice that higher values of closeness indicate higher centrality.
Wasserman and Faust propose an improved formula for graphs with more than one connected component. The result is “a ratio of the fraction of actors in the group who are reachable, to the average distance” from the reachable actors [2]. You might think this scale factor is inverted but it is not. As is, nodes from small components receive a smaller closeness value. Letting
N
denote the number of nodes in the graph,\[C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},\]- Parameters
- Ggraph
A NetworkX graph
- unode, optional
Return only the value for node u
- distanceedge attribute key, optional (default=None)
Use the specified edge attribute as the edge distance in shortest path calculations
- wf_improvedbool, optional (default=True)
If True, scale by the fraction of nodes reachable. This gives the Wasserman and Faust improved formula. For single component graphs it is the same as the original formula.
- Returns
- nodesdictionary
Dictionary of nodes with closeness centrality as the value.
See also
Notes
The closeness centrality is normalized to
(n-1)/(|G|-1)
wheren
is the number of nodes in the connected part of graph containing the node. If the graph is not completely connected, this algorithm computes the closeness centrality for each connected part separately scaled by that parts size.If the ‘distance’ keyword is set to an edge attribute key then the shortest-path length will be computed using Dijkstra’s algorithm with that edge attribute as the edge weight.
The closeness centrality uses inward distance to a node, not outward. If you want to use outword distances apply the function to
G.reverse()
In NetworkX 2.2 and earlier a bug caused Dijkstra’s algorithm to use the outward distance rather than the inward distance. If you use a ‘distance’ keyword and a DiGraph, your results will change between v2.2 and v2.3.
References
- 1
Linton C. Freeman: Centrality in networks: I. Conceptual clarification. Social Networks 1:215-239, 1979. https://doi.org/10.1016/0378-8733(78)90021-7
- 2
pg. 201 of Wasserman, S. and Faust, K., Social Network Analysis: Methods and Applications, 1994, Cambridge University Press.