Large michele

Two examples of stochastic processes on graphs

Michele Garetto

Recorded 16 January 2017 in Lausanne, Vaud, Switzerland

Event: IC Colloquia - EPFL IC School Colloquia

Abstract

In this talk I will present my recent work on two problems that can be formalized as stochastic processes modifying the structure (node/edges) of a graph. The first one is a generalization of the classic bootstrap percolation process, a simple epidemic process in which a node gets infected as soon as R neighbors are infected. We generalize this process to the case of random infection thresholds in the nodes and random weights on the edges. The second example is related to reinforced random walks, i.e., weighted random walks that reinforce the weight of traversed edges. We show that under mild conditions shortest paths between a source and a destination naturally emerge by iterating the interplay between network structure (edge weights) and network function (random walks).

Watched 208 times.

 Watch