Attachment Centrality: Properties and Computation

Speaker(s)

Oskar Skibski

Affiliation

Instytut Informatyki, UW

Date

Nov. 22, 2018, 10:15 a.m.

Room

room 4050

Seminar

Seminar Games, Mechanisms, and Social Networks

---

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. In this presentation, I will discuss one such index, called the Attachment centrality, which 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.

---