The diameter of a scale-free random graph
type: Item
instance of: scholarly article
title: The diameter of a scale-free random graph
zbMATH Open document ID: 1047.05038
author: Béla Bollobás
author: Oliver Riordan
published in: Combinatorica
publication date: 2004-10-19T00:00:00Z
review text: There has recently been substantial interest in models of random graphs where vertices are added to the graph succesively and are more likely to be joined to vertices which are already of high degrees. Such graphs are thought to be good models of various \` real-world\'\, graphs such as the world-wide web, where pages are likely to have links to already popular sites such as Google. In \textit{A.-L. Barabási} and \textit{R. Albert} [Emergence of scaling in random networks, Science, 286, 509--512 (1999)] a particular model along these lines is (nearly) defined. They start with a small number \(m_{0}\) of vertices. Each vertex added subsequently is made adjacent to \(m\) different vertices already in the graph, and preferential attachment is ensured by saying the probability that the new vertex is adjacent to an existing vertex of degree \(d_{i}\) is \(d_{i}/\sum_{j}d_{j}\) (the sum over all vertices already in the graph). This will, after \(t\) steps, yield a graph with \(t+m_{0}\) vertices and \(mt\) edges. This is not an unambiguous description, but various papers have studied interpretations of this description and investigated the diameter (the maximum, over all pairs of vertices, of the distance between them in the graph). These papers suggest, on the basis of computer experiments, that the diameter should typically be about \(C\log(n)\) where \(C\) is a constant and \(n\) the number of vertices. This appears to be regarded, in many such papers, as surprisingly small: the authors of the paper under review point out some reasons why it is actually surprisingly large. In the paper under review, the authors define a precise form of the Barabási-Albert model. We omit the details of how it is made precise, merely noting that at time \(n\) the random graph \(G^{n}_{m}\) produced has \(n\) vertices, that (for \(n\) large) most vertices do indeed have degree \(m\), and that \(G^{n}_{m}\) can be obtained from \(G_{1}^{mn}\) by identifying vertices \(1,2,\dots, m\) of a \…
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 2108686
zbMATH Keywords: scale-free random graph
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: s00493-004-0002-2
OpenAlex ID: W2061118827
DOI: 10.1007/S00493-004-0002-2
description: scientific article; zbMATH DE number 2108686