Game-Theoretic Network Centrality

Publications

Check out our latest publications.

View details »

Team

Read about us.

View details »

Complexity.

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.

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\|³)`	`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\|²\|E\|)`	`O(\|V\|³\|E\| + \|V\|³log\|V\|)`	mimeo, University of Oxford
Shapley value-based Betweenness Centrality	`O(\|V\|\|E\|)`	`O(\|V\|²\|E\| + \|V\|²log\|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\|²log\|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.

Social Capital.

The Owen value (Owen 1977) is an extension of the Shapley value to situations in which the players have a priori agreed to partition themselves into unions. The players in any union strictly collaborate in the game. Similarly to the Shapley value, the Owen value quanti es the role of an individual player, but now taking into account the role of the a priori union that this player belongs to. For instance, a player may be weak by himself/herself, but if he/she belongs to an important union, then his/her role will grow stronger according to the Owen value.

Recently, Szczepanski et al. (2014) proposed the game-theoretic extension of degree centrality based on the Owen value. Interestingly, this centrality has a nontrivial interpretation as a measure of social capital. In particular, social capital of an individual is increased (decreased) if he/she belongs to a community that is rich (poor) in terms of social capital. For instance, if a lawyer is not particularly well connected, his/her social capital is still increased by the fact that he/she belongs to the well-connected community of lawyers. Thus this is the first social capital measure that evaluates individual actors both in the context of their relationships with the external world as well as in the context of the external role of the community they belong to.

As a sample application of this measure, Szczepanski et al. (2014) studied a network consisting of articles connected by citation relations. Here, all publications of a particular journal, or the series of proceedings of a particular conference, can be viewed as a naturally defined scientific community. The aim of Szczepanski et al. was to study how the importance of a given scientific community influences the role of a single article in the citation network. The real-life network used for simulations is a citation network that consists of 2,084,055 publications and 2,244,018 citation relationships. All publications are categorized into 22,954 unique communities representing journals, conference proceedings or single book titles. In what follows, out of all 2,084,055 nodes, Figure 1 focuses on the top 11 ones according to the degree centrality. More specifically, Figure 1(a) illustrates the relative power of the communities to which these nodes belong (the bigger the circle, the more powerful is the community). As can be seen, nodes ranked 5, 6 and 8 belong to signicantly less powerful communities than nodes 1, 2, 3, 4, 7, 9, 10 and 11. Figure 1(b) shows how the ranking of those 11 nodes changes according to the Shapley value-based and Owen value-based centralities. While for most nodes the perturbations are not so intensive, we observe significant downgrade of the position of nodes 5, 6 and 8 in the Owen-based ranking, which demonstrates how it is capable of recognizing the fact that these three nodes belong to weaker communities.

As for computational issues, Szczepanski et al. (2014) showed that the Owen value-based degree centrality can be computed in O(|V|+|E|) time, which makes this concept practical even for large real-life networks.

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.

Brain networks.

Clinical observations of the brain functions are nowadays usually represented as a network consisting of brain regions and structures (e.g., neuronal structures) and their interconnections. For instance, brain networks are represented by directed graphs whose nodes are neuronal structures (nuclei or cortical regions) and whose set of directed arcs represents the set of directed connections (projections) between these structures. In Kötter et al. (2007), coalitional games and the Shapley value have been used to measure the importance of individual brain structures to the connectivity of the graph derived from the global properties of the networks made up by neurons and their interconnections. The worth of each nonempty coalition of neuronal structures in the game is defined as the number of connected components in the brain network and the Shapley value of this game is used to understand the functional consequences of a lesion of the different areas of the brain. Applications of the Shapley value to the analysis of real brain networks representing visual cortical areas and prefrontal cortical areas of macaque, respectively, are presented and discussed in Kötter et al. (2007).
Genes networks.

Gene networks (e.g., representing protein–protein interactions, co-expression of genes, etc.) are increasingly used to explore the system-level functionality of proteins and genes. Recently, a new method based on coalitional games has been introduced in Moretti et al. (2010) to evaluate the centrality in gene networks, keeping into account the interactions among genes. The basic idea of the approach in Moretti et al. (2010) is based on the analysis of two coalitional games: an association game, defined as a coalitional game over a set of genes where the worth of each coalition S measures the “interaction” between the genes in S and a given set of an a priori family of key-genes, and a graph-restricted game, where gene interaction is restricted to the connections provided by a gene network. The difference of Shapley values computed on the two aforementioned coalitional games is used in Moretti et al. (2010) as a gene centrality measure on a real gene network derived from gene expression data.

The above figure shows the Interaction network between genes (nodes) from blood cells of children from Teplice (TP) region in the Czech Republic, a mining district characterized by high levels of airborne pollutants including carcinogens. Interactions between gene's pairs are represented by edges. Thicker edges show the shortest paths among the most associated genes. Source: Moretti et al. (2010).
Metabolic networks.

Metabolic networks represent complex biological systems composed of biochemical reactions through which metabolites are transformed. Flux balance analysis (FBA) of metabolic networks has been used in Sajitz-Hermstein and Zoran (2012) to introduce FBA-games, which are coalitional games where the set of players is the set of reactions forming the metabolic network and a coalition S corresponds to the subnetwork induced by the reactions included in S. The value given to coalition S by the characteristic function of an FBA-game is then the optimal value of the objective function determined by FBA on the corresponding subnetwork on S. The Shapley value considering only the restricted set of subnetworks capable of performing the investigated biochemical function has been used in Sajitz-Hermstein and Zoran (2012) as a functional centrality measure to quantifies the contributions of individual reactions to the biochemical conversion capabilities. Applications to real metabolic networks, like a model of glycolysis and pentose phosphate pathway, are presented in [Sajitz-Hermstein and Zoran (2012), Sajitz-Hermstein and Zoran (2013)].
Chemosensory networks.

The Multi-perturbation Shapley Value Analysis (MSA) (Keinan et al., 2004), is a method for deducing causal function localization from multiple perturbations data, where the Shapley value is used to quantify the importance of each of the elements of a complex system in carrying out different functions. Following this approach, the value of each coalition of system's elements is a measure of the biological system’s performance for a certain function (e.g., the ability of the system to survive the UV irradiation). The authors in Kaufman et al. (2005) used the MSA method to analyze function localization in the nervous system, based on laser ablation experiments of the chemosensory neurons in C. elegans.

Applications of game theoretic centrality to Information Communications Technology.

Computer networks.

In order to reduce their carbon footprint, emerging ICTs are embedded with energy aware protocols and energy saving techniques. An energy-aware routing approach is studied in [Bianzino et al. (2011), Bianzino et al. (2012)] with the objective to summarize the contribution of devices using power indices (and in particular the Shapley value) of particular coalitional games defined over the set of the elements of a backbone network. Such coalitional games incorporate the information about the network structure (e.g., the connectivity of sub-networks), the amount of traffic that the devices are routing and the network robustness (i.e., possible failure scenarios). The ranking provided by the Shapley value of such games has been used to drive the selection of less critical devices that should be switched off first in order to reduce the energy consumption and keeping into account the expected global performance of the network. The ranking provided by the Shapley value has been compared on realistic network scenarios with the rankings given by methods based on classical centrality notions. This comparison shows that the Shapley value ranking may provide high energy savings with a smaller impact on the expected QoS (Quality of Service) levels on the network.

In the figure above: Left: Graphical view of the criticality of links according to the Shapley index for the reference network scenario during the peak hour traffic: the thicker a link, the higher its importance. Right: Achievable energy saving for the referece network scenario, for different link rankings. Source: Bianzino et al. (2012)

Publications. Where to read about game-theoretic centrality

Computer science literature:

{{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 ]