Community detection in social networks: Breaking the taboos

Current approaches to community detection in social networks usually neglect nodes, which we call taboo, whose neighborhood does not fit into main memory. In this paper, we model communities as cliques and present a distributed approach that is able to detect maximal cliques in social networks with taboo nodes. Our technique relies on a two-level decomposition algorithm. The first level aims at recursively identifying and isolating tractable portions of the network. The second level further decomposes the tractable portions into small blocks. This process is able to detect all maximal cliques provided that the sparsity of the network is bounded, as it happens in real-world social networks.