Search

Common models for random graphs, such as Erdős-Rényi and Kronecker graphs, correspond to generating random adjacency matrices where each entry is nonzero based on a large matrix of probabilities. Generating an instance of a random graph based on these models is easy, although ineficient, by ipping biased coins (i.e., sampling binomial random variables) for each possible edge. This process is ineficient because most large graph models correspond to sparse graphs where the vast majority of coin ips will result in no edges. We describe some not entirely well-known, but not entirely unknown, techniques that will enable us to sample a graph by nding only the coin ips that will produce edges. Our analogies for these procedures are ball-dropping, which is easier to implement, but may need extra work due to duplicate edges, and grass-hopping, which results in no duplicated work or extra edges. Grass-hopping does this using geometric random variables. In order to use this idea for complex probability matrices such as those in Kronecker graphs, we decompose the problem into three steps, each of which is an independently useful computational primitive: (i) enumerating nondecreasing sequences; (ii) unranking multiset permutations; and (iii) decoding and encoding z-curve and Morton codes and permutations. The third step is the result of a new connection between repeated Kronecker product operations and Morton codes. Throughout, we draw connections to ideas underlying applied math and computer science, including coupon collector problems. [ABSTRACT FROM AUTHOR]