Disguising centrality

Speaker(s)

Marcin Waniek

Affiliation

Instytut Informatyki, Wydział MIM UW

Date

Oct. 22, 2015, 12:15 p.m.

Room

room 3320

Seminar

Seminar Games, Mechanisms, and Social Networks

---

Various centrality measures have been developed to identify key members of a social network. We study how such members can escape detection without giving away much of their influence on the network.

In our work, we focus on the best-known centrality measures and influence models. In particular, we show that finding an optimal way to lower one's centrality is a computationally demanding task. The same holds for the problem of rebuilding one's influence. Thus finding the best solution is next to impossible for most networks.

However, we propose a simple heuristic solution, that can be used by any network member, without any expertise in algorithm design. It allows member of the network to lower values of all three most important centrality measures, at the same time maintaining her influence on the network. It proves effective in simulations for different types of real social and covert networks, as well as those artificially generated.

We also propose an algorithm for building a network from scratch. In such network the founding member is low in rankings of all three centrality measures, but at the same time she highest influence score. Building process is easy and does not demand to store much bookkeeping information.

---