A Random Graph Model for Power Law Graphs
This paper introduces a random graph model of the world wide web. Fix \(\alpha\) and \(\beta\), and a distribution \(P(\alpha, \beta)\) assigns a uniform probability to a class of multigraphs such that, for any such multigraph, the number of vertices of a degree \(d\) is \(\lfloor e^{\alpha}/d^{\beta} \rfloor\). This model approximates the observed structure of the world wide web in some aspects. In studying the asymptotics of this model, \(\beta > 0\) is fixed, while \(\alpha\) is permitted to grow (and as \(\alpha\) increases, so does the expected order and size of the multidigraphs). The results in this paper concern the sizes of the connected components of random graphs in the spaces \(P(\alpha, \beta)\), for various \(\beta\), as \(\alpha \to \infty\). (1) If \(\beta > 3.47875 \ldots\), then a.s.{} there is no giant component. They present estimates of the sizes of the small components. (2) If \(\beta < 3.47875 \ldots\), then a.s.{} the graph has a giant component. (3) If \(2 < \beta < 3.47875 \ldots\), the second largest component is a.s.{} log-sized; if \(\beta = 2\), the second largest component is a.s.{} log/loglog-sized; if \(2 > \beta > 1\), the second component is a.s.{} size \(\Theta(1)\). (4) If \(\beta < 1\), then the graph is a.s.{} connected. The proofs rely on martingale arguments. While this model and its properties are interesting, expository problems occasionally make the meaning of passages in the proofs difficult to ascertain.
- A critical point for random graphs with a given degree sequence
- A random graph model for massive graphs
- On the strength of connectedness of a random graph
- Relaxing the uniformity and independence assumptions using the concept of fractal dimension
- The asymptotic connectivity of labelled regular graphs
- The Size of the Giant Component of a Random Graph with a Given Degree Sequence
- Perturbation of coupling matrices and its effect on the synchronizability in arrays of coupled chaotic systems
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- MAX \(\kappa\)-cut and the inhomogeneous Potts spin Glass
- De-anonymization of heterogeneous random graphs in quasilinear time
- How likely is an LLD degree sequence to be graphical?
- Power-law partial correlation network models
- An algorithm generating random graphs with power law degree distributions
- Catching homologies by geometric entropy
- Networks of causal relationships in the U.S. stock market
- Greed is good for deterministic scale-free networks
- Percolation on complex networks: theory and application
- Ising model with invisible states on scale-free networks
- A tolerance-based heuristic approach for the weighted independent set problem
- Parameterized clique on inhomogeneous random graphs
- Activity maxima in some models of information networks with random weights and heavy tails
- On the hardness of optimization in power-law graphs
- On certain connectivity properties of the internet topology
- Mining market data: a network approach
- A web model with power law exponents less than 2
- On the mean distance in scale free graphs
- Evolving protein-protein interaction networks: a model based on duplication and mutation at different rates
- How to distribute antidote to control epidemics
- Minimum vertex cover in generalized random graphs with power law degree distribution
- A random graph model for massive graphs
- Techniques for analyzing dynamic random graph models of web-like networks: An overview
- scientific article; zbMATH DE number 5732563 (Why is no real title available?)
- ESTIMATION OF POWER-LAW EXPONENT OF DEGREE DISTRIBUTION USING MEAN VERTEX DEGREE
- Approximability of the vertex cover problem in power-law graphs
- A generalization of the Buckley-Osthus model for web graphs
- Identifying large robust network clusters via new compact formulations of maximum k-club problems
- New techniques for approximating optimal substructure problems in power-law graphs
- Modeling memory effects in activity-driven networks
- Information geometric methods for complexity
- Inapproximability of dominating set on power law graphs
- Some properties of random Apollonian networks
- Why do simple algorithms for triangle enumeration work in the real world?
- Modularity of Erdős-Rényi random graphs
- Power-law distribution of degree-degree distance: a better representation of the scale-free property of complex networks
- True scale-free networks hidden by finite size effects
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
- Bounds on the satisfiability threshold for power law distributed random SAT
- Approximation algorithm for partial positive influence problem in social network
- Modularity of Erdős-Rényi random graphs
- Activity maxima in random networks in the heavy tail case
- From heavy-tailed Boolean models to scale-free Gilbert graphs
- The phase transition in inhomogeneous random graphs
- Distances in random graphs with finite variance degrees
- Quasi‐random graphs with given degree sequences
- On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
- Thek-Core and Branching Processes
- The average distances in random graphs with given expected degrees
- Spectra of random graphs with given expected degrees
- Satisfiability threshold for power law random 2-SAT in configuration model
- A random graph model for clustering graphs
- Differentially private graph publishing through noise-graph addition
- Generating large scale‐free networks with the Chung–Lu random graph model
- Navigational guidance -- a deep learning approach
- The winner takes it all but one
- Cliques in high-dimensional geometric inhomogeneous random graphs
- Analysis of the survival time of the SIRS process via expansion
- Scaling limits and generic bounds for exploration processes
- Strategic geometric graphs through mean field games
- Fine-grained complexity lower bounds for families of dynamic graphs
- On the minimum edge bisection of graph
- Computation of certain domination numbers of collaboration graphs
- Concentration and mean field approximation results for Markov processes on large networks
- Degree-corrected deep single graph generation
- Evolution of scale-free random graphs: Potts model formulation
- Distance in random graphs with infinite mean degrees
- Enumeration of graphs with a heavy-tailed degree sequence
- Statistical analysis of financial networks
This page was built for publication: A Random Graph Model for Power Law Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2729376)
