Research plan summary
Stochastic processes on random graphs are mathematical models for real-world systems where interactions between nodes (e.g. human individuals, computer units) are governed by a network structure (e.g. a social network, the Internet). Such models are often impossible to analyze by direct numerical computations, due to highly irregular network structure, uncoordinated behavior of the nodes, and randomly varying environmental effects. Despite vast research literature on the structure of random graphs, mathematical results on stochastic processes on random graphs are still rather scarce, and mostly restricted to unrealistic graph models with weak clustering and light-tailed degree distributions. Likewise, results on stochastic processes in random environments are mostly restricted to simple random walks on regular lattices.
This project aims to quantify how strong clustering, heavy-tailed degree distributions, and random environmental features affect the dynamics of random walks, queueing networks, and more general population processes on realistic graph models. This shall be done by analyzing new graph models based on stochastic geometry, and by developing new time-scale separation inequalities using convex and supermodular stochastic orders. Other key research methods include stochastic coupling theory, Palm calculus, Hardy–Littlewood maximal functions, Lyapunov functions, and regular variation theory.
The project's results will help to evaluate the effect of realistic graph features on the dynamics of key stochastic processes encountered in our society: random walks are used to rank web pages, queueing networks to analyze traffic flows in data networks, and contact processes to model the spread of information in social networks and distributed computing. These results may have far-reaching implications in the development of fast search engines for the Internet, efficient transmission protocols for wireless data networks, and scalable distributed algorithms for large data sets.
Please contact Lasse Leskelä if you are interested in collaboration or if you have any questions or comments.