Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph minors; bounded expansion; webgraphs
graph minors; bounded expansion; webgraphs
Summary:
In this paper we study various models for web graphs with respect to bounded expansion. All the deterministic models even have constant expansion, whereas the copying model has unbounded expansion. The most interesting case turns out to be the preferential attachment model --- which we conjecture to have unbounded expansion, too.
References:
[1] Albert R., Barabási A.-L.: Statistical mechanics of complex networks. Rev. Modern Phys. 74 (2002), 47--97. DOI 10.1103/RevModPhys.74.47 | MR 1895096
[2] Andrade J.S., Jr., Herrmann H.J., Andrade R.F.S., da Silva L.R.: Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs. Phys. Rev. Lett. 94 (2005), 018702. DOI 10.1103/PhysRevLett.94.018702
[3] Barabási A.-L., Albert R.: Emergence of scaling in random networks. Science 286 (1999), 509--512. DOI 10.1126/science.286.5439.509 | MR 2091634
[4] Barabási A.-L., Ravasz E., Vicsek T.: Deterministic scale-free networks. Phys. A 299 (2001), 559--564. DOI 10.1016/S0378-4371(01)00369-7
[5] Bollobás B., Riordan O.: Mathematical results on scale-free random graphs. in Handbook of Graphs and Networks: From the Genome to the Internet (S. Bornholdt and H.G. Schuster, Eds.), Wiley-VCH, Weinheim, 2003, pp. 1--34. MR 2016117
[6] Bollobás B., Riordan O.: The diameter of a scale-free random graph. Combinatorica 4 (2004), 5--34. DOI 10.1007/s00493-004-0002-2 | MR 2057681
[7] Bollobás B., Riordan O., Spencer J., Tusnády G.: The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 (2001), 279--290. DOI 10.1002/rsa.1009 | MR 1824277
[8] Bonato A.: A survey of models of the web graph. Proceedings of the 1st Workshop on Combinatorial and Algorithmic Aspects of Networking, Springer, Berlin, 2005, pp. 159--172. MR 2182910
[9] Bonato A., Janssen J.: Infinite limits of copying models of the web graph. Internet Math. 1 (2004), 193--213. DOI 10.1080/15427951.2004.10129087 | MR 2077225 | Zbl 1080.05084
[10] Comellas F., Fertin G., Raspaud A.: Recursive graphs with small-world scale-free properties. Phys. Rev. E 69 (2004), 037104. DOI 10.1103/PhysRevE.69.037104
[11] Dorogovtsev S.N., Goltsev A.V., Mendes J.F.F.: Pseudofractal scale-free web. Phys. Rev. E 65 (2002), 066122. DOI 10.1103/PhysRevE.65.066122
[12] Doye J.P.K., Massen C.P.: Self-similar disk packings as model spatial scale-free networks. Phys. Rev. E 71 (2005), 016128. DOI 10.1103/PhysRevE.71.016128 | MR 2139325
[13] Dvořák S.: Asymptotical structures of combinatorial objects. PhD Thesis, Charles University, Prague, 2007.
[14] Flexman A., Frieze A., Fenner T.: High degree vertices and eigenvalues in the preferential attachment graph. Internet Math. 2 (2005), 1--19. DOI 10.1080/15427951.2005.10129097 | MR 2166274
[15] Iguchi K., Yamada H.: Exactly solvable scale-free network model. Phys. Rev. E 71 (2005), 036144. DOI 10.1103/PhysRevE.71.036144 | MR 2135710
[16] Kleinberg J., Kumar S.R., Raghavan P., Rajagopalan S., Tomkins A.: The web as a graph: Measurements, models and methods. Proceedings of the International Conference on Combinatorics and Computing, Springer, Berlin, 1999, pp. 1--17. MR 1730317
[17] Kumar S.R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A., Upfal E.: Stochastic models for the web graph. Proceedings of the 41st IEEE Symp. on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 57--65. MR 1931804
[18] Kumar S.R., Raghavan P., Rajagopalan S., Tomkins A.: Trawling the web for emerging cyber-communities. Proceedings of the 8th WWW Conference, 1999, 403--416.
[19] Nešetřil J., Ossona de Mendez P.: Grad and classes with bounded expansion I. Decompositions. European J. Combin. 29 (2008), no. 3, 760--776. DOI 10.1016/j.ejc.2006.07.013 | MR 2397335
[20] Nešetřil J., Ossona de Mendez P.: Grad and classes with bounded expansion II. Algorithmic aspects. European J. Combin. 29 (2008), no. 3, 777--791. DOI 10.1016/j.ejc.2006.07.014 | MR 2397336
[21] Nešetřil J., Ossona de Mendez P.: Grad and classes with bounded expansion III. Restricted graph homomorphism dualities. European J. Combin. 29 (2008), no. 4, 1012--1024. DOI 10.1016/j.ejc.2007.11.019 | MR 2408375
[22] Nešetřil J., Ossona de Mendez P.: The grad of a graph and classes with bounded expansion. in 7th International Colloquium on Graph Theory (A. Raspaud and O. Delmas, Eds.), Electron. Notes Discrete Math. 22, Elsevier, 2005, pp. 101-106.
[23] Nešetřil J., Ossona de Mendez P.: Linear time low tree-width partitions and algorithmic consequences. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 391--400. MR 2277165
[24] Noh J.D.: Exact scaling properties of a hierarchical network model. Phys. Rev. E 67 (2003), 045103. DOI 10.1103/PhysRevE.67.045103
[25] Ravasz E., Barabási A.-L.: Hierarchical organization in complex networks. Phys. Rev. E 67 (2003), 026112. DOI 10.1103/PhysRevE.67.026112
[26] Zhang Z., Rong L., Comellas F., Fertin G.: High-dimensional Apollonian networks. J. Phys. A 39 (2006), 1811--1818. DOI 10.1088/0305-4470/39/8/003 | MR 2209302 | Zbl 1086.68017
[27] Zhang Z., Rong L., Guo C.: A deterministic small-world network created by edge iterations. Phys. A 363 (2006), 567--572. DOI 10.1016/j.physa.2005.08.020
Search
Partner of
