Sublinear Random Access Generators for Preferential Attachment Graphs
Sublinear Random Access Generators for Preferential Attachment Graphs
We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored …