# Closeness

### From visone user support

**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.

## Contents |

## Definition (simple case)

On directed, unweighted graphs that are strongly connected, the closeness centrality of a node is defined as the inverse of the sum of distances from *v* to all other nodes, i.e., it is

,

where denotes the length of a shortest directed path from *v* to *t*. The definition for connected undirected graphs is identical with 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

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*.

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 ; the sum of distances from Node 4 to all other nodes is 1 + 3 + 2 = 6 and, hence, it is . 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 is undefined (or sometimes, for convenience, set to , 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 . Hence, the closeness of all vertices can be computed in . On graphs with varying edge lengths ...