The diameter of protean graphs
type: Item
instance of: scholarly article
title: The diameter of protean graphs
zbMATH Open document ID: 1153.05064
author: Paweł Prałat
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
review text: A model for the web graph depending on three parameters \(n, d, \eta\) is considered. The \(n\) vertices are renewed over time, and older vertices are more likely to receive edges than younger ones. The vertices are ranked according to age: oldest ranked 1 and youngest ranked \(n\). The random edges have probabilities proportional to the rank raised to a fixed power \(-\eta\). At each time step a randomly selected vertex is renewed and get \(d\) updated edges. The process yields a so called protean graph. The main result is that with high probability the protean graph has a giant component of diameter of order log \(n\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 5300627
zbMATH Keywords: random graphs
zbMATH Keywords: protean web graph
zbMATH Keywords: giant component
zbMATH Keywords: graph diameter
MaRDI profile type: Publication
full work available at URL: j.disc.2007.06.025
OpenAlex ID: W1968105630
cites work: Q5674726
cites work: Infinite Limits of Copying Models of the Web Graph
cites work: Coupling Online and Offline Analyses for Random Power Law Graphs
cites work: Q4519896
cites work: Rank-Based Attachment Leads to Power Law Graphs
cites work: Protean Graphs
cites work: Growing Protean Graphs
cites work: Renormalization group analysis of the small-world network model
DOI: 10.1016/J.DISC.2007.06.025
description: scientific article; zbMATH DE number 5300627