Cluster-preserving sampling from fully-dynamic streaming graphs

Jianpeng Zhang (Corresponding author), Kaijie Zhu, Yulong Pei, George Fletcher, Mykola Pechenizkiy

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
84 Downloads (Pure)


Current sampling techniques on graphs (i.e., network-structured data) mainly study static graphs and suppose that the whole graph is available at all times. However, a surge of graphs are becoming too large-scale and/or fully-dynamic (i.e., nodes and edges are added or deleted arbitrarily) to be handled with small memory footprint. Moreover, the intrinsic property (i.e., clustering structure) has been ignored and is not preserved well when the sampling performs. To solve these issues, we propose a Cluster-preserving Partially Induced Edge Sampling (CPIES) algorithm that dynamically keep up-to-date samples in an online fashion and preserve the inherent clustering structure in streaming graphs. The experiments on various synthetic and real-world graphs demonstrated that the proposed CPIES algorithm is capable of preserving the inherent clustering structure while sampling from the fully-dynamic streaming graphs, and performs better than other competing algorithms in cluster-related properties.

Original languageEnglish
Pages (from-to)279-300
Number of pages22
JournalInformation Sciences
Publication statusPublished - 1 May 2019


  • Clustering structure
  • Fully-dynamic streaming graph
  • Graph sampling
  • Isolated nodes
  • Reservoir sampling


Dive into the research topics of 'Cluster-preserving sampling from fully-dynamic streaming graphs'. Together they form a unique fingerprint.

Cite this