Clustering social networks

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

99 Scopus citations


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. An algorithm is given for provably finding the clusters, provided there is a sufficiently large gap between internal density and external sparsity. Experiments on real social networks illustrate the effectiveness of the algorithm.

Original languageEnglish (US)
Title of host publicationAlgorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540770039
StatePublished - 2007
Event5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007 - San Diego, CA, United States
Duration: Dec 11 2007Dec 12 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4863 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Clustering social networks'. Together they form a unique fingerprint.

Cite this