Generating random networks without short cycles
From MaRDI portal
Abstract: Random graph generation is an important tool for studying large complex networks. Despite abundance of random graph models, constructing models with application-driven constraints is poorly understood. In order to advance state-of-the-art in this area, we focus on random graphs without short cycles as a stylized family of graphs, and propose the RandGraph algorithm for randomly generating them. For any constant k, when m=O(n^{1+1/[2k(k+3)]}), RandGraph generates an asymptotically uniform random graph with n vertices, m edges, and no cycle of length at most k using O(n^2m) operations. We also characterize the approximation error for finite values of n. To the best of our knowledge, this is the first polynomial-time algorithm for the problem. RandGraph works by sequentially adding edges to an empty graph with n vertices. Recently, such sequential algorithms have been successful for random sampling problems. Our main contributions to this line of research includes introducing a new approach for sequentially approximating edge-specific probabilities at each step of the algorithm, and providing a new method for analyzing such algorithms.
Recommendations
Cites work
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A sequential algorithm for generating random graphs
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- Algorithms, games, and the internet
- Bootstrap methods: another look at the jackknife
- Concentration of non‐Lipschitz functions and applications
- Constrainted graph processes
- Dynamic concentration of the triangle-free process
- Efficient importance sampling for binary contingency tables
- Finite-length analysis of low-density parity-check codes on the binary erasure channel
- Generating random graphs with large girth
- Generating random regular graphs
- Generating Random Regular Graphs Quickly
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 1559530 (Why is no real title available?)
- Modern Coding Theory
- On the size of a random maximal graph
- Poisson approximation for large deviations
- Random Graph Processes with Degree Restrictions
- Random maximalH-free graphs
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- The Cℓ‐free process
- The asymptotic number of labeled graphs with given degree sequences
- The early evolution of the \(H\)-free process
- The evolution of social and economic networks.
- The Structure and Function of Complex Networks
- Triangle-free subgraphs in the triangle-free process
Cited in
(8)- Generating random networks from a given distribution
- Limitations of Chung Lu random graph generation
- Mathematical programming approaches for classes of random network problems
- Generating random graphs with large girth
- Parallel and I/O-efficient randomisation of massive networks using global curveball trades
- Coin-flipping, Ball-dropping, and Grass-hopping for generating random graphs from matrices of edge probabilities
- Random graph generation using multiple switches of edges
- Generating constrained random graphs using multiple edge switches
This page was built for publication: Generating random networks without short cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4971560)
