Spectral Sparsification (SS) computes a subgraph preserving the spectrum of the original graph and has been shown to outperform Random Vertex (RV) and Random Edge (RE) sampling methods on various sampling quality metrics. While Random Walk (RW) has been shown to perform better than RV and RE, especially on Largest Connected Component and Clustering Coefficient quality metrics, a comparison between SS and RW has not yet been done. This paper presents a comparison experiment of the graph sampling methods SS and RW. Extensive experiments on real-world and synthetic data sets demonstrate that SS outperforms RW, on average 23% better sampling quality metrics, with the largest improvement on Clustering Coefficient and Closeness centrality metrics at 45% and 26% better respectively. Furthermore, visual comparisons demonstrate that SS samples better preserve the structure of the original graphs than RW on a wide variety of graphs, even on graphs where RW fails, such as the grid and long-diameter graphs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Comparison of Graph Sampling: Spectral Sparsification vs. Random Walk

  • Xingjue Jiang,
  • Seok-Hee Hong,
  • Amyra Meidiana

摘要

Spectral Sparsification (SS) computes a subgraph preserving the spectrum of the original graph and has been shown to outperform Random Vertex (RV) and Random Edge (RE) sampling methods on various sampling quality metrics. While Random Walk (RW) has been shown to perform better than RV and RE, especially on Largest Connected Component and Clustering Coefficient quality metrics, a comparison between SS and RW has not yet been done. This paper presents a comparison experiment of the graph sampling methods SS and RW. Extensive experiments on real-world and synthetic data sets demonstrate that SS outperforms RW, on average 23% better sampling quality metrics, with the largest improvement on Clustering Coefficient and Closeness centrality metrics at 45% and 26% better respectively. Furthermore, visual comparisons demonstrate that SS samples better preserve the structure of the original graphs than RW on a wide variety of graphs, even on graphs where RW fails, such as the grid and long-diameter graphs.