A Topology-Aware Random Walk

作者:Yu InKwan*; Newman Richard
来源:IEICE - Transactions on Communications, 2012, E95B(3): 995-998.
DOI:10.1587/transcom.E95.B.995

摘要

When a graph can be decomposed into components of well-connected subgraphs, it is possible to speed up random walks by taking advantage of topology of the graph. In this paper, a modified Metropolis random walk scheme is introduced and conditions are given when it performs better than the original Metropolis algorithm.

  • 出版日期2012-3