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 language | English |
---|---|
Title of host publication | Complex Networks and Their Applications VI |
Subtitle of host publication | Proceedings of Complex Networks 2017 (The 6th International Conference on Complex Networks and Their Applications) |
Editors | C. Cherifi, H. Cherifi, M. Karsai, M. Musulesi |
Place of Publication | Dordrecht |
Publisher | Springer |
Pages | 265-277 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-319-72150-7 |
ISBN (Print) | 978-3-319-72149-1 |
DOIs | |
Publication status | Published - 1 Jan 2018 |
Event | 6th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS 2017) - Lyon, France Duration: 29 Nov 2017 → 1 Dec 2017 Conference number: 6 |
Publication series
Name | Studies in Computational Intelligence |
---|---|
Volume | 689 |
ISSN (Print) | 1860-949X |
Conference
Conference | 6th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS 2017) |
---|---|
Abbreviated title | COMPLEX NETWORKS 2017 |
Country/Territory | France |
City | Lyon |
Period | 29/11/17 → 1/12/17 |
Funding
Acknowledgements. This research of Zhang is supported by the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No. 61521003) and the National key Research and Development Program of China (Grant No. 2016YFB0800101). The research of Pei is supported by the Netherlands Organisation for Scientific Research (NWO).