Presentation
Fast random walk through reduction of absorbing Markov chain
DescriptionRandom walk is a prevalent statistical technique that has been widely used in network analysis. This requires a considerable number of walk samples for accurate estimation; thus, random walk does not work well on large networks with long walk lengths. This paper addresses fast random walk through the reduction of absorbing Markov chains (AMC). We first select some states in an AMC as additional absorbing states, and random walk is performed on this modified AMC. Next, we construct a reduced AMC retaining only the absorbing states, with additionally selected ones reverted to transient states, and perform random walk again. Based on the results of two random walks, the expected number of visits to each state is calculated in a stochastic manner. Experimental results on IR-drop analysis demonstrate significant speedup, achieving a 78% reduction in runtime compared to the state-of-the-art random walk approach.
Event Type
Networking
Work-in-Progress Poster
TimeMonday, June 236:00pm - 7:00pm PDT
LocationLevel 2 Lobby