Closeness

Closeness is a radial measure of centrality that favors actors that can reach many others via short paths. Intuitively, if the graph represents a transportation network, then a node with high closeness would make a good location for a warehouse since the average distance to all other locations (i.e., all other nodes in the graph) is relatively short. In information-spreading networks, a node with high closeness centrality would be a good choice to start a rumor since many others can be reached with relatively few intermediates.

Definition (simple case)

On directed, unweighted graphs $\displaystyle {G=(V,E)}$ that are strongly connected, the closeness centrality $\displaystyle {c_{C}(v)}$ of a node $v\in V$ is defined as the inverse of the sum of distances from $v$ to all other nodes, i.e., it is

$c_{C}(v)={\frac {1}{\sum \limits _{t\in V\setminus v}d_{G}(v,t)}}$,

where $\displaystyle {d_{G}(v,t)}$ denotes the length of a shortest directed path from $v$ to $t$. The definition for connected undirected graphs is identical with $\displaystyle {d_{G}(v,t)}$ being defined as the length of a shortest path.

Example

Consider the directed graph below. For example, the length of a shortest path from Node 1 to Node 3 is one while the distance from 3 to 1 equals two, since edges can only be traveled in the specified direction. The length of a shortest path from Node 4 to Node 2 is three; the unique shortest path connecting these nodes is $4\rightarrow 1\rightarrow 3\rightarrow 2$

All pairwise distances are listed in the following matrix where the entry in row $u$ and column $v$ is equal to the distance from node $u$ to node $v$.

${\begin{bmatrix}\cdot &2&1&2\\1&\cdot &1&2\\2&1&\cdot &1\\1&3&2&\cdot \end{bmatrix}}$

The inverse closeness centrality (i.e., the denominator in the formula above) of node $v$ is equal to the row sum in the above matrix. For instance, the sum of distances from Node 1 to all other nodes is $2+1+2=5$ and, hence, it is $\displaystyle {c_{C}(1)=1/5=0.2}$; the sum of distances from Node 4 to all other nodes is $1+3+2=6$ and, hence, it is $\displaystyle {c_{C}(1)=1/6\approx 0.167}$. The closeness centrality of all nodes is shown in the image below.

Special cases

Unconnected graphs

The definition of closeness centrality needs to be adapted for cases in which the graph is not strongly connected. Indeed, if a node $u$ is not reachable from another node $v$, then the distance $\displaystyle {d_{G}(v,u)}$ is undefined (or sometimes, for convenience, set to $\infty$, which is no help either) implying that the closeness formula presented above is undefined as well. Furthermore, it would be a bad choice to simply drop the unreachable nodes from the summation, since then adding an outgoing link to a node could actually decrease its closeness centrality in such a way that it looses its closeness rank compared to other nodes. Possibilities to generalize closeness centrality to graphs that are not strongly connected include ...

Edge weights and distances

If a link length has been selected, the length of an $(v,t)$-path is the sum of the length of all links in the path.

Implementation in visone

Normalization and treatment of special cases

Standardize ...

Algorithmic runtime

The closeness centrality of one node $v$ can be computed by a single breadth-first-search (BFS) starting at $v$. On graphs without edge weights, BFS has a run-time linear in the size of the graph, i.e., in ${\mathcal {O}}(|V|+|E|)$. Hence, the closeness of all vertices can be computed in ${\mathcal {O}}(|V|^{2}+|E|\cdot |V|)$. On graphs with varying edge lengths ...

Related measures

• Radiality
• Eccentricity
• Current-flow closeness