Clustering-structure representative sampling from graph streams

Research output: Contribution to conferencePaperAcademic

95 Downloads (Pure)

Abstract

Most existing sampling algorithms on graphs (i.e., network-structured data) focus on sampling from memory-resident static graphs and assume the entire graphs are always available. However, the graphs encountered in modern applications are often too large and/or too dynamic to be processed with limited memory.
Furthermore, existing sampling techniques are inadequate for preserving the inherent clustering structure, which is an essential property of complex networks.
To tackle these problems, we propose a new sampling algorithm that dynamically maintains a representative sample and is capable of retaining clustering structure in graph streams at any time.
Performance of the proposed algorithm is evaluated through empirical experiments using real-world networks. The experimental results have shown that our proposed \textit{CPIES} algorithm can produce clustering-structure representative samples and outperforms current online sampling algorithms.
Original languageEnglish
Publication statusPublished - 2017

Fingerprint

Sampling
Data storage equipment
Complex networks
Experiments

Cite this

@conference{f3f4da3aebcd4a14b5d866318f23df8a,
title = "Clustering-structure representative sampling from graph streams",
abstract = "Most existing sampling algorithms on graphs (i.e., network-structured data) focus on sampling from memory-resident static graphs and assume the entire graphs are always available. However, the graphs encountered in modern applications are often too large and/or too dynamic to be processed with limited memory.Furthermore, existing sampling techniques are inadequate for preserving the inherent clustering structure, which is an essential property of complex networks.To tackle these problems, we propose a new sampling algorithm that dynamically maintains a representative sample and is capable of retaining clustering structure in graph streams at any time.Performance of the proposed algorithm is evaluated through empirical experiments using real-world networks. The experimental results have shown that our proposed \textit{CPIES} algorithm can produce clustering-structure representative samples and outperforms current online sampling algorithms.",
author = "J. Zhang and K. Zhu and Y. Pei and G.H.L. Fletcher and M. Pechenizkiy",
year = "2017",
language = "English",

}

Clustering-structure representative sampling from graph streams. / Zhang, J.; Zhu, K.; Pei, Y.; Fletcher, G.H.L.; Pechenizkiy, M.

2017.

Research output: Contribution to conferencePaperAcademic

TY - CONF

T1 - Clustering-structure representative sampling from graph streams

AU - Zhang, J.

AU - Zhu, K.

AU - Pei, Y.

AU - Fletcher, G.H.L.

AU - Pechenizkiy, M.

PY - 2017

Y1 - 2017

N2 - Most existing sampling algorithms on graphs (i.e., network-structured data) focus on sampling from memory-resident static graphs and assume the entire graphs are always available. However, the graphs encountered in modern applications are often too large and/or too dynamic to be processed with limited memory.Furthermore, existing sampling techniques are inadequate for preserving the inherent clustering structure, which is an essential property of complex networks.To tackle these problems, we propose a new sampling algorithm that dynamically maintains a representative sample and is capable of retaining clustering structure in graph streams at any time.Performance of the proposed algorithm is evaluated through empirical experiments using real-world networks. The experimental results have shown that our proposed \textit{CPIES} algorithm can produce clustering-structure representative samples and outperforms current online sampling algorithms.

AB - Most existing sampling algorithms on graphs (i.e., network-structured data) focus on sampling from memory-resident static graphs and assume the entire graphs are always available. However, the graphs encountered in modern applications are often too large and/or too dynamic to be processed with limited memory.Furthermore, existing sampling techniques are inadequate for preserving the inherent clustering structure, which is an essential property of complex networks.To tackle these problems, we propose a new sampling algorithm that dynamically maintains a representative sample and is capable of retaining clustering structure in graph streams at any time.Performance of the proposed algorithm is evaluated through empirical experiments using real-world networks. The experimental results have shown that our proposed \textit{CPIES} algorithm can produce clustering-structure representative samples and outperforms current online sampling algorithms.

M3 - Paper

ER -