Generic placeholder image


Check out our latest publications.

View details »

Generic placeholder image


Read about us.

View details »

Generic placeholder image


Check our computational results.

View details »

Tomasz MichalakA new class of network analysis tools.

The key idea behind game-theoretic centrality measures is to treat nodes as players in a cooperative game, where the value of each coalition of nodes is determined by certain graph-theoretic properties. The key advantage of this approach is that nodes are ranked not only according to their individual roles in the network but also according to how they contribute to the role played by all possible subsets (or groups) of nodes. This is important in various applications in which a group's performance cannot be simply described as the sum of the individual performances of the involved nodes.


Consider, for instance, an epidemiology application, where the aim is to contain the spread of a disease. If we ask the question of whether the vaccination of any individual node is sufficient to stop the spread of the disease then the answer is most probably negative. A much more likely way to contain the disease is to simultaneously vaccinate a (possibly relatively small) group of nodes. Based on this, to quantify the importance of a node, we need to consider the potential gain of vaccinating it as part of a bigger group, rather than just considering the potential gain of vaccinating it alone.

Such analysis of groups of nodes in the network directly corresponds to coalitional game theory, where the performance of players is studied in ``coalitions'' (i.e., subsets of players); this way the value added from cooperation becomes fully exposed. Importantly, by imposing the combinatorial structure of a coalitional game over a network, it is possible to analyse the performance of nodes using a plethora of game-theoretic solution concepts developed over decades to analyse the performance of players. One such well-known game-theoretic solution concept is the Shapley value which received ample attention in the literature due to its desirable properties. Another one is the Banzhaf index of power.

A particular advantage of such a game-theoretic perspective of network analysis is that it exposes the possibility of extending a wide variety of centrality measures. This is because a cooperative game typically places no assumptions or restrictions on how the groups are evaluated. This evaluation can be tailored to best fit the centrality measure at hand. For instance, a group of nodes can be evaluated based on the average degree therein, or based on its diameter, or its closeness to other nodes, etc.

A potential downside of game-theoretic network centralities is that they are based on solution concepts that are themselves hard to compute. For instance, given a coalitional game defined over a network of O(|V|) nodes, a straight-forward computation of the Shapley value requires considering all possible O(2|V|) coalitions (i.e., groups) of nodes. This is clearly prohibitive for networks with hundreds, or even tens, of nodes. Indeed, it has been shown that in some cases the exponential number of computations cannot be avoided, i.e., it is impossible to compute particular game-theoretic network centralities in time polynomial in the size of the network. This negative result holds, for instance, for game-theoretic network centralities in the spirit of Myerson's (1977) graph-restricted games.

Fortunately, various positive computational results have also been found. In particular, Michalak et al. (2013) analysed various Shapley value-based extensions of degree and closeness centrality and showed that it is possible to leverage the fact that the values of groups of nodes depend on the topology of the network. As a result, they showed that some game-theoretic centrality measures can be computable in polynomial time. Similarly, polynomial results are known for the Shapley value-based betweenness centrality.

Back to top

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.

Applications. Domains for which game-theoretic centralities were advocated.

Applications of game theoretic centrality to social networks analysis.

Applications of game theoretic centrality to biology.

In biology and medical research, a variety of high-throughput experimental technologies are used to collect huge amount of data about interacting biological features. In many cases, the interactions among these features can be represented as a network, whose analysis involves the definition of appropriate measures of relevance for nodes and for links. For this purpose, several centrality measures based on coalitional game theory have been successfully applied to different kinds of biological networks.

Applications of game theoretic centrality to Information Communications Technology.

Back to top

Publications. Where to read about game-theoretic centrality

Computer science literature:


{{}}, {{pub.title}}, {{pub.venue}} {{pub.special}}, {{pub.volume}} ({{pub.number}}), p. {{pub.pages}}, ({{pub.year}}) bib ]

Working Papers and Submissions under Review:

{{}}, {{pub.title}}, {{pub.venue}} {{pub.special}}, {{pub.volume}} ({{pub.number}}), p. {{pub.pages}}, ({{pub.year}}) bib ]

Other contributions (the list is, by far, not exhaustive and will be updated):

[1] Julia Belau. Consequences of connection failure - centrality and the importance for cohesion. In Public Choice Society, 2014. [ bib ]
[2] R. Lindelauf, H. Hamers, and B. Husslage. Cooperative game theoretic centrality analysis of terrorist networks: The cases of jemaah islamiyah and al qaeda. European Journal of Operational Research, 229(1):230-238, 2013. [ bib ]
[3] Rafael Amer, José Miguel Giménez, and Antonio Magaña. Accessibility measures to nodes of directed graphs using solutions for generalized cooperative games. Mathematical Methods of Operations Research, 75(1):105-134, 2012. [ bib | DOI | http ]
[4] M. del Pozo, C. Manuel, E. González-Arangüena, and G. Owen. Centrality in directed social networks. a game theoretic approach. Social Networks, 33(3):191 - 200, 2011. [ bib ]
[5] Jeong-Yoo Kim and Jun Tackseung. Connectivity and allocation rule in a directed network. The B.E. Journal of Theoretical Economics, 8(1):1-21, 2008. [ bib | http ]
[6] Rafael Amer, José Miguel Giménez, and Antonio Magaña. Accessibility in oriented networks. European Journal of Operational Research, 180(2):700 - 712, 2007. [ bib | DOI | http ]
[7] Rafael Amer and José Miguel Giménez. A connectivity game for graphs. Math. Meth. of OR, 60(3):453-470, 2004. [ bib ]
[8] B. Grofman and Guillermo Owen. A game-theoretic approach to measuring centrality in social networks. Social Networks, 4:213-224, 1982. [ bib ]

Back to top

People involved in research on game-theoretic centrality. Who are we?

Edith Elkind UK

University of Oxford

algorithmic game theory computational social choice

Tomasz P. Michalak UK, Poland
University of Warsaw

algorithmic game theory multi-agent systems

Stefano Moretti France


game theory operations research decision theory

Talal Rahwan UAE

Masdar Institute

multi-agent systems cooperative game theory knowledge representation

Oskar Skibski Japan

Kyushu University

coalitional game theory graph-restricted games

Michael Wooldridge UK

University of Oxford

multi-agent systems computational complexity game theory

Mateusz Tarkowski UK

University of Oxford

coalitional game theory graph-restricted games

Piotr L. Szczepański Poland

Warsaw University of Technology

coalitional game theory soical networks

Back to top

To contact us please send an email to Tomasz Michalak .

This website was supported by the Polish National Science Center grant DEC-2013/09/D/ST6/03920