Author: Andrey Raigorodskiy
In my lectures, I shall give a survey of various approaches to construct models of random web graphs. First, I shall speak about classical models such as the Barabasi — Albert model, the Bollobas — Riordan model, the Buckley — Osthus model, the Copying model, etc. In particular, I shall describe some features of the real WWW which are well captured by these models: on the one hand, I shall formulate and probably prove some theorems concerning these features in different models; on the other hand, I shall try to provide empirical validations of theoretical results, which are sometimes quite surprising. Second, I shall exhibit new recent approaches that are proposed by our research group in Yandex. Finally, I shall discuss some applications to web search.
The lectures will be accompanied by research seminars, where the students would be able to realize some algorithms described in the lectures.