Shapley value
A class of game-theoretic network centrality measures based on the
Shapley value
from the cooperative game theory is discussed in [2]. The Shapley value \(SV(i)\) of node \(i\) is defined as the average marginal contribution of \(i\) to all possible coalitions of nodes \(C \subseteq \mathcal{N} \setminus \{i\}\):
\begin{equation*}
SV(i) = \sum_{C \subseteq \mathcal{N} \setminus \{i\}} \frac{(|C|-1)!(|\mathcal{N}|-|C|)!}{|\mathcal{N}|!} \left[ v(C \cup \{ i \}) - v(C) \right],
\end{equation*}
where \(v\) is a
characteristic function
that assigns to every coalition \(C\) a real number representing the value or performance of the coalition [3].
Michalak et al. [2] proposed efficient linear-time algorithms to compute Shapley value-based centralities for specific definitions of the characteristic function \(v\):
- Game 1: \(v(C)\) is the number of nodes reachable from the coalition \(C\) in at most one hop. In that case, the Shapley value \(SV_1(i)\) of node \(i\) reduces to \begin{equation*} SV_1(i) = \frac{1}{1+d_i} + \sum_{j \in \mathcal{N}(i)} \frac{1}{1+d_j}, \end{equation*} where \(d_i\) is the degree of node \(i\).
- Game 2: \(v(C)\) is the number of nodes that are either in \(C\) or adjacent to at least \(k\) neighbors in \(C\). In that case, the Shapley value \(SV_2(i)\) of node \(i\) reduces to \begin{equation*} SV_2(i) = \min \left(1, \frac{k}{1+d_i}\right) + \sum_{j \in \mathcal{N}(i)} \max \left(0, \frac{d_j - k + 1}{d_j(1+d_j)}\right). \end{equation*} For \(k = 1\), this game is equivalent to Game 1.
- Game 3: \(v(C)\) is the number of nodes that are at most \(d_{\max}\) hops away from \(C\). In that case, the Shapley value \(SV_3(i)\) of node \(i\) reduces to \begin{equation*} SV_3(i) = \frac{1}{1+|s_i(d_{\max})|} + \sum_{j \in s_i(d_{\max})} \frac{1}{1+|s_j(d_{\max})|}, \end{equation*} where \(s_i(d_{\max})\) denotes the set of nodes within distance \(d_{\max}\) from node \(i\).