The diameter of protean graphs (Q932616)

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\).