Random walks and their application in exploring networks and ranking objects

Today, random walks and Markov chain Monte Carlo method appear in many fields of engineering and computer science. In many scenarios samples are needed from an unknown data set, or there is demand to explore an unknown network. In such situations random walks do not only provide very simple algorithms but also these algorithms are provably optimal.

In this talk, I will talk about two different directions I have been working on Markov chains. In the first part of the talk, I will talk about random walks on the set of permutations of $n$ objects, a set whose size is $n!$. Since 1990s to today, various versions of this problem have been studied, each for different motivation. After introducing the problem and presenting a brief history, I will talk about some of my work on such random walks motivated from applications in data structures and machine learning.

The second part of the talk is about exploring social network graphs, where my co-author and I proved that in a certain framework, random walk based methods beat any other algorithm in runtime.