Efficient algorithms for game-theoretic betweenness centrality
Piotr Lech Szczepański , Tomasz P. Michalak , Talal Rahwan
AbstractBetweenness 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. 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.
|Journal series||Artificial Intelligence, ISSN 0004-3702|
|Publication size in sheets||1.2|
|Keywords in English||betweenness centrality, Shapley value, semivalue|
|ASJC Classification||; ;|
|Project||Game theoretical approach to determining a crucial nodes in the networks. Project leader: Szczepański Piotr Lech,
, application date 13-06-2013, start date 21-03-2014, end date 20-03-2017, II/2014/PRELUDIUM/1, Completed
|Score|| = 40.0, 04-02-2020, ArticleFromJournal|
= 40.0, 04-02-2020, ArticleFromJournal
|Publication indicators||: 2016 = 3.849; : 2016 = 4.797 (2) - 2016=5.786 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.