The phase transition in inhomogeneous random graphs

By Béla Bollobás, Svante Janson, Oliver Riordan. Random Struct. Algorithms, 2005

844 citations recorded by the source corpus.

The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models.

Subfields: Computational Theory and Mathematics, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/926898ef1ccc9ce34c868271dd5556560030900b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Random Graphs and Complex Networks (2016, methodology): “In [54], also the choices p ij (κn) = 1− e nij, (9.”
Graphons, cut norm and distance, couplings and rearrangements (2010, neutral): “, [9] and [21].”
Community detection and stochastic block models: recent developments (2017, background): “…under the SBM terminology in the context of social networks in the machine learning and statistics literature [93], while the model is typically called the planted partition model in theoretical computer science [49, 119, 41], and the inhomogeneous random graph in the mathematics literature [40].”
Scale-free percolation (2011, neutral): “In the random graph setting, this is established in [11,22].”
Universality for first passage percolation on sparse random graphs (2012, result): “In a forthcoming paper [11], we will show that, due to the flexible choice of degree distribution, our results carry over to various other random graph models, including rank-1 inhomogeneous random graphs as introduced in [13].”
An almost-bijective proof of an asymptotic property of partitions (2007, methodology): “Our aim in this paper is to show that Penrose’s result is a simple consequence of the main (and very general) results of [ 3 ].”
Spectral redemption in clustering sparse networks (2013, background): “[19] Bollobas B, Svante J and Oliver R (2007).”
Distances in Random Graphs with Finite Mean and Infinite Variance Degrees (2005, background): “The most general version of this model can be found in [4].”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, background): “The Erdős-Rényi (ER) model is one of the simplest generative models for random graphs, but this simplicity belies astonishingly rich behavior ([6], [15]).”
Percolation on dense graph sequences. (2007, neutral): “The Annals of Probability 2010, Vol. 38, No. 1, 150–183 DOI: 10.1214/09-AOP478 © Institute of Mathematical Statistics, 2010”
A Survey of Statistical Network Models (2009, methodology): “[45], it is tractable enough to allow the analysis of the giant component in (K,α) space, by leveraging the branching process strategy developed by Durrett [91] (see the appendix at the end of the chapter).”
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs (2018, methodology): “The random graph G is usually called the stochastic block model (SBM) or inhomogeneous random graph; see Bollobás, Janson and Riordan [5] and Holland, Laskey and Leinhardt [13].”
A nonparametric view of network models and Newman–Girvan and other modularities (2009, neutral): “We define asymptotic consistency of a sequence of assignments ĉ by P[ĉ = c] → 1 [4] as n → ∞.”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “The phrase “inhomogeneous random graph” comes from a paper by Bollobas, Janson and Rior-dan [11] where the above model was studied in the range p = Θ (1 /n ) with background spaces more general than [0 , 1].”
Asymptotic Normality of Maximum Likelihood and its Variational Approximation for Stochastic Blockmodels (2012, background): “The stochastic blockmodel is a special case of a more general latent variable model, considered by various authors [Hoﬀ, Raftery and Handcock (2002), Bickel and Chen (2009), Bollob´as, Janson and Riordan (2007)].”
Reconstruction and estimation in the planted partition model (2012, background): “[4], who show a Poisson limit for cycle counts in more general inhomogeneous graphs, which have continuous edge labels and a kernel that defines edge probabilities; our special case is recovered by taking the obvious two-valued kernel in [4, Theorem 17.”
A tensor approach to learning mixed membership community models (2013, background): “, Bollobás et al. [2007], Lovász [2009]) and are generalizations of the stochastic block model. Here, the probability of an edge between any two nodes is characterized by a general function (rather than by a k×k matrix as in the stochastic block model with k blocks). Note that the mixed membership m”