Para receber por e-mail novas publicações de Seminário de Probabilidade e Combinatória, Clique Aqui!

Seminários do IMPA

Probabilidade e Combinatória

Estimating graph parameters with random walks
Anna Ben-Hamou

Sorbonne Université
Terça-feira, 14 de agosto de 2018, 13:30
Auditorio 1

What can one learn about a graph from random walk trajectories on it? A trivial answer is that, given enough time and resources, we can learn everything. If the graph is connected, and one is willing to wait for long enough, eventually, all edges of the graph are crossed by the walk. However, our motivation is the analysis of large networks that can contain billions of nodes. Direct manipulation or full observations of such huge graphs are typically impractical. Our problem, then, is to determine the least number of random walk steps that are needed to compute interesting graph parameters. Most methods are based on the number of collisions in the sample formed by the endpoints of random walks with length larger than the mixing time. We show that counting the number of intersections between random walk trajectories give strictly more information and allow us to estimate the number of nodes and of edges with an optimal time complexity. This is a joint work with Roberto I. Oliveira (IMPA) and Yuval Peres (Microsoft Research).