Web Graph Models: Properties and Applications

Speaker  Andrey Raigorodsky

Affiliation  Moscow State University and Moscow Institute of Physics and Technology

Host  Yuval Peres

Duration  00:45:51

Date recorded  5 July 2011

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.

©2011 Microsoft Corporation. All rights reserved.
> Web Graph Models: Properties and Applications