Attachment Centrality: Properties and Computation

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.