Clustering-structure representative sampling from graph streams

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
1 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 CPIES algorithm can produce clustering-structure representative samples and outperforms current online sampling algorithms.

Original languageEnglish
Title of host publicationComplex Networks and Their Applications VI
Subtitle of host publicationProceedings of Complex Networks 2017 (The 6th International Conference on Complex Networks and Their Applications)
EditorsC. Cherifi, H. Cherifi, M. Karsai, M. Musulesi
Place of PublicationDordrecht
PublisherSpringer
Pages265-277
Number of pages13
ISBN (Electronic)978-3-319-72150-7
ISBN (Print)978-3-319-72149-1
DOIs
Publication statusPublished - 1 Jan 2018
Event6th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS 2017) - Lyon, France
Duration: 29 Nov 20171 Dec 2017
Conference number: 6

Publication series

NameStudies in Computational Intelligence
Volume689
ISSN (Print)1860-949X

Conference

Conference6th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS 2017)
Abbreviated titleCOMPLEX NETWORKS 2017
CountryFrance
CityLyon
Period29/11/171/12/17

Fingerprint Dive into the research topics of 'Clustering-structure representative sampling from graph streams'. Together they form a unique fingerprint.

  • Cite this

    Zhang, J., Zhu, K., Pei, Y., Fletcher, G., & Pechenizkiy, M. (2018). Clustering-structure representative sampling from graph streams. In C. Cherifi, H. Cherifi, M. Karsai, & M. Musulesi (Eds.), Complex Networks and Their Applications VI : Proceedings of Complex Networks 2017 (The 6th International Conference on Complex Networks and Their Applications) (pp. 265-277). (Studies in Computational Intelligence; Vol. 689). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-72150-7_22