Web Graph Models: Properties and Applications


July 5, 2011


Andrey Raigorodsky


Moscow State University and Moscow Institute of Physics and Technology


In 1999 A. Barabasi and R. Albert suggested the idea of preferential attachment to explain the power law distribution of the vertex degrees in web graphs. Several mathematical models have then appeared incorporating this idea. Among them, the LCD model by B. Bollobas and O. Riordan, the Buckley–Osthus model, the Bollobas–Borgs-Chayes–Riordan model of directed scale-free graphs, etc. Many deep results have been obtained concerning these models. For example, one studies the degree distributions, the diameter, the clustering coefficient, and so on. In our work, we continue studying important statistics of the random web graph in the just-mentioned models. On the one hand, we substantially improve some of the formerly known results. On the other hand, we introduce new characteristics of the web including the number of edges between vertices of given degrees. For these characteristics, we find accurate analytic expressions and we apply them to improve quality of search engine rankings.


Andrey Raigorodsky

Andrei M. Raigorodskii is a Professor at the Department of Mathematical Statistics and Random Processes in Moscow State University. He is also a Professor at the Department of Data Analysis in Moscow Institute of Physics and Technology. Three years ago he organized a research group in Yandex Internet company in Moscow. Now this group is transformed into a big laboratory which is intensively working on various research problems concerning the Internet. Raigorodskii’s current research interests include random graphs, extremal graph and hypergraph theory, probabilistic and algebraic methods in combinatorics, combinatorial geometry.