Web Graph Models: Properties and Applications

Опубликовано 17 августа 2016, 2:33

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.