Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Random walks and their application in exploring networks and ranking objects
Speaker:Shahrzad Haddadan
coming from:Sapienza University of Rome
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 6 September 2019
Duration:30 Minutes
Building:E1 4
The study of Markov chains began in the early 20th century. Being a tool to describe various phenomenons ranging from card shuffling to stock profit, Markov chains received enormous attention from researchers active in different field of science.

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.

Name(s):Stefano Leucci
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Stefano Leucci, 09/05/2019 03:07 PM -- Created document.