2018/10/03 by Hüseyin Acan, Acan, Hüseyin, Boris Pittel +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #05C80 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Opportunistic and Delay-Tolerant Networks #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1810.02041
openalex publication_date 2018/10/03 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
A uniform attachment graph (with parameter k), denoted Gn,k in the\npaper, is a random graph on the vertex set [n], where each vertex v makes\nk selections from [v-1] uniformly and independently, and these selections\ndetermine the edge set. We study several aspects of this graph. Our motivation\ncomes from two similarly constructed, well-studied random graphs: k-out\ngraphs and preferential attachment graphs. In this paper, we find the\nasymptotic distribution of its minimum degree and connectivity, and study the\nexpansion properties of Gn,k to show that the conductance of Gn,k is\nof order (\log n)-1. We also study the bootstrap percolation on Gn,k,\nwhere, each vertex is either initially infected with probability p,\nindependently of others, or gets infected later as a result of having r\ninfected neighbors at some point. We show that, for 2\≤ r\≤ k-1, if p\≪\n(\log n)-r/(r-1), then, with probability approaching 1, the process ends\nbefore all vertices get infected. On the other hand, if p\≥ \ω(\log\nn)-r/(r-1), where \ω is a certain very slowly growing function, then\nall the vertices get infected with probability approaching 1.\n