Coupling scale-free and classical random graphs. (English) Zbl 1061.05084

Bollobás, Béla; Riordan, Oliver

Internet Math. 1, No. 2, 215-225 (2004).

There has recently been much interest in so-called scale free graphs, in which at each discrete time point a new vertex \(v\) is added to a graph, and then \(v\) is joined to existing vertices, with probabilities proportional to the degrees of the existing vertices. This is meant to be a reasonable model of (say) the World Wide Web, where a new site is more likely to have a link to a popular site such as Google or a national rail timetable, than to an obscure site. There is a large amount of evidence that many \` real-world\' networks have similar properties.
One of the most widely known attempts to develop this idea was introduced by Barabási and Albert. Their model is not unambiguously defined, so the authors instead use their so-called LCD model \(G_{m}^{(n)}\) on \(n\) vertices \(1,2,\dots, n\), which is one way of making Barabási and Albert’s idea precise. We omit the details of how the LCD graph is constructed, merely noting that in \(G_{1}^{(t)}\) each new vertex \(v\), when put in the graph at time \(t\), is joined to one earlier vertex, and the choice of vertex is proportional to the degrees of the vertices in the graph at time \(t-1\): and \(G_{m}^{(t)}\) is formed from a \(G_{1}^{(mt)}\) by identifying the first \(m\) vertices to form the first vertex, the next \(m\) to form the second, and so on. \(m\) is the number of edges from each vertex when it is first inserted: note that loops may arise.
The basic aim of the paper under review is to investigate the question of what proportion of the vertices in an LCD graph have to be removed to break the graph into small pieces: more formally, to avoid leaving any component whose order is linear in the total number of vertices of the graph. The first main result is the existence of an absolute constant \(m_{0}\) such that, for all \(m\geq m_{0}\), every induced subgraph of \(G_{m}^{(n)}\) on \(\geq 10n\log(m)/m\) vertices contains a component of order at least \(2n\log(m)/m\). This shows that we must delete all but a proportion constant times \(\log(m)/m\) of the vertices to ensure there is no component whose order is linear in the number of vertices. The second result is that (in addition to \(m_{0}\)) there is a further absolute constant \(c>0\) such that \(G_{m}^{(n)}\) contains an independent set of order \(cn\log(m)/m\): this of course shows that the first result is best possible, up to a constant multiple, against general attacks (i.e. attempts to disconnect the graph).
The interesting proof technique is to link the LCD model to a (on the surface very different) random graph, namely the classical Erdős-Rényi model \(G(n,p(n))\) where each edge arises with probability \(p(n)\) independent of all other edges. Because of the large amount of independence in it, the Erdős-Rényi model is mathematically tractable. The first key result is that, if \(\eta<1/2\) is fixed, there exist constants \(A,c>0\), independent of \(m\), such that for each fixed \(m\) we may construct coupled random graphs \(G_{1}\) and \(G_{2}\) on the same vertex set such that \[ G_{1}\sim G_{m}^{(n)},\,\,G_{2}\sim G(n,\eta m/n),\,\text{~and~\textbf{whp}~}e(G_{2}\backslash G_{1})\leq Ae^{-cm}n. \] Here \(e(G_{2}\backslash G_{1})\) is the number of edges in \(G_{2}\) but not in \(G_{1}\), and saying that an event happens whp means that the event happens with probability tending to 1 as \(n\rightarrow\infty\). Putting it another way, we can couple \(G_{n}^{(m)}\) with a \(G(n,p)\) (which, for \(\eta\) close to 1/2, will contain approximately one quarter the number of edges of the \(G_{m}^{(n)}\)) in such a way that most edges of the \(G(n,p)\) are also in the \(G_{m}^{(n)}\).
The second key coupling result is that if \(\varepsilon>0\) is given there is a constant \(C>0\) (independent of \(m\)) such that for each fixed \(m\) we can construct coupled random graphs \(G_{1}\) and \(G_{2}\) on the same vertex set \(\{1,2,\ldots n\}\) such that \[ G_{1}\sim G_{m}^{(n)},\;G_{2}\sim G(n,Cm/n),\text{~and~\textbf{whp}~}G_{2}\text{ contains }G_{1}\backslash V \] for some set of vertices \(V\) such that \(| \{i\in V: i\geq \varepsilon n\}| \leq \varepsilon n/m\). That is, if we accept a weaker constant than in the first result, we can control not only the number of vertices deleted, but how they are spread out. The proofs of both results are by building the two graphs \(G_{1}\) and \(G_{2}\) up gradually, and besides careful study of the graph processes do not need technical tools beyond the Chernoff bounds, an earlier result about degrees in the LCD graphs and (a special case of) results of Frieze on the independence number of \(G(n,a/n)\).

Reviewer: David B. Penman (Colchester)

MSC:

05C80

Random graphs (graph-theoretic aspects)

Keywords:

random graph; scale-free graph; coupling