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

1 Citation (Scopus)
2 Downloads (Pure)

Abstract

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
Volume482
DOIs
Publication statusPublished - 1 May 2019

    Fingerprint

Keywords

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

Cite this