A centrality measure captures the importance of a node within a network. Dependent on the application, different types of centrality can be important. ## Degree Centrality - The more edges a nodes has to other nodes, the more important it is. - For undirected graphs it is simply the degree $k_i$ of node $i$. In the [[Network Types#^daa3e3|Adjacency Matrix]] is means to either sum the row or column of the node. $ k_i = \sum_jA_{ij} $ - For directed graphs we distinguish between *indegree* and *outdegree centrality*, which sum up the incoming or outgoing edges. Here the notation $A_{ij}$ describes and edge going from node $i$ to $j$. Hence in the adjacency matrix we sum row-wise for the outdegree and column-wise for the indegree. $ k_i^{\text{out}}=\sum_jA_{ij} \quad \quad k_i^{\text{in}}=\sum_jA_{ji} $ ## Closeness Centrality How close is a node to all the other nodes in the network. The closer a node is to every other nodes the more important it is (think of the placement of a gas station in a transportation network). $ C_i=\left(\frac{1}{n-1} \sum_{j \not=i} d_{ij} \right)^{-1} $ We sum the distances $d_{ij}$ over all $j$ (excluding distance to $i$ itself). Then we divide by $(n-1)$ to get the average distance. Finally we take the inverse since low average distance means high centrality. >[!note:] >When the network has disconnected components, some distances will be infinity, which distorts the metric as a whole. Therefore harmonic centrality comes to rescue. ## Harmonic Centrality $ H_i= \frac{1}{n-1} \sum_{j \not = i} \frac{1}{d_{ij}} $ The harmonic centrality gives more weight to small distances. ## Betweenness Centrality Measures the extent to which a nodes lies on paths between other nodes. Again think about a transportation network, and which routes are essential to get from A to B. $ B_i=\frac{1}{n^2} \sum_{s,t}\frac{n^{i}_{st}}{g_{st}} $ - $n^{i}_{st}$ denotes the number of shortest paths between $s$ and $t$ which pass through $i$. - $g_{st}$ denotes the total number of shortest paths between $s$ and $t$. So we look at the fraction of shortest paths between two nodes that go through the specific node $i$. We sum these up for all possible combinations of $s$ and $t$. Finally we normalize by the number of these combinations, which is $n^2$.