in Advanced Probability
"Stochastic equations and random walks on graphs"
March 13-17, 2017, Novosibirsk, Russian Federation
A general goal of the mini-course is to introduce the audience into some notions and methods of stochastic differential equations (SDEs). Firstly, SDEs are one of the
main methods of constructing continuous Markov processes. Secondly, they are very useful for the theory of partial differential equations (mainly elliptic and
paraboic) and many important results in this area were originally obtained by stochastic analysis methods. (An inverse effect of PDEs on SDEs is also rather
important, too.) Finally, SDEs serve as a basis for numerous models in applications in physics, biology, et al.
In December 2015 the lecturer delivered amini-course on stochastic integration and basic SDEs. It is likely that some part of the audience today attended that course. However, this is not a pre-requisite. Everything from the backgrounds that is necessary will be briefly repeated (the repetition is the mother of the learning!) and there will be some new material. In particular, it will be shown why solutions of SDEs are Markov processes.
Typical questions in the analysis of large complex networks are how large is a network in terms of nodes and links? which nodes are most important/central? the degree distribution follows a power law? if yes, what is the exponent of the power law? how to estimate quickly the clustering coefficient? how to detect quickly principal clusters/communities of the network? All these questions can be answered with the help of the theory of random walks on graphs. In particular, using the theory of random walks on graphs, we can design algorithms with linear or even sublinear complexity. Such light complexity is necessary if we need to deal with networks of billions of nodes and links. In the first lecture, I provide an introduction to random walk based algorithms for network analysis. Then, in the first part I'll discuss methods based on random walks for network sampling, whereas in the second part I'll discuss methods based on random walks for network clustering.
The introductory part will be in English with possibility to ask questions in Russian. The two main parts I'll try to present in Russian.
The short course includes a number of relatively novel results on the asymptotic properties of the maximal path length in a class of directed acyclic graphs. In the introductory lecture, I will present the basic model and its extensions and discuss links with computer science, queueing theory, biology, percolation, etc. In the first main lecture, I will link the basic model (Barak-Erdos directed acyclic graph) with the infinite bin model, discuss its regenerative properties, formulate a number of main results and provide hints to their proofs. In the second main lecture, I will consider directed acyclic graphs of a more general nature, including graphs with varying probabilities of edges, random lengths of edges and multi-type edges. In particular, I will show that the asymptotic properties of the maximal path length differ significantly in the cases of light- and heavy-tailed distributions of edges lengths.
The list of references and some files related to the course may be found here. In particular, it includes 4 papers written by the lecturer jointly with T. Konstantopoulos, S. Zachary, D. Denisov, J. Martin, and Ph. Schmidt.
|Novosibirsk State University|
|International Mathematical Center (IMC NSU)|