Finding All Maximal Cliques in Very Large Social Networks
The detection of communities in social networks is a challenging task. A rigorous way to model communities considers maximal cliques, that is, maximal subgraphs in which each pair of nodes is connected by an edge. State of the art strategies for nding maximal cliques in very large networks decompose the network in blocks and then perform a distributed computation. These approaches exhibit a trade o between eciency and completeness: decreasing the size of the blocks has been shown to improve eciency but some cliques may remain undetected since high degree nodes, also called hubs, may not t with all their neighborhood into a small block. In this paper, we present a distributed approach that, by suitably handling hub nodes, is able to detect maximal cliques in large networks meeting both completeness and eciency. The approach relies on a two level decomposition process. The rst level aims at recursively identifying and isolating tractable portions of the network. The second level further decomposes the tractable portions into small blocks. We demonstrate that this process is able to correctly detect all maximal cliques, provided that the sparsity of the network is bounded, as it is the case of real world social networks. An extensive campaign of experiments conrms the
EDBT