  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.
