Abstract

Signed networks describe many real-world relations among users. Positive connections between two users or vertices generally mean good feelings between them, but negative connections mean bad feelings. A disruptor cycle in a graph is a cycle containing only one negative edge. A signed graph is known to be clusterable if and only if it does not contain a disruptor cycle. In this paper, we study the clusterability of a signed graph from the point of view of game theory introducing social disruption games on signed graphs. In these games, a coalition wins if the subgraph induced by the coalition is non-clusterable, i.e., it contains a disruptor cycle. Moreover, we study parameters and properties of players and compare them to other subclasses of simple games. In addition, we give some complexity results. In particular, we show that, unlike other subclasses of simple games, given a social disruption game, computing its length, deciding whether it is proper, or deciding whether it has a dummy player can be done in polynomial time. However, other problems, such as deciding whether the game is strong, or computing known power indices, remain computationally hard.