Vertex Clustering of Augmented Graph Streams

Ryan McConville, Weiru Liu, Paul Miller

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

4 Citations (Scopus)
260 Downloads (Pure)


In this paper we propose a graph stream clustering algorithm with a unied 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
PublisherSociety for Industrial and Applied Mathematics
Number of pages9
Publication statusPublished - 2015
Event2015 SIAM International Conference on Data Mining - Vancouver, Canada
Duration: 30 Apr 201502 May 2015


Conference2015 SIAM International Conference on Data Mining


Dive into the research topics of 'Vertex Clustering of Augmented Graph Streams'. Together they form a unique fingerprint.

Cite this