Paper detail

Distance between two random k-out digraphs, with and without preferential attachment

A random k-out mapping (digraph) on [n] is generated by choosing k random images of each vertex one at a time, subject to a "preferential attachment" rule: the current vertex selects an image i with probability proportional to a given parameter α= α(n) plus the number of times i has already been selected. Intuitively, the larger αgets, the closer the resulting k-out mapping is to the uniformly random k-out mapping. We prove that α= Θ(n^{1/2}) is the threshold for αgrowing "fast enough" to make the random digraph approach the uniformly random digraph in terms of the total variation distance. We also determine an exact limit for this distance for α= βn^{1/2}.