Empirical validation of the buckley-osthus model for the web host graph: Degree and edge distributions

Maxim Zhukovskiy, Dmitry Vinogradov, Yuri Pritykin, Liudmila Ostroumova, Evgeniy Grechnikov, Gleb Gusev, Pavel Serdyukov, Andrei Raigorodskii

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We consider the Buckley-Osthus implementation of preferential attachment and its ability to model the web host graph in two aspects. One is the degree distribution that we observe to follow the power law, as often being the case for real-world graphs. Another one is the two-dimensional edge distribution, the number of edges between vertices of given degrees. We fit a single "initial attractiveness" parameter a of the model, first with respect to the degree distribution of the web host graph, and then, absolutely independently, with respect to the edge distribution. Surprisingly, the values of a we obtain turn out to be nearly the same. Therefore the same model with the same value of the parameter a fits very well the two independent and basic aspects of the web host graph. In addition, we demonstrate that other models completely lack the asymptotic behavior of the edge distribution of the web host graph, even when accurately capturing the degree distribution. To the best of our knowledge, this is the first study confirming the ability of preferential attachment models to reflect the distribution of edges between vertices with respect to their degrees in a real graph of Internet.

Original languageEnglish (US)
Title of host publicationCIKM 2012 - Proceedings of the 21st ACM International Conference on Information and Knowledge Management
Pages1577-1581
Number of pages5
DOIs
StatePublished - 2012
Externally publishedYes
Event21st ACM International Conference on Information and Knowledge Management, CIKM 2012 - Maui, HI, United States
Duration: Oct 29 2012Nov 2 2012

Publication series

NameACM International Conference Proceeding Series

Conference

Conference21st ACM International Conference on Information and Knowledge Management, CIKM 2012
Country/TerritoryUnited States
CityMaui, HI
Period10/29/1211/2/12

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Keywords

  • assortative mixing
  • buckley-osthus random graphs
  • edge distribution with respect to vertex degrees
  • power law degree distribution
  • preferential attachment
  • web host graph

Fingerprint

Dive into the research topics of 'Empirical validation of the buckley-osthus model for the web host graph: Degree and edge distributions'. Together they form a unique fingerprint.

Cite this