2018/03/29 by Jan Dreier, Dreier, Jan, Philipp Kuinke +3
Computer Science · Physics and Astronomy · #Caching and Content Delivery #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.1803.11114
openalex publication_date 2018/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Preferential attachment graphs are random graphs designed to mimic properties of typical real world networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We use improved concentration bounds for vertex degrees to show that preferential attachment graphs contain asymptotically almost surely (a.a.s.) a one-subdivided clique of size at least (log n)1/4. Therefore, preferential attachment graphs are a.a.s somewhere-dense. This implies that algorithmic techniques developed for sparse graphs are not directly applicable to them. The concentration bounds state: Assuming that the exact degree d of a fixed vertex (or set of vertices) at some early time t of the random process is known, the probability distribution of d is sharply concentrated as the random process evolves if and only if d is large at time t.