Cluster-preserving sampling from fully-dynamic streaming graphs

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

8 Citaten (Scopus)
136 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.

Originele taal-2Engels
Pagina's (van-tot)279-300
Aantal pagina's22
TijdschriftInformation Sciences
StatusGepubliceerd - 1 mei 2019


Duik in de onderzoeksthema's van 'Cluster-preserving sampling from fully-dynamic streaming graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit