Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCoin-flipping, ball-dropping, and grass-hopping for generating random graphs from matrices of edge probabilities
380
0
0.0
(
0
)
Added by
David Gleich
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Common models for random graphs, such as ErdH{o}s-R{e}nyi and Kronecker graphs, correspond to generating random adjacency matrices where each entry is non-zero based on a large matrix of probabilities. Generating an instance of a random graph based on these models is easy, although inefficient, by flipping biased coins (i.e. sampling binomial random variables) for each possible edge. This process is inefficient because most large graph models correspond to sparse graphs where the vast majority of coin flips 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 finding only the coin flips 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 on complex probability matrices such as those in Kronecker graphs, we decompose the problem into three steps, each of which are independently useful computational primitives: (i) enumerating non-decreasing 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.
rate research
Read More
We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{max}=O(m^{1/4-tau})$, our algorithm generates almost uniform random graphs with that degree sequence in time $O(m,d_{max})$ where $m=f{1}{2}sum_id_i$ is the number of edges in the graph and $tau$ is any positive constant. The fastest known algorithm for uniform generation of these graphs McKay Wormald (1990) has a running time of $O(m^2d_{max}^2)$. Our method also gives an independent proof of McKays estimate McKay (1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of $d_{max}=O(m^{1/4-tau})$. Moreover, we show that for $d = O(n^{1/2-tau})$, our algorithm can generate an asymptotically uniform $d$-regular graph. Our results improve the previous bound of $d = O(n^{1/3-tau})$ due to Kim and Vu (2004) for regular graphs.
Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias $alpha$, as a function of data she receives from $p$ sources; she seeks privacy from any coalition of $r$ of them. We show: If $p/2 leq r < p$, the bias can be any rational number and nothing else; if $0 < r < p/2$, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the $r=1$ case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.
We consider a natural model of inhomogeneous random graphs that extends the classical ErdH os-Renyi graphs and shares a close connection with the multiplicative coalescence, as pointed out by Aldous [AOP 1997]. In this model, the vertices are assigned weights that govern their tendency to form edges. It is by looking at the asymptotic distributions of the masses (sum of the weights) of the connected components of these graphs that Aldous and Limic [EJP 1998] have identified the entrance boundary of the multiplicative coalescence, which is intimately related to the excursion lengths of certain Levy-type processes. We, instead, look at the metric structure of these components and prove their Gromov-Hausdorff-Prokhorov convergence to a class of random compact measured metric spaces that have been introduced in a companion paper. Our asymptotic regimes relate directly to the general convergence condition appearing in the work of Aldous and Limic. Our techniques provide a unified approach for this general critical regime, and relies upon two key ingredients: an encoding of the graph by some Levy process as well as an embedding of its connected components into Galton-Watson forests. This embedding transfers asymptotically into an embedding of the limit objects into a forest of Levy trees, which allows us to give an explicit construction of the limit objects from the excursions of the Levy-type process. The mains results combined with the ones in the other paper allow us to extend and complement several previous results that had been obtained via regime-specific proofs, for instance: the case of ErdH os-Renyi random graphs obtained by Addario-Berry, Goldschmidt and B. [PTRF 2012], the asymptotic homogeneous case as studied by Bhamidi, Sen and Wang [PTRF 2017], or the power-law case as considered by Bhamidi, Sen and van der Hofstad [PTRF 2018].
We study various methods to generate ensembles of random density matrices of a fixed size N, obtained by partial trace of pure states on composite systems. Structured ensembles of random pure states, invariant with respect to local unitary transformations are introduced. To analyze statistical properties of quantum entanglement in bi-partite systems we analyze the distribution of Schmidt coefficients of random pure states. Such a distribution is derived in the case of a superposition of k random maximally entangled states. For another ensemble, obtained by performing selective measurements in a maximally entangled basis on a multi--partite system, we show that this distribution is given by the Fuss-Catalan law and find the average entanglement entropy. A more general class of structured ensembles proposed, containing also the case of Bures, forms an extension of the standard ensemble of structureless random pure states, described asymptotically, as N to infty, by the Marchenko-Pastur distribution.
Any modern network inference paradigm must incorporate multiple aspects of network structure, including information that is often encoded both in vertices and in edges. Methodology for handling vertex attributes has been developed for a number of network models, but comparable techniques for edge-related attributes remain largely unavailable. We address this gap in the literature by extending the latent position random graph model to the line graph of a random graph, which is formed by creating a vertex for each edge in the original random graph, and connecting each pair of edges incident to a common vertex in the original graph. We prove concentration inequalities for the spectrum of a line graph, and then establish that although naive spectral decompositions can fail to extract necessary signal for edge clustering, there exist signal-preserving singular subspaces of the line graph that can be recovered through a carefully-chosen projection. Moreover, we can consistently estimate edge latent positions in a random line graph, even though such graphs are of a random size, typically have high rank, and possess no spectral gap. Our results also demonstrate that the line graph of a stochastic block model exhibits underlying block structure, and we synthesize and test our methods in simulations for cluster recovery and edge covariate inference in stochastic block model graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
