

# Introduction to closeness centrality



Closeness centrality is defined as the inverse of the sum of the shortest path distances from a node to all other nodes in the network. It is a measure of how close a node is to all other nodes in the network. Nodes with high closeness centrality are considered more influential or important in the network.

Consider a network with four nodes A, B, C, and D. The shortest path distances from node A to all other nodes are as follows:

- A to B: 1
- A to C: 2
- A to D: 3

The closeness centrality of node A is calculated as:

$$C(A) = \frac{1}{1 + 2 + 3} = \frac{1}{6}$$

## Exercise
Calculate the closeness centrality for the following network:

```
A--1--B
|\    |
| 2   |
|    \|
C--3--D
```

### Solution
```
C(A) = \frac{1}{1 + 2 + 3} = \frac{1}{6}
C(B) = \frac{1}{1 + 2 + 3} = \frac{1}{6}
C(C) = \frac{1}{1 + 2 + 3} = \frac{1}{6}
C(D) = \frac{1}{1 + 2 + 3} = \frac{1}{6}
```

# Definition and properties of closeness centrality

Closeness centrality is defined as the inverse of the sum of the shortest path distances from a node to all other nodes in the network. Mathematically, it is represented as:

$$C(i) = \frac{1}{\sum_{j=1}^{n-1} d(i, j)}$$

where $C(i)$ is the closeness centrality of node $i$, $d(i, j)$ is the shortest path distance between nodes $i$ and $j$, and $n$ is the total number of nodes in the network.

Closeness centrality has several properties:

- It is a normalized measure, meaning that it ranges between 0 and 1.
- A node with a high closeness centrality is closer to all other nodes in the network.
- Closeness centrality is sensitive to the network structure and the presence of hubs.
- Closeness centrality is not symmetric. That is, $C(i)$ does not necessarily equal $C(j)$ for nodes $i$ and $j$.

# Measures of closeness centrality

There are several measures of closeness centrality, each with its own advantages and disadvantages. Some of the commonly used measures are:

- **Local closeness centrality**: This measure is based on the shortest path distances between a node and its neighbors. It is calculated as the average of the shortest path distances to all neighbors of the node.

- **Global closeness centrality**: This measure is based on the shortest path distances between a node and all other nodes in the network. It is calculated as the inverse of the sum of the shortest path distances to all other nodes.

- **Betweenness centrality**: This measure is based on the number of shortest paths that pass through a node. It is calculated as the sum of the fractions of all shortest paths for which the node is part of the path.

- **Eigenvector centrality**: This measure is based on the eigenvectors of the adjacency matrix of the network. It is calculated as the largest eigenvalue of the adjacency matrix, with the corresponding eigenvector representing the centrality of each node.

# Algorithms for computing closeness centrality

There are several algorithms for computing closeness centrality, each with its own advantages and disadvantages. Some of the commonly used algorithms are:

- **Floyd-Warshall algorithm**: This algorithm computes the shortest path distances between all pairs of nodes in the network. It has a time complexity of $O(n^3)$, where $n$ is the number of nodes.

- **Dijkstra's algorithm**: This algorithm computes the shortest path distances between a source node and all other nodes in the network. It has a time complexity of $O(n^2)$ for dense networks and $O(n log n)$ for sparse networks.

- **PageRank algorithm**: This algorithm computes the closeness centrality of nodes in a network based on the importance of web pages. It is used by search engines like Google to rank web pages.

- **Centrality measures in NetworkX**: NetworkX is a popular Python library for network analysis. It provides several centrality measures, including closeness centrality, betweenness centrality, and eigenvector centrality.

# Real-world applications of closeness centrality

Closeness centrality has numerous real-world applications in various fields. Some of the applications include:

- **Social network analysis**: Closeness centrality can be used to identify influential individuals in social networks, such as Twitter or Facebook.

- **Transportation networks**: Closeness centrality can be used to identify nodes that are easily accessible from other nodes in transportation networks, such as road networks or public transportation systems.

- **Biological networks**: Closeness centrality can be used to identify genes or proteins that are closely connected to other genes or proteins in biological networks, such as protein-protein interaction networks.

- **Recommender systems**: Closeness centrality can be used to recommend items to users based on their closeness to other users who have interacted with the items.

# Limitations and challenges in closeness centrality

Despite its versatility, closeness centrality has some limitations and challenges:

- **Scalability**: Computing closeness centrality for large networks can be computationally expensive, especially when using the Floyd-Warshall algorithm.

- **Hubs**: Closeness centrality is sensitive to the presence of hubs in the network. Hubs can have a disproportionate influence on the closeness centrality of other nodes.

- **Sparse networks**: Closeness centrality is less meaningful in sparse networks, where most nodes have no connections.

- **Self-loops**: Closeness centrality is not defined for self-loops in the network. Self-loops can introduce errors in the computation of closeness centrality.

# Advanced topics in closeness centrality

- **Resistance distance**: Closeness centrality can be used to compute resistance distance in electrical networks. Resistance distance is the shortest path distance between two nodes in a network, considering the resistance values of the edges.

- **Weighted closeness centrality**: Closeness centrality can be extended to weighted networks, where the edges have different weights. This can be useful in networks with different types of connections, such as social networks with different types of interactions.

- **Temporal closeness centrality**: Closeness centrality can be computed over time, considering the evolution of the network over time. This can be useful in studying the evolution of influence or the spread of information in networks.

- **Approximation algorithms**: There are several approximation algorithms for computing closeness centrality, such as the Brandes algorithm or the Luby algorithm. These algorithms can provide a faster and more scalable solution for large networks.

# Case studies and examples

- **Twitter network**: Closeness centrality can be used to identify influential users in a Twitter network based on the shortest path distances between users.

- **Google search engine**: Closeness centrality can be used to rank web pages in the Google search engine based on the shortest path distances between web pages.

- **Protein-protein interaction networks**: Closeness centrality can be used to identify proteins that are closely connected to other proteins in a protein-protein interaction network.

- **Transportation networks**: Closeness centrality can be used to identify nodes that are easily accessible from other nodes in a transportation network, such as road networks or public transportation systems.

# Conclusion and summary of the textbook

In this textbook, we have covered the fundamentals of closeness centrality, its definition and properties, measures of closeness centrality, algorithms for computing closeness centrality, real-world applications, limitations and challenges, and advanced topics. Closeness centrality is a powerful measure in network analysis that can be applied to various fields, such as social networks, computer networks, and biological networks.

# Further reading and resources

For further reading and resources on closeness centrality, we recommend the following sources:

- Newman, M. E. J. (2006). Networks: An Introduction. Oxford University Press.
- Wasserman, S., & Faust, K. (2013). Social Network Analysis: Methods and Applications. Cengage Learning.
- Bonacich, J. M. (1978). Power and centrality: A family of measures. American Journal of Sociology, 84(5), 1072-1088.
- Luby, M. (2003). A note on the computation of betweenness centrality. Journal of Experimental Algorithmics, 8(1-2), 1-11.