📂Graph Theory

Network Mediation Centrality in Network Theory

Definition ¹

Stress Centrality

In a network $\left( V, E \right)$, let’s denote by $\sigma_{st} = \sigma_{ts}$ the number of shortest paths between two nodes $s,t \in V$, and specifically, let’s denote by $\sigma_{st} (v)$ the number of paths including another node $v \in V$ among the paths connecting $s,t$. The following defined $C_{S} : V \to \mathbb{Z}$ is called the Stress Centrality of node $v$. $$ C_{S} (v) := \sum_{s \ne v \ne t \in V} \sigma_{st} (v) $$

Betweenness Centrality

The following defined $C_{S} : V \to \mathbb{R}$ is called the Betweenness Centrality of node $v$. $$ C_{B} (v) := \sum_{s \ne v \ne t \in V} {{ \sigma_{st} (v) } \over { \sigma_{st} }} $$

Explanation

$\sigma_{st} (v)$

Reading the definition of $\sigma_{st}$ carefully, it’s about the number of routes that make the shortest distance $d(s,t) = d(t,s)$ between $s,t$, not the shortest distance itself, so for all $v \in V$, $\sigma_{vv} = 1$, and for the graph distance function $d$, $\sigma_{st} (v)$ is as follows. $$ \sigma_{st} (v) = \begin{cases} 0 & , \text{if } d \left( s , t \right) < d \left( s , v \right) + d \left( v , t \right) \\ \sigma_{sv} \cdot \sigma_{vt} & , \text{otherwise} \end{cases} $$

Intuitive Meaning

$$ C_{S} (v) = \sum_{s \ne v \ne t \in V} \sigma_{st} (v) \\ C_{B} (v) = \sum_{s \ne v \ne t \in V} {{ \sigma_{st} (v) } \over { \sigma_{st} }} $$ Betweenness Centrality, essentially the same concept as Stress Centrality, naturally illustrates how important a node is in terms of traffic/communication. Unlike Stress Centrality, it’s adjusted by dividing $\sigma_{st}$ for each $s,t$ to more appropriately evaluate the node.

See Also

Various Centrality in Network

• Degree Centrality
• Betweenness Centrality
  • Stress Centrality
• Closeness Centrality
• Eigenvector Centrality