Bounded expansion in web graphs

Silvia Gago; Dirk Schlatter

Commentationes Mathematicae Universitatis Carolinae (2009)

  • Volume: 50, Issue: 2, page 181-190
  • ISSN: 0010-2628

Abstract

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

How to cite

top

Gago, Silvia, and Schlatter, Dirk. "Bounded expansion in web graphs." Commentationes Mathematicae Universitatis Carolinae 50.2 (2009): 181-190. <http://eudml.org/doc/32492>.

@article{Gago2009,
abstract = {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.},
author = {Gago, Silvia, Schlatter, Dirk},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph minors; bounded expansion; webgraphs; graph minor; bounded expansion; webgraph},
language = {eng},
number = {2},
pages = {181-190},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Bounded expansion in web graphs},
url = {http://eudml.org/doc/32492},
volume = {50},
year = {2009},
}

TY - JOUR
AU - Gago, Silvia
AU - Schlatter, Dirk
TI - Bounded expansion in web graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2009
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 50
IS - 2
SP - 181
EP - 190
AB - 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.
LA - eng
KW - graph minors; bounded expansion; webgraphs; graph minor; bounded expansion; webgraph
UR - http://eudml.org/doc/32492
ER -

References

top
  1. Albert R., Barabási A.-L., 10.1103/RevModPhys.74.47, Rev. Modern Phys. 74 (2002), 47--97. MR1895096DOI10.1103/RevModPhys.74.47
  2. Andrade J.S., Jr., Herrmann H.J., Andrade R.F.S., da Silva L.R., 10.1103/PhysRevLett.94.018702, Phys. Rev. Lett. 94 (2005), 018702. DOI10.1103/PhysRevLett.94.018702
  3. Barabási A.-L., Albert R., 10.1126/science.286.5439.509, Science 286 (1999), 509--512. MR2091634DOI10.1126/science.286.5439.509
  4. Barabási A.-L., Ravasz E., Vicsek T., 10.1016/S0378-4371(01)00369-7, Phys. A 299 (2001), 559--564. DOI10.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. MR2016117
  6. Bollobás B., Riordan O., 10.1007/s00493-004-0002-2, Combinatorica 4 (2004), 5--34. MR2057681DOI10.1007/s00493-004-0002-2
  7. Bollobás B., Riordan O., Spencer J., Tusnády G., 10.1002/rsa.1009, Random Structures Algorithms 18 (2001), 279--290. MR1824277DOI10.1002/rsa.1009
  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. MR2182910
  9. Bonato A., Janssen J., 10.1080/15427951.2004.10129087, Internet Math. 1 (2004), 193--213. Zbl1080.05084MR2077225DOI10.1080/15427951.2004.10129087
  10. Comellas F., Fertin G., Raspaud A., 10.1103/PhysRevE.69.037104, Phys. Rev. E 69 (2004), 037104. DOI10.1103/PhysRevE.69.037104
  11. Dorogovtsev S.N., Goltsev A.V., Mendes J.F.F., 10.1103/PhysRevE.65.066122, Phys. Rev. E 65 (2002), 066122. DOI10.1103/PhysRevE.65.066122
  12. Doye J.P.K., Massen C.P., 10.1103/PhysRevE.71.016128, Phys. Rev. E 71 (2005), 016128. MR2139325DOI10.1103/PhysRevE.71.016128
  13. Dvořák S., Asymptotical structures of combinatorial objects, PhD Thesis, Charles University, Prague, 2007. 
  14. Flexman A., Frieze A., Fenner T., 10.1080/15427951.2005.10129097, Internet Math. 2 (2005), 1--19. MR2166274DOI10.1080/15427951.2005.10129097
  15. Iguchi K., Yamada H., 10.1103/PhysRevE.71.036144, Phys. Rev. E 71 (2005), 036144. MR2135710DOI10.1103/PhysRevE.71.036144
  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. MR1730317
  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. MR1931804
  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., 10.1016/j.ejc.2006.07.013, European J. Combin. 29 (2008), no. 3, 760--776. MR2397335DOI10.1016/j.ejc.2006.07.013
  20. Nešetřil J., Ossona de Mendez P., 10.1016/j.ejc.2006.07.014, European J. Combin. 29 (2008), no. 3, 777--791. MR2397336DOI10.1016/j.ejc.2006.07.014
  21. Nešetřil J., Ossona de Mendez P., 10.1016/j.ejc.2007.11.019, European J. Combin. 29 (2008), no. 4, 1012--1024. MR2408375DOI10.1016/j.ejc.2007.11.019
  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. MR2277165
  24. Noh J.D., 10.1103/PhysRevE.67.045103, Phys. Rev. E 67 (2003), 045103. DOI10.1103/PhysRevE.67.045103
  25. Ravasz E., Barabási A.-L., 10.1103/PhysRevE.67.026112, Phys. Rev. E 67 (2003), 026112. DOI10.1103/PhysRevE.67.026112
  26. Zhang Z., Rong L., Comellas F., Fertin G., 10.1088/0305-4470/39/8/003, J. Phys. A 39 (2006), 1811--1818. Zbl1086.68017MR2209302DOI10.1088/0305-4470/39/8/003
  27. Zhang Z., Rong L., Guo C., 10.1016/j.physa.2005.08.020, Phys. A 363 (2006), 567--572. DOI10.1016/j.physa.2005.08.020

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.