Séminaire SPACE Tours

Hitting times for simple random walk on dense Erdös-Rényi random graphs
Felipe Torres
Friday 24 May 2013 11:00 -  Tours -  Salle 1180 (Bât E2)

Résumé :
Diffusions process are classical tools for exploring the topology of networks, by - for example - using the connections between spectral properties of their generators and the local or global network's geometry. In this talk, consider a simple random walk (at discrete time) on the set of vertices of a dense Erdös-Rényi random graph. Roughly speaking, the hitting time of the random walk between two vertices of the graph, is defined as to be the expected number of steps the random walk needs to go from one vertex to the other one. The aim of this talk is to estimate the order of magnitud of the hitting time between vertices chosen according to the stationary distribution of the random walk, for almost all realizations of the random graph, as the number of vertices tends to infinity. A short review of techniques for when the graph is non random will be presented and their application to the random case will be discussed. If time permits, connections to mixing time and to cover time problems for when the graph is random will be also mentioned. This is work in progress with Matthias Löwe.

Liens :