Let \(G\) be a connected graph. The closeness centrality of a vertex is defined as
\[ c_C(u) = \frac{1}{\sum_{v\in V(G)} d(u,v)}\, , \qquad \left(\text{normalized } c_C(u) = \frac{n-1}{\sum_{v\in V(G)} d(u,v)} \right) \]where \(d(u,v)\) is the distance between \(u\) and \(v\). In other words: The closeness of a node is high if it is close to all other nodes in the network.
Closeness typically increases logarithmically. Hence the dynamic range of values is small; therefore, it does not have good discriminant power. Furthermore, it is sensitive to small fluctuations in the network structure, i.e., small changes in the structure of the network might change the order of the centralities substantially.
The exact computation of the centrality is based on the BFS (Dijkstra for weighted graphs). Therefore, the complexity is \(\mathcal{O}(n(n+m))\), where \(n=|V(G)|\) and \(m=|E(G)|\); and \(\mathcal{O}(n(m+n\log n))\) for weighted graphs.