you're reading...

Friday SACT talk – Ilia

Tomorrow’s speaker will be Ilia Zvedeniouk.

I will give an introduction to random walks on directed graphs and discuss some concepts to do with Markov Processes. Then I will discuss the paper ‘Local Partitioning for Directed Graphs Using PageRank‘ and walk through the proof of the ‘main theorem’ discussed therein.

Abstract. A local partitioning algorithm finds a set with small conductance near a specified seed ver-
tex. In this paper, we present a generalization of a local partitioning algorithm for undirected graphs to
strongly connected directed graphs. In particular, we prove that by computing a personalized PageRank
vector in a directed graph, starting from a single seed vertex within a set S that has conductance at
most α, and by performing a sweep over that vector, we can obtain a set of vertices S’ with conduc-
tance Φ_M (S’) = O( sqrt(α log |S|) ). Here, the conductance function Φ_M is defined in terms of the stationary
distribution of a random walk in the directed graph. In addition, we describe how this algorithm may
be applied to the PageRank Markov chain of an arbitrary directed graph, which provides a way to
partition directed graphs that are not strongly connected.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: