Geodesic
Distribution of small subgraphs in Buckley--Osthus random graphs
Izvestiya. Mathematics , Tome 81 (2017) no. 2, pp. 391-443.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study a random graph model similar to the Buckley–Osthus preferential attachment model and develop a technique for estimating the expectation of a wide class of random variables in this model. By means of this technique, we prove a theorem on the asymptotic behaviour of the expectation of the number of subgraphs isomorphic to a fixed graph in the random graphs of the model.
Keywords: random graph, preferential attachment, Buckley–Osthus model, number of subgraphs.
Mots-clés : internet graph 
@article{IM2_2017_81_2_a6,
     author = {S. D. Tilga},
     title = {Distribution of small subgraphs in {Buckley--Osthus} random graphs},
     journal = {Izvestiya. Mathematics },
     pages = {391--443},
     publisher = {mathdoc},
     volume = {81},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2017_81_2_a6/}
}
TY  - JOUR
AU  - S. D. Tilga
TI  - Distribution of small subgraphs in Buckley--Osthus random graphs
JO  - Izvestiya. Mathematics 
PY  - 2017
SP  - 391
EP  - 443
VL  - 81
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2017_81_2_a6/
LA  - en
ID  - IM2_2017_81_2_a6
ER  - 
%0 Journal Article
%A S. D. Tilga
%T Distribution of small subgraphs in Buckley--Osthus random graphs
%J Izvestiya. Mathematics 
%D 2017
%P 391-443
%V 81
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2017_81_2_a6/
%G en
%F IM2_2017_81_2_a6
S. D. Tilga. Distribution of small subgraphs in Buckley--Osthus random graphs. Izvestiya. Mathematics , Tome 81 (2017) no. 2, pp. 391-443. http://geodesic.mathdoc.fr/item/IM2_2017_81_2_a6/

[1] A.-L. Barabási, R. Albert, “Emergence of scaling in random networks”, Science, 286:5439 (1999), 509–512 | DOI | MR | Zbl

[2] R. Albert, Hawoong Jeong, A.-L. Barabási, “Diameter of the world-wide web”, Nature, 401 (1999), 130–131 | DOI

[3] B. Bollobás, O. M. Riordan, “Mathematical results on scale-free random graphs”, Handbook of graphs and networks, Wiley-VCH, Weinheim, 2003, 1–34 | MR | Zbl

[4] B. Bollobás, O. Riordan, “The diameter of a scale-free graph”, Combinatorica, 24:1 (2004), 5–34 | DOI | MR | Zbl

[5] A. A. Ryabchenko, E. A. Samosvat, “On the number of subgraphs of the Barabási–Albert random graph”, Izv. Math., 76:3 (2012), 607–625 | DOI | DOI | MR | Zbl

[6] P. G. Buckley, D. Osthus, “Popularity based random graph models leading to a scale-free degree sequence”, Discrete Math., 282:1-3 (2004), 53–68 | DOI | MR | Zbl

[7] T. F. Móri, “The maximum degree of the Barabási–Albert random tree”, Combin. Probab. Comput., 14:3 (2005), 339–348 | DOI | MR | Zbl

[8] E. A. Grechnikov, G. G. Gusev, L. A. Ostroumova, Yu. L. Pritykin, A. M. Raigorodskii, P. Serdyukov, D. V. Vinogradov, M. E. Zhukovskiy, “Empirical validation of the Buckley–Osthus model for the web host graph”, CIKM '12: Proceedings of the 21st ACM international conference on information and knowledge management, 2012, 1577–1581

[9] A. M. Raigorodskii, Modeli interneta, Intellekt, Dolgoprudnyi, 2013, 64 pp.

[10] S. N. Dorogovtsev, Lectures on complex networks, Oxf. Master Ser. Phys., 20, Oxford Univ. Press, Oxford, 2010, x+134 pp. | DOI | MR | Zbl

[11] L. Lovász, Large networks and graph limits, Amer. Math. Soc. Colloq. Publ., 60, Amer. Math. Soc., Providence, RI, 2012, xiv+475 pp. | DOI | MR | Zbl

[12] M. E. J. Newman, Networks. An introduction, Oxford Univ. Press, Oxford, 2010, xii+772 pp. | DOI | MR | Zbl

[13] M. E. J. Newman, “Power laws, Pareto distributions and Zipf's law”, Contemporary Physics, 46:5 (2005), 323–351 | DOI

[14] M. Penrose, Random geometric graphs, Oxford Stud. Probab., 5, Oxford Univ. Press, Oxford, 2003, xiv+330 pp. | DOI | MR | Zbl

[15] M. E. J. Newman, “The structure and function of complex networks”, SIAM Rev., 45:2 (2003), 167–256 | DOI | MR | Zbl

[16] L. Ostroumova Prokhorenkova, E. Samosvat, Global clustering coefficient in scale-free networks, arXiv: 1410.1997

[17] N. Eggemann, S. D. Noble, “The clustering coefficient of a scale-free random graph”, Discrete Appl. Math., 159:10 (2011), 953–965 | DOI | MR | Zbl

[18] R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal, “Stochastic models for the web graph”, 41st annual symposium on foundations of computer science (Redondo Beach, CA, 2000), IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 57–65 | DOI | MR | Zbl