Seminar Details
2010-02-18 (16.30) : Colloquium CESAME-MAPA - Random walks on graphs: what for?
At Auditoire Ch.-J. de La Vallée Poussin (cycl 01)
Organized by Mathematical Engineering
Speaker :
Delvenne, Jean-Charles
Abstract :
How does Google work? What is so magical about expander graph? How do we
detect communities in large social graphs? The three answers involve one
same tool: random walks on graphs.
Given a graph, one may start from a vertex and, at each time step, jump
randomly to one of its neighbours. This random walk transforms the graph
into a Markov chain. The study of this Markov chain provides a lot of
insight into the combinatorial properties of the graph. We will cover a
sample of applications of this technique.