Main computational results. How fast we can compute game-theoretic centralities.
In general, game-theoretic solution concepts, such as the Shapley value or the Banzhaf power index, are computationally challenging. Typically, they require computations which are exponential in the number of players. Fortunately, this is not always the case if the values of coalitions depend on the topology of the network. In particular, for game-theoretic centrality, various positive computational results have been found. We list them below:
Centrality Name | Unweighted graphs | Weigthed graphs | Paper (PDF) |
---|---|---|---|
Semivalue-based Degree Centrality | O(|V|3) |
O(|V|3) |
Szczepański et al. (2015) |
Shapley value-based Degree Centrality | O(|V|+|E|) |
O(|V|+|E|) |
Michalak et al. (2013) |
Coalitional Semivalue-based Degree Centrality | O(|V|4) |
O(|V|4) |
Szczepański et al. (2014) |
Owen value-based Degree Centrality | O(|V|+|E|) |
O(|V|+|E|) |
Szczepański et al. (2014) |
Semivalue-based Betweenness Centrality | O(|V|2|E|) |
O(|V|3|E| + |V|3log|V|) |
mimeo, University of Oxford |
Shapley value-based Betweenness Centrality | O(|V||E|) |
O(|V|2|E| + |V|2log|V|) |
Szczepański et al. (2012) |
Semivalue-based Closeness Centrality | O(|V|5) |
O(|V|5) |
Szczepański et al. (2015) |
Shapley value-based Closeness Centrality | O(|V||E|) |
O(|V||E| + |V|2log|V|) |
Michalak et al. (2013) |
Click here to compute game-theoretic centralities and compare them to other centrality measures using our On-line Computational Toolbox.