## Main computational results (how fast can we compute game-theoretic centralities).

In general, game-theoretic solution concepts such as the Shapley value or the Banzhaf power index are computationally challenging; the number of required calculations is exponential in the number of players. Fortunately, this is not necessarily the case when the evaluation of coalitions (i.e., groups of nodes) depends 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|` |
`O(|V|` |
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|` |
`O(|V|` |
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|` |
`O(|V|` |
mimeo, University of Oxford |

Shapley value-based Betweenness Centrality | `O(|V||E|)` |
`O(|V|` |
Szczepański et al. (2012) |

Semivalue-based Closeness Centrality | `O(|V|` |
`O(|V|` |
Szczepański et al. (2015) |

Shapley value-based Closeness Centrality | `O(|V||E|)` |
`O(|V||E| + |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.
**