closenesscentrality

Closeness centrality is a measure in network analysis that captures how close a given node is to all other nodes in a graph. It favors nodes that can rapidly interact with the rest of the network and is often interpreted as a proxy for the speed of information or influence dissemination from that node.

For a graph with n nodes, the standard closeness centrality of a node v is defined as C(v) = (n−1) / sum_{u ≠ v} d(v, u), where d(v, u) is the length of the shortest path between v and u. In weighted graphs, d uses the edge weights as distances. This form means a node in a fully connected graph has C(v) = 1 for all v, and nodes with shorter average distances to others have higher centrality. In graphs that are not connected, the sum may include infinite distances; practical variants address this by restricting to reachable nodes or by using harmonic centrality, which sums 1/d(v, u) over all other nodes (treating unreachable terms as zero).

Computation typically relies on shortest-path algorithms. In unweighted graphs, breadth-first search computes d(v, u) efficiently; in weighted graphs, Dijkstra’s algorithm is used. Overall, exact computation scales with the size of the network and the chosen algorithm, often requiring all-pairs shortest paths.

Variants and extensions include normalized closeness, which divides by the maximum possible value for comparability across networks, and harmonic centrality, which provides a measure that handles disconnected graphs more gracefully. Closeness centrality is widely used in social networks, infrastructure planning, epidemiology, and information diffusion studies, but it is sensitive to network connectivity and incomplete data. See also betweenness, eigenvector, and degree centrality.