Efficient algorithms for game-theoretic betweenness centrality

Piotr Lech Szczepański , Tomasz P. Michalak , Talal Rahwan


Betweenness centrality measures the ability of different nodes to control the flow of information in a network. In this article, we extend the standard definition of betweenness centrality using Semivalues—a family of solution concepts from cooperative game theory that includes, among others, the Shapley value and the Banzhaf power index. Any Semivalue-based betweenness centrality measure (such as, for example, the Shapley value-based betweenness centrality measure) has the advantage of evaluating the importance of individual nodes by considering the roles they each play in different groups of nodes. Our key result is the development of a general polynomial-time algorithm to compute the Semivalue-based betweenness centrality measure, and an even faster algorithm to compute the Shapley value-based betweenness centrality measure, both for weighted and unweighted networks. Interestingly, for the unweighted case, our algorithm for computing the Shapley value-based centrality has the same complexity as the best known algorithm for computing the standard betweenness centrality due to Brandes[15]. We empirically evaluate our measures in a simulated scenario where nodes fail simultaneously. We show that, compared to the standard measure, the ranking obtained by our measures reflects more accurately the influence that different nodes have on the functionality of the network.
Author Piotr Lech Szczepański II
Piotr Lech Szczepański,,
- The Institute of Computer Science
, Tomasz P. Michalak
Tomasz P. Michalak,,
, Talal Rahwan
Talal Rahwan,,
Journal seriesArtificial Intelligence, ISSN 0004-3702
Issue year2016
Publication size in sheets1.2
Keywords in Englishbetweenness centrality, Shapley value, semivalue
URL http://www.sciencedirect.com/science/article/pii/S0004370215001666
projectGame theoretical approach to determining a crucial nodes in the networks. Project leader: Szczepański Piotr Lech, , Phone: +48 22 234-7148, application date 13-06-2013, start date 21-03-2014, end date 20-03-2017, II/2014/PRELUDIUM/1, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
Languageen angielski
AI_FINALL.pdf (file archived - login or check accessibility on faculty) AI_FINALL.pdf 1.28 MB
Score (nominal)40
ScoreMinisterial score = 40.0, 27-03-2017, ArticleFromJournal
Ministerial score (2013-2016) = 40.0, 27-03-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 4.797 (2) - 2016=5.786 (5)
Citation count*0
Share Share

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.