A Topology-Aware Random Walk

InKwan YU  Richard NEWMAN  

Publication
IEICE TRANSACTIONS on Communications   Vol.E95-B   No.3   pp.995-998
Publication Date: 2012/03/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E95.B.995
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network
Keyword: 
topology-aware,  random walk,  

Full Text: PDF>>
Buy this Article




Summary: 
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.