Clustering social networks

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

doi:10.1007/978-3-540-77004-6_5

Clustering social networks

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

101 Scopus citations

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. 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 language	English (US)
Title of host publication	Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings
Publisher	Springer Verlag
Pages	56-67
Number of pages	12
ISBN (Print)	9783540770039
DOIs	https://doi.org/10.1007/978-3-540-77004-6_5
State	Published - 2007
Event	5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007 - San Diego, CA, United States Duration: Dec 11 2007 → Dec 12 2007

Publication series

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

Other

Other	5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Country/Territory	United States
City	San Diego, CA
Period	12/11/07 → 12/12/07

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-77004-6_5

Cite this

Mishra, N., Schreiber, R., Stanton, I., & Tarjan, R. E. (2007). Clustering social networks. In Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings (pp. 56-67). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4863 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-77004-6_5

@inproceedings{8ef106491c0041e08a84851f20304913,

title = "Clustering social networks",

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. 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.",

author = "Nina Mishra and Robert Schreiber and Isabelle Stanton and Tarjan, {Robert E.}",

year = "2007",

doi = "10.1007/978-3-540-77004-6_5",

language = "English (US)",

isbn = "9783540770039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "56--67",

booktitle = "Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings",

address = "Germany",

note = "5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007 ; Conference date: 11-12-2007 Through 12-12-2007",

}

Mishra, N, Schreiber, R, Stanton, I & Tarjan, RE 2007, Clustering social networks. in Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4863 LNCS, Springer Verlag, pp. 56-67, 5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007, San Diego, CA, United States, 12/11/07. https://doi.org/10.1007/978-3-540-77004-6_5

Clustering social networks. / Mishra, Nina; Schreiber, Robert; Stanton, Isabelle et al.
Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings. Springer Verlag, 2007. p. 56-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4863 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Clustering social networks

AU - Mishra, Nina

AU - Schreiber, Robert

AU - Stanton, Isabelle

AU - Tarjan, Robert E.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38149014810&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149014810&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-77004-6_5

DO - 10.1007/978-3-540-77004-6_5

M3 - Conference contribution

AN - SCOPUS:38149014810

SN - 9783540770039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 56

EP - 67

BT - Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings

PB - Springer Verlag

T2 - 5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007

Y2 - 11 December 2007 through 12 December 2007

ER -

Mishra N, Schreiber R, Stanton I, Tarjan RE. Clustering social networks. In Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings. Springer Verlag. 2007. p. 56-67. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-77004-6_5

Clustering social networks

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this