| Title:
|
Bounded expansion in web graphs (English) |
| Author:
|
Gago, Silvia |
| Author:
|
Schlatter, Dirk |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
50 |
| Issue:
|
2 |
| Year:
|
2009 |
| Pages:
|
181-190 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
graph minors |
| Keyword:
|
bounded expansion |
| Keyword:
|
webgraphs |
| MSC:
|
05C83 |
| MSC:
|
90B10 |
| MSC:
|
90B15 |
| MSC:
|
94C15 |
| idZBL:
|
Zbl 1212.05248 |
| idMR:
|
MR2537830 |
| . |
| Date available:
|
2009-08-18T12:24:27Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133427 |
| . |
| Reference:
|
[1] Albert R., Barabási A.-L.: Statistical mechanics of complex networks.Rev. Modern Phys. 74 (2002), 47--97. MR 1895096, 10.1103/RevModPhys.74.47 |
| Reference:
|
[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. 10.1103/PhysRevLett.94.018702 |
| Reference:
|
[3] Barabási A.-L., Albert R.: Emergence of scaling in random networks.Science 286 (1999), 509--512. MR 2091634, 10.1126/science.286.5439.509 |
| Reference:
|
[4] Barabási A.-L., Ravasz E., Vicsek T.: Deterministic scale-free networks.Phys. A 299 (2001), 559--564. 10.1016/S0378-4371(01)00369-7 |
| Reference:
|
[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 |
| Reference:
|
[6] Bollobás B., Riordan O.: The diameter of a scale-free random graph.Combinatorica 4 (2004), 5--34. MR 2057681, 10.1007/s00493-004-0002-2 |
| Reference:
|
[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. MR 1824277, 10.1002/rsa.1009 |
| Reference:
|
[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 |
| Reference:
|
[9] Bonato A., Janssen J.: Infinite limits of copying models of the web graph.Internet Math. 1 (2004), 193--213. Zbl 1080.05084, MR 2077225, 10.1080/15427951.2004.10129087 |
| Reference:
|
[10] Comellas F., Fertin G., Raspaud A.: Recursive graphs with small-world scale-free properties.Phys. Rev. E 69 (2004), 037104. 10.1103/PhysRevE.69.037104 |
| Reference:
|
[11] Dorogovtsev S.N., Goltsev A.V., Mendes J.F.F.: Pseudofractal scale-free web.Phys. Rev. E 65 (2002), 066122. 10.1103/PhysRevE.65.066122 |
| Reference:
|
[12] Doye J.P.K., Massen C.P.: Self-similar disk packings as model spatial scale-free networks.Phys. Rev. E 71 (2005), 016128. MR 2139325, 10.1103/PhysRevE.71.016128 |
| Reference:
|
[13] Dvořák S.: Asymptotical structures of combinatorial objects.PhD Thesis, Charles University, Prague, 2007. |
| Reference:
|
[14] Flexman A., Frieze A., Fenner T.: High degree vertices and eigenvalues in the preferential attachment graph.Internet Math. 2 (2005), 1--19. MR 2166274, 10.1080/15427951.2005.10129097 |
| Reference:
|
[15] Iguchi K., Yamada H.: Exactly solvable scale-free network model.Phys. Rev. E 71 (2005), 036144. MR 2135710, 10.1103/PhysRevE.71.036144 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 2397335, 10.1016/j.ejc.2006.07.013 |
| Reference:
|
[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. MR 2397336, 10.1016/j.ejc.2006.07.014 |
| Reference:
|
[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. MR 2408375, 10.1016/j.ejc.2007.11.019 |
| Reference:
|
[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. |
| Reference:
|
[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 |
| Reference:
|
[24] Noh J.D.: Exact scaling properties of a hierarchical network model.Phys. Rev. E 67 (2003), 045103. 10.1103/PhysRevE.67.045103 |
| Reference:
|
[25] Ravasz E., Barabási A.-L.: Hierarchical organization in complex networks.Phys. Rev. E 67 (2003), 026112. 10.1103/PhysRevE.67.026112 |
| Reference:
|
[26] Zhang Z., Rong L., Comellas F., Fertin G.: High-dimensional Apollonian networks.J. Phys. A 39 (2006), 1811--1818. Zbl 1086.68017, MR 2209302, 10.1088/0305-4470/39/8/003 |
| Reference:
|
[27] Zhang Z., Rong L., Guo C.: A deterministic small-world network created by edge iterations.Phys. A 363 (2006), 567--572. 10.1016/j.physa.2005.08.020 |
| . |
