TY - JOUR

T1 - Efficient algorithms for game-theoretic betweenness centrality

AU - Szczepański, Piotr L.

AU - Michalak, Tomasz P.

AU - Rahwan, Talal

N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.

PY - 2016/2/1

Y1 - 2016/2/1

N2 - 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.

AB - 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.

KW - Betweenness centrality

KW - Semivalue

KW - Shapley value

UR - http://www.scopus.com/inward/record.url?scp=84947284999&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947284999&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2015.11.001

DO - 10.1016/j.artint.2015.11.001

M3 - Article

AN - SCOPUS:84947284999

SN - 0004-3702

VL - 231

SP - 39

EP - 63

JO - Artificial Intelligence

JF - Artificial Intelligence

ER -