Breaking Bad: Finding Triangle-Breaking Points in Large Networks

Many online social networks (OSN), such as Facebook, Twitter can quickly become popular, but many such as Friendster or MySpace can also suffer catastrophic decline in traffics and users. Understanding the capability of OSNs to withstand perturbation and changes, termed social resilience, is a matter of the uttermost importance. In this paper, we investigate the resilience of OSNs under nodes and links removals, where the robustness of the network is measured through the number of triangles, a fundamental property in many networks. Specifically, we strive to discover critical nodes and links whose failures will critically break most triangles in the network, changing the network's organization and (possibly) leading to the unpredictable dissolving of the network. We formulate this vulnerability analysis as optimization problems, and provide proofs of their intractability. Given the intractability of the problem, we also investigate approximation algorithms and their efficient implementations.