Attachment Centrality: Properties and Computation

Prelegent(ci)

Oskar Skibski

Afiliacja

Instytut Informatyki, UW

Termin

22 listopada 2018 10:15

Pokój

p. 4050

Seminarium

Seminarium „Ekonomia algorytmiczna”

---

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.

---