TY - GEN

T1 - Empirical validation of the buckley-osthus model for the web host graph

T2 - 21st ACM International Conference on Information and Knowledge Management, CIKM 2012

AU - Zhukovskiy, Maxim

AU - Vinogradov, Dmitry

AU - Pritykin, Yuri

AU - Ostroumova, Liudmila

AU - Grechnikov, Evgeniy

AU - Gusev, Gleb

AU - Serdyukov, Pavel

AU - Raigorodskii, Andrei

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - assortative mixing

KW - buckley-osthus random graphs

KW - edge distribution with respect to vertex degrees

KW - power law degree distribution

KW - preferential attachment

KW - web host graph

UR - http://www.scopus.com/inward/record.url?scp=84871072234&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871072234&partnerID=8YFLogxK

U2 - 10.1145/2396761.2398476

DO - 10.1145/2396761.2398476

M3 - Conference contribution

AN - SCOPUS:84871072234

SN - 9781450311564

T3 - ACM International Conference Proceeding Series

SP - 1577

EP - 1581

BT - CIKM 2012 - Proceedings of the 21st ACM International Conference on Information and Knowledge Management

Y2 - 29 October 2012 through 2 November 2012

ER -