Bounded expansion in models of webgraphs

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/1213

Title:	Bounded expansion in models of webgraphs
Author:	Gago Álvarez, Silvia; Schlatter, Dirk
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Abstract:	We study the bounded expansion of several models of web graphs. We show that various deterministic graph models for large complex networks have constant bounded expansion.We study two random models of webgraphs, showing that the model of Bonato has not bounded expansion, and we conjecture that the classical model of Barabási may have also not bounded expansion.
Subject(s):	-Combinatorics -Graph theory -Computer science -Probability -bounded expansion -grad -webgraphs -minor closed class -random graphs -Combinacions (Matemàtica) -Grafs, Teoria de -Informàtica--Matemàtica -Probabilitats -Classificació AMS::05 Combinatorics -Classificació AMS::05 Combinatorics::05C Graph theory -Classificació AMS::68 Computer science::68R Discrete mathematics in relation to computer science -Classificació AMS::60 Probability theory and stochastic processes::60C05 Combinatorial probability
Rights:	Attribution-NonCommercial-NoDerivs 2.5 Spain http://creativecommons.org/licenses/by-nc-nd/2.5/es/
Document type:	Article
Share: