ABSTRACT

Social networks are ubiquitous. The discovery of close-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 work develops both combinatorial results regarding how these new clusters interact and three algorithms for provably finding the clusters. Experiments on real social networks illustrate the effectiveness of the algorithms. To demonstrate the practical utility of these clusters we describe a group recommendation algorithm that uses our definitions. Experiments on real social networks indicate that, with just a few group predictions, we succeed in recommending to a substantial fraction of the population. Other Recent and Upcoming Colloquia