TY - JOUR AU - SzczepaƄski, Piotr AU - Tarkowski, Mateusz AU - Michalak, Tomasz AU - Harrenstein, Paul AU - Wooldridge, Michael PY - 2015/02/10 Y2 - 2024/03/28 TI - Efficient Computation of Semivalues for Game-Theoretic Network Centrality JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - AAAI Technical Track: Applications DO - 10.1609/aaai.v29i1.9215 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9215 SP - AB - <p> Solution concepts from cooperative game theory, such as the Shapley value or the Banzhaf index, have recently been advocated as interesting extensions of standard measures of node centrality in networks. While this direction of research is promising, the computation of game-theoretic centrality can be challenging. In an attempt to address the computational issues of game-theoretic network centrality, we present a generic framework for constructing game-theoretic network centralities. We prove that all extensions that can be expressed in this framework are computable in polynomial time. Using our framework, we present the first game-theoretic extensions of weighted and normalized degree centralities, impact factor centrality,distance-scaled and normalized betweenness centrality,and closeness and normalized closeness centralities. </p> ER -