TY - JOUR
T1 - Attachment centrality
T2 - Measure for connectivity in networks
AU - Skibski, Oskar
AU - Rahwan, Talal
AU - Michalak, Tomasz P.
AU - Yokoo, Makoto
N1 - Funding Information:
Oskar Skibski was supported by the Foundation for Polish Science within the Homing programme (Project title: “Centrality Measures: from Theory to Applications”). Oskar Skibski and Makoto Yokoo were supported by JSPS KAKENHI Grant ( 24220003 ). Tomasz Michalak was supported by the Polish National Science Centre grant 2015/19/D/ST6/03113 and by the European Research Council under Advanced Grant 291528 (“RACE”). Makoto Yokoo was supported by JSPS KAKENHI Grant ( 17H00761 ). The early version of this work was also supported by the Polish National Science Centre grant 2013/09/D/ST6/03920 .
Funding Information:
This article is an extended version of a paper originally presented at AAMAS-16 [56] with a number of new technical results. Specifically, all the results regarding the Attachment Delta are new ( Lemmas 4–5 and Theorem 7). Furthermore, most of the complexity results are new: all hardness results (Theorem 10, Lemmas 11–12, Theorem 13), as well as the complexity result for chordal graphs (Theorem 14). Finally, we significantly extended the related work section (Section 2), added several new examples and illustrations. Oskar Skibski was supported by the Foundation for Polish Science within the Homing programme (Project title: “Centrality Measures: from Theory to Applications”). Oskar Skibski and Makoto Yokoo were supported by JSPS KAKENHI Grant (24220003). Tomasz Michalak was supported by the Polish National Science Centre grant 2015/19/D/ST6/03113 and by the European Research Council under Advanced Grant 291528 (“RACE”). Makoto Yokoo was supported by JSPS KAKENHI Grant (17H00761). The early version of this work was also supported by the Polish National Science Centre grant 2013/09/D/ST6/03920.
Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2019/9
Y1 - 2019/9
N2 - Centrality indices aim to quantify the importance of nodes or edges in a network. Much interest has been recently raised by the body of work in which a node's connectivity is understood less as its contribution to the quality or speed of communication in the network and more as its role in enabling communication altogether. Consequently, a node is assessed based on whether or not the network (or part of it) becomes disconnected if this node is removed. While these new indices deliver promising insights, to date very little is known about their theoretical properties. To address this issue, we propose an axiomatic approach. Specifically, we prove that there exists a unique centrality index satisfying a number of desirable properties. This new index, which we call the Attachment centrality, is equivalent to the Myerson value of a certain graph-restricted game. Building upon our theoretical analysis we show that, while computing the Attachment centrality is #P-complete, it has certain computational properties that are more attractive than the Myerson value for an arbitrary game. In particular, it can be computed in chordal graphs in polynomial time.
AB - Centrality indices aim to quantify the importance of nodes or edges in a network. Much interest has been recently raised by the body of work in which a node's connectivity is understood less as its contribution to the quality or speed of communication in the network and more as its role in enabling communication altogether. Consequently, a node is assessed based on whether or not the network (or part of it) becomes disconnected if this node is removed. While these new indices deliver promising insights, to date very little is known about their theoretical properties. To address this issue, we propose an axiomatic approach. Specifically, we prove that there exists a unique centrality index satisfying a number of desirable properties. This new index, which we call the Attachment centrality, is equivalent to the Myerson value of a certain graph-restricted game. Building upon our theoretical analysis we show that, while computing the Attachment centrality is #P-complete, it has certain computational properties that are more attractive than the Myerson value for an arbitrary game. In particular, it can be computed in chordal graphs in polynomial time.
KW - Axiomatization
KW - Centrality measures
KW - Myerson value
KW - Networks
UR - http://www.scopus.com/inward/record.url?scp=85063961938&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85063961938&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2019.03.002
DO - 10.1016/j.artint.2019.03.002
M3 - Article
AN - SCOPUS:85063961938
SN - 0004-3702
VL - 274
SP - 151
EP - 179
JO - Artificial Intelligence
JF - Artificial Intelligence
ER -