Privacy Policy Disclaimer
  Advanced SearchBrowse




Book Chapter

Network Sparsification via Degree- and Subgraph-based Edge Sampling


Su,  Zhen
Potsdam Institute for Climate Impact Research;


Kurths,  Jürgen
Potsdam Institute for Climate Impact Research;

Meyerhenke,  Henning
External Organizations;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PIKpublic
Supplementary Material (public)
There is no public supplementary material available

Su, Z., Kurths, J., Meyerhenke, H. (2023): Network Sparsification via Degree- and Subgraph-based Edge Sampling. - In: An, J., Charalampo, C., Magdy, W. (Eds.), Proceedings of the 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2022, Piscataway, NJ : Institute of Electrical and Electronics Engineers, 9-16.

Cite as: https://publications.pik-potsdam.de/pubman/item/item_28712
Network (or graph) sparsification compresses a graph by removing inessential edges. By reducing the data volume, it accelerates or even facilitates many downstream analyses. Still, the accuracy of many sparsification methods, with filtering-based edge sampling being the most typical one, heavily relies on an appropriate definition of edge importance. Instead, we propose a different perspective with a generalized local-property-based sampling method, which preserves (scaled) local node characteristics. Apart from degrees, these local node characteristics we use are the expected (scaled) number of wedges and triangles a node belongs to. Through such a preservation, main complex structural properties are preserved implicitly. We adapt a game-theoretic framework from uncertain graph sampling by including a threshold for faster convergence (at least 4 times faster empirically) to approximate solutions. Extensive experimental studies on functional climate networks show the effectiveness of this method in preserving macroscopic to meso-scopic and microscopic network structural properties.