Finding strongly knit clusters in social networks

Nina Mishra, Robert Schreiber, Isabelle Stanton, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

33 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)155-174
Number of pages20
JournalInternet Mathematics
Issue number1-2
StatePublished - Jan 1 2008

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Finding strongly knit clusters in social networks'. Together they form a unique fingerprint.

Cite this