📂Graph Theory

Stress Centrality in Network Theory

Definition ¹

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

Explanation

$\sigma_{st} (v)$

If you read carefully the definition of $\sigma_{st}$, it is not the shortest distance $d(s,t) = d(t,s)$ between $s,t$, but the number of paths that make it the shortest distance, for all $v \in V$, $\sigma_{vv} = 1$, and with respect to the graph’s 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

Stress Centrality is one of the oldest centralities introduced by Shimbel in 1953, and the equation $$ C_{S} (v) = \sum_{s \ne v \ne t \in V} \sigma_{st} (v) $$ can be seen as how much a node $v \in V$ creates the shortest paths by intermediating between all pairs of nodes $s, t \in V$. In many phenomena in nature… for example, as a water droplet minimizes surface area and the action in motion is minimized, there is often a great interest in the shortest or fastest path to connect two nodes, and points that frequently belong to the shortest path would bear a lot of Stress. From this intuitive standpoint, it makes quite sense to call $C_{S} (v)$ Stress Centrality.

Later, Betweenness Centrality was introduced as a measure that complements Stress Centrality.

See Also

Various Centrality in Networks

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