Analysis of Dense Partial Coverings of Large Social and information Networks

Characterizing and detecting dense subgraphs (tight communities) of social graphs 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 dense community (an need to be iterated to find the next one). As social networks grow larger both apporaches (i) and (ii) result in algorithms too slow to be practical, in particular when on-the-fly results are needed. In this paper we propose an alternative approach that aims at balancing efficiency of computation and expressiveness/manageability of the output community representation. We define the notion of a partial dense cover (PDC) of a graph. Intutively a PDC of a graph is that set of nodes that (a) forma set of disjoint dense induced subgraphs and (b) whose removal leaves the residual graph without dense regions. Exact computation of PDC is an NP-complete problem. Thus, we propose efficient heuristic algorithms for computing them. Precision and recall of the approach is measured by embedding dense subgraphs in large social networks and by measuring the ability of our method in finding them blindly