Random networks with concave preferential attachment rule (Q2431083)

The authors introduce a random network model which relies on the preferential attachment rule. To be more specific, the vertices arrive one by one and when a new vertex \(n+1\) arrives, it is attached to each of the existing vertices independently with probability \(f(\text{in-degree})/n\). The main property of the function \(f\) is some kind of concavity. That is, for each non-negative integer \(k\), it satisfies \(f(k+1) - f(k) \leq \gamma\), where \(\gamma > 0\) is independent of \(k\). The authors determine the typical degree sequence of the random graph that is created. Further, they determine the existence of hubs in this random network. Thereafter, they focus on the case where \(f(k)= \gamma k + \beta\), and determine the critical condition, which depends on \(\gamma\) and \(\beta\), for the almost sure existence of a giant component. They also provide a general result for the case where \(f\) is nonlinear. The robustness of the random graph is also studied, when the graph undergoes an edge percolation process with \(p\) being the probability an edge is retained. They provide the critical value of \(p\), so that if \(p\) exceeds this then a giant component is left after the percolation process. Finally, they determine the typical distance between two randomly chosen vertices of the giant component of the random graph and they find that this is with high probability of order \(\log \log n\). That is, this random graph forms an \textit{ultrasmall world}. Regarding the clustering coefficient, the authors comment that their model exhibits relatively low clustering compared to that empirically found in real-world networks.