net.jpg Game-Theoretic Network Centrality
Generic placeholder image

Publications

Check out our latest publications.

View details »

Generic placeholder image

Team

Find out more about us.

View details »

Generic placeholder image

Complexity

Check our computational results.

View details »


Game theoretic-centrality at a glance (a 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 nodes involved.

500x500

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 No. 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). 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 certain 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 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-time results are known for the Shapley value-based betweenness centrality (Szczepański et al., 2012).

Back to top


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|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:

{{pubs[0].year}}

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

Working Papers and Submissions under Review:

{{pub.cite}}:
{{pub.author}}, {{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

tomasz.michalak#@#cs.ox.ac.uk
University of Oxford
University of Warsaw

algorithmic game theory multi-agent systems

Stefano Moretti France

CNRS

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

PhD Students. Our young scientists.

Szymon Matejczyk Poland

PhD student at Polish Academy of Sciences

big data social networks

Piotr L. Szczepański Poland

PhD student at Warsaw University of Technolog

coalitional game theory soical networks

Mateusz Tarkowski UK

PhD student at University of Oxford

coalitional game theory graph-restricted games

Back to top


To contact us please send an email to Tomasz Michalak tomasz.michalak#@#cs.ox.ac.uk .


500x500