论文标题
随机步行图中的加权跳跃抽样
Weighted Jump in Random Walk Graph Sampling
论文作者
论文摘要
近年来，基于随机步行的采样方法已被广泛用于图形采样中，而该方法对样本中的高度节点有偏见。为了克服这种缺陷，诸如GMD之类的经典方法修改了目标图的拓扑结构，以便马尔可夫链的长期行为可以实现统一的分布。但是，这种修饰会降低图的电导，从而使采样器长期保持在同一节点中，从而导致采样。为了解决这个问题，我们提出了一种修改目标图的新方法，因此提出了使用参数C的加权跳跃随机步行（WJRW）以提高性能。我们证明WJRW可以通过C统一简单的随机步行和均匀分布，并且我们还对现实世界数据集进行了广泛的实验。实验结果表明，WJRW可以在同一预算下显着提高准确性。我们还研究了参数C的效果，并给出了建议的范围，以更好地使用应用。
Random walk based sampling methods have been widely used in graph sampling in recent years, while it has bias towards higher degree nodes in the sample. To overcome this deficiency, classical methods such as GMD modify the topology of target graphs so that the long-term behavior of Markov chain can achieve uniform distribution. This modification, however, reduces the conductance of graphs, thus makes the sampler stay in the same node for long time, resulting in undersampling. To address this issue, we propose a new way of modifying target graph, thus propose Weighted Jump Random Walk (WJRW) with parameter C to improve the performance. We prove that WJRW can unify Simple Random Walk and uniform distribution through C, and we also conduct extensive experiments on real-world dataset. The experimental results show WJRW can promote the accuracy significantly under the same budget. We also investigate the effect of the parameter C, and give the suggested range for a better usage in application.
