Finding strongly knit clusters in social networks

Social networks are ubiquitous. The discovery of closely knit clusters in these networks is of fundamental and practical interest. Existing clustering criteria are limited in that clusters typically do not overlap, all vertices are clustered, and/or external sparsity is ignored. We introduce a new criterion that overcomes these limitations by combining internal density with external sparsity in a natural way. This paper explores combinatorial properties of internally dense and externally sparse clusters. A simple algorithm is given for provably finding such clusters assuming a sufficiently large gap between internal density and external sparsity. Experimental results show that the algorithm is able to identify over 90% of the clusters in real graphs, assuming conditions on external sparsity.