In graph theory, Centrality is a measure of how "important" a node is in a graph. Based on its connectivity to other nodes. It is relevant in the study of social networks because it can help identify individuals or groups that are influential in the network and understand how information or behavior may flow through the network. There are many different measures of centrality.
|
Table of Contents
|
Overview
Below is an incomplete list of commonly used centrality measures. For example, in the study of social networks:
- Degree Centrality can be useful in studying the basic overall popularity of individuals or hubs in a social network.
- Closeness Centrality can be useful in identifying individuals who are central in terms of the overall network structure and could have a strong influence on the network.
- Betweenness Centrality can be useful in identifying individuals who play important roles in facilitating communication and information flow between different parts of the network.
- Eigenvector Centrality can be useful in identifying individuals who are connected to other important individuals, and thus have a high level of influence in the network.
- Laplacian Centrality can be useful in identifying nodes that have influence over the entire network, and could be important for controlling or shaping network behavior.
- Exp Subgraph Centrality can be useful in identifying nodes that are important for community detection, and thus can help understand the structure of the network.
- Communicability Centrality can be useful in identifying nodes that play a key role in information flow between all pairs of nodes, and thus can help understand how information spreads through the network.
- Information Centrality can be useful in identifying nodes that are important for transmitting information through the network, and thus can help understand how information is disseminated.
- Load Centrality can be useful in identifying nodes that are important for directing traffic flow through the network, and thus can help understand how resources or information are distributed.
Static Centrality
Degree Centrality
Degree centrality, which is defined as the number of links incident upon a node. In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely indegree and outdegree. For each vertex $i$, for a given graph $G$, we define degree centrality as:
$$C_i = d_i = \deg(i)$$
Closeness Centrality
Closeness centrality is a measure of how quickly information spreads from a given node to other nodes in a network. It is defined as the inverse of the sum of the shortest path distances between a node and all other nodes in the network. For each vertex $i$, for a given graph $G$, we define closeness centrality as:
$$C_i = \frac{1}{\sum_{j \neq i} d_{ij}}$$
where $d_{ij}$ is the shortest path distance between nodes $i$ and $j$.
Betweenness Centrality
Betweenness centrality is a measure of how important a node is in connecting other nodes in a network. It is defined as the number of shortest paths between all pairs of nodes in the network that pass through a given node. For each vertex $i$, for a given graph $G$, we define betweenness centrality as:
$$C_i = \sum_{s \neq i \neq t} \frac{\sigma_{st}(i)}{\sigma_{st}}$$
where $\sigma_{st}$ is the number of shortest paths from node $s$ to node $t$, and $\sigma_{st}(i)$ is the number of shortest paths from $s$ to $t$ that pass through node $i$.
Eigenvector Centrality
Eigenvector centrality is a measure of how well connected a node is to other well connected nodes in a network. It is defined as the principal eigenvector of the adjacency matrix of the network. For each vertex $i$, for a given graph $G$, we define eigenvector centrality as:
$$C_i = \frac{1}{\lambda} \sum_j A_{ij}C_j$$
where $A$ is the adjacency matrix of the network, $\lambda$ is the largest eigenvalue of $A$, and $C_j$ is the eigenvector centrality of node $j$.
Laplacian Centrality
See also: Graph Laplacian
Laplacian centrality is a measure of how well connected a node is to the rest of the network, taking into account the degree of the neighboring nodes. It is defined as the sum of the squared differences between a node's degree and the degrees of its neighbors. For each vertex $i$, for a given graph $G$, we define Laplacian centrality as:
$$C_i = \sum_{j \neq i} (d_i - d_j)^2 A_{ij}$$
where $d_i$ is the degree of node $i$, and $A_{ij}$ is the adjacency matrix of the network.
Exponential Subgraph Centrality
Exponential subgraph centrality is a measure of how well connected a node is to other nodes in a network, taking into account the structure of the network. It is defined as the sum of the weights of all subgraphs that contain a given node, where the weight of a subgraph is proportional to the product of the weights of its edges. For each vertex $i$, for a given graph $G$, we define exponential subgraph centrality as:
$$C_i = \sum_{S \subseteq G} w(S) e^{-\alpha |S|} [i \in S]$$
where $w(S)$ is the weight of subgraph $S$, $\alpha$ is a constant, and $[i \in S]$ is the indicator function that takes the value 1 if node $i$ is in subgraph $S$, and 0 otherwise.
Communicability Centrality
Communicability centrality is a measure of how easily information can flow between all pairs of nodes in a network. It is defined as the sum of the entries of the matrix exponential of the adjacency matrix of the network. For each vertex $i$, for a given graph $G$, we define communicability centrality as:
$$C_i = \sum_{j \neq i} e^{-(A^{+})_{ij}}$$
where $A^{+}$ is the pseudoinverse of the adjacency matrix $A$.
Information Centrality
Information centrality is a measure of how important a node is in transmitting information through a network. It is defined as the total amount of information that passes through a node when all nodes in the network communicate with each other. For each vertex $i$, for a given graph $G$, we define information centrality as:
$$C_i = \sum_{j \neq i} I(i;j)$$
where $I(i;j)$ is the mutual information between nodes $i$ and $j$.
Load Centrality
Load centrality is a measure of how much traffic passes through a node in a network. It is defined as the sum of the shortest path distances between a node and all other nodes in the network, weighted by the inverse of the distance. For each vertex $i$, for a given graph $G$, we define load centrality as:
$$C_i = \sum_{j \neq i} \frac{1}{d_{ij}}$$
where $d_{ij}$ is the shortest path distance between nodes $i$ and $j$.
Dynamic Centrality Measures
Dynamic centrality measures are used to study the evolution of graphs over time.
Percolation Centrality
One such measure is percolation centrality, which characterizes the importance of nodes in a graph that is subject to edge deletions over time. Percolation centrality is defined as the expected size of the largest connected component containing a node, when edges are deleted randomly with probability p. It can be computed efficiently using Monte Carlo simulations. The percolation centrality of a node can provide insights into its robustness and resilience to edge deletions in dynamic networks. The equation to calculate percolation centrality for a node $i$ in a graph $G$ is given by:
$$C_i(p) = \sum_{S\subseteq G-i} P(S) \cdot f_S(i,p)$$
where $S$ is a set of nodes in the graph $G$ that excludes $i$, $P(S)$ is the probability of $S$ being connected, and $f_S(i,p)$ is the probability that $i$ is part of the largest connected component of $G-S$ after deleting edges with probability $p$.
Equivalently, percolation centrality of a node is defined as the sum of the size of the connected components that remain in the graph after removing that node over time. It can be expressed mathematically as follows:
$$\mathit{C}_i = \sum_{t=1}^T \frac{s_i(t)}{s_G(t)}$$
Where $T$ is the number of time steps, $s_i(t)$ is the size of the largest connected component in the graph after removing node $i$ at time $t$, and $s_G(t)$ is the size of the largest connected component in the original graph at time $t$.
See also
|