  Detecting and characterizing dense subgraphs (tight communities) in social
and information networks is an important exploratory tool in social network
analysis. Several approaches have been proposed that either (i) partition the
whole network into clusters, even in low density region, or (ii) are aimed at
finding a single densest community (and need to be iterated to find the next
one). As social networks grow larger both approaches (i) and (ii) result in
algorithms too slow to be practical, in particular when speed in analyzing the
data is required. In this paper we propose an approach that aims at balancing
efficiency of computation and expressiveness and manageability of the output
community representation. We define the notion of a partial dense cover (PDC)
of a graph. Intuitively a PDC of a graph is a collection of sets of nodes that
(a) each set forms a disjoint dense induced subgraphs and (b) its removal
leaves the residual graph without dense regions. Exact computation of PDC is an
NP-complete problem, thus, we propose an efficient heuristic algorithms for
computing a PDC which we christen Core and Peel. Moreover we propose a novel
benchmarking technique that allows us to evaluate algorithms for computing PDC
using the classical IR concepts of precision and recall even without a golden
standard. Tests on 25 social and technological networks from the Stanford Large
Network Dataset Collection confirm that Core and Peel is efficient and attains
very high precison and recall.

Social and Information Networks;Data Structures and Algorithms;Physics and Society