2013/04/21 by Andrey Kupavskii, Kupavskii, Andrey, Ostroumova, Liudmila +4
Physics and Astronomy · Mathematics · #Complex Network Analysis Techniques #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1304.5715
In this paper we consider a well-known generalization of the Barab 'asi and\nAlbert preferential attachment model - the Buckley-Osthus model. Buckley and\nOsthus proved that in this model the degree sequence has a power law\ndistribution. As a natural (and arguably more interesting) next step, we study\nthe second degrees of vertices. Roughly speaking, the second degree of a vertex\nis the number of vertices at distance two from this vertex. The distribution of\nsecond degrees is of interest because it is a good approximation of PageRank,\nwhere the importance of a vertex is measured by taking into account the\npopularity of its neighbors.\n We prove that the second degrees also obey a power law. More precisely, we\nestimate the expectation of the number of vertices with the second degree\ngreater than or equal to k and prove the concentration of this random variable\naround its expectation using the now-famous Talagrand's concentration\ninequality over product spaces. As far as we know this is the only application\nof Talagrand's inequality to random web graphs, where the (preferential\nattachment) edges are not defined over a product distribution, making the\napplication nontrivial, and requiring certain novelty.\n