Vertex clustering of augmented graph streams

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

4 Citations (Scopus)
278 Downloads (Pure)


In this paper we propose a graph stream clustering algorithm with a unified similarity measure on both structural and attribute properties of vertices, with each attribute being treated as a vertex. Unlike others, our approach does not require an input parameter for the number of clusters, instead, it dynamically creates new sketch-based clusters and periodically merges existing similar clusters. Experiments on two publicly available datasets reveal the advantages of our approach in detecting vertex clusters in the graph stream. We provide a detailed investigation into how parameters affect the algorithm performance. We also provide a quantitative evaluation and comparison with a well-known offline community detection algorithm which shows that our streaming algorithm can achieve comparable or better average cluster purity.
Original languageEnglish
Title of host publicationProceedings of the 2015 SIAM International Conference on Data Mining
EditorsSuresh Venkatasubramanian, Jieping Ye
PublisherSociety for Industrial and Applied Mathematics
Number of pages9
ISBN (Electronic)9781611974010
ISBN (Print)9781510811522
Publication statusPublished - 26 Mar 2015
EventSIAM International Conference on Data Mining 2015, SDM 2015 - Vancouver, Canada
Duration: 30 Apr 20152 May 2015


ConferenceSIAM International Conference on Data Mining 2015, SDM 2015

Structured keywords

  • Jean Golding


Dive into the research topics of 'Vertex clustering of augmented graph streams'. Together they form a unique fingerprint.

Cite this