The scaling window for a random graph with a given degree sequence

We consider a random graph on a given degree sequence D, satisfying certain conditions. Molloy and Reed defined a parameter Q = Q(D) and proved that Q = 0 is the threshold for the random graph to have a giant component. We introduce a new parameter R = R( \begin{align*}\mathcal {D}\end{align*}) and prove that if |Q| = O(n^‐1/3R^2/3) then, with high probability, the size of the largest component of the random graph will be of order Θ(n^2/3R^‐1/3). If |Q| is asymptotically larger than n^‐1/3R^2/3 then the size of the largest component is asymptotically smaller or larger than n^2/3R^‐1/3. Thus, we establish that the scaling window is |Q| = O(n^‐1/3R^2/3). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The degree sequence of a scale‐free random graph process

Recently, Barabási and Albert [2] suggested modeling complex real‐world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In [2] and, with Jeong, in [3], Barabási and Albert suggested that after many steps the proportion P(d) of vertices with degree d should obey a power law P(d)αd^?γ. They obtained γ=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that γ=3. Here we obtain P(d) asymptotically for all d≤n^1/15, where n is the number of vertices, proving as a consequence that γ=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279–290, 2001     

The number of graphs and a random graph with a given degree sequence

We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d₁,…,d_n). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

The degree of a typical vertex in generalized random intersection graph models

In this paper we consider the degree of a typical vertex in two models of random intersection graphs introduced in [E. Godehardt, J. Jaworski, Two models of random intersection graphs for classification, in: M. Schwaiger, O. Opitz (Eds.), Exploratory Data Analysis in Empirical Research, Proceedings of the 25th Annual Conference of the Gesellschaft für Klassifikation e.V., University of Munich, March 14-16, 2001, Springer, Berlin, Heidelberg, New York, 2002, pp. 67-81], the active and passive models. The active models are those for which vertices are assigned a random subset of a list of objects and two vertices are made adjacent when their subsets intersect. We prove sufficient conditions for vertex degree to be asymptotically Poisson as well as closely related necessary conditions. We also consider the passive model of intersection graphs, in which objects are vertices and two objects are made adjacent if there is at least one vertex in the corresponding active model “containing” both objects. We prove a necessary condition for vertex degree to be asymptotically Poisson for passive intersection graphs.     

Vertices of given degree in a random graph

This paper concerns the degree sequence d₁ ≥ d₂ ≥ … ≥ d_n of a randomly labeled graph of order n in which the probability of an edge is p(n) ≦ 1/2. Among other results the following questions are answered. What are the values of p(n) for which d₁, the maximum degree, is the same for almost every graph? For what values of p(n) is it true that d₂ > d₂ for almost every graph, that is, there is a unique vertex of maximum degree? The answers are (essentially) p(n) = o(logn/n/n) and p(n)n/logn → ∞. Also included is a detailed study of the distribution of degrees when 0 < lim n p(n)/log n ≦ lim n p(n)/log n < ∞.     

The cores of random hypergraphs with a given degree sequence

We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d₁…,d_n), maximum degree Δ = o(n^1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n^2/3 Δ^4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004     

The realization graph of a degree sequence with majorization gap 1 is Hamiltonian

It is known that the degree sequences of threshold graphs are characterized by the property that they are not majorized strictly by any degree sequence. Consequently every degree sequence d can be transformed into a threshold sequence by repeated operations consisting of subtracting I from a degree and adding 1 to a larger or equal degree. The minimum number of these operations required to transform d into a threshold sequence is called the majorization gap of d. A realization of a degree sequence d of length n is a graph on the vertices 1, …, n, where the degree of vertex i is d_i. The realization graph %plane1D;4A2;(d) of a degree sequence d has as vertices the realizations of d, and two realizations are neighbors in %plane1D;4A2;(d) if one can be obtained from the other by deleting two existing edges [a, b], [c, d] and adding two new edges [a, d]; [b, c] for some distinct vertices a, b, c, d. It is known that %plane1D;4A2;(d) is connected. We show that if d has a majorization gap of 1, then %plane1D;4A2;(d) is Hamiltonian.     

Sandwiching random graphs: universality between random graph models

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on G_d(n).     

The simple random walk and max‐degree walk on a directed graph

We bound total variation and L^∞ mixing times, spectral gap and magnitudes of the complex valued eigenvalues of general (nonreversible nonlazy) Markov chains with a minor expansion property. The resulting bounds for the (nonlazy) simple and max‐degree walks on a (directed) graph are of the optimal order. It follows that, within a factor of two or four, the worst case of each of these mixing time and eigenvalue quantities is a walk on a cycle with clockwise drift. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the number of vertices of given degree in a random graph

This note can be treated as a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G ∈ ??(n, p) asymptotically has a normal distribution.     

The connectivity threshold for the min‐degree random graph process

Let ??_n = {G_min(n, M)}_M≥0 denote a min‐degree random multigraph process in which G_min(n, M + 1) is obtained from G_min(n, M) by connecting a randomly chosen vertex of a minimum degree with another vertex of the multigraph. We study the probability that the random multigraph G_min(n, M) is connected. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Vertex degree of random geometric graph on exponentially distributed points

In this article, we consider exponential random geometric graph, in d-dimensional space (d≥2). The main results are almost-sure asymptotic rates of convergence/divergence for the maximum and minimum vertex degrees of graph, when edge distance varies with the number of vertices.     

SIR epidemics on random graphs with a fixed degree sequence

Let Δ > 1 be a fixed positive integer. For \begin{align*}{\textbf{ {z}}} \in \mathbb{R}_+^\Delta\end{align*} let G_z be chosen uniformly at random from the collection of graphs on ∥z∥₁n vertices that have z_in vertices of degree i for i = 1,…,Δ. We determine the likely evolution in continuous time of the SIR model for the spread of an infectious disease on G_z, starting from a single infected node. Either the disease halts after infecting only a small number of nodes, or an epidemic spreads to infect a linear number of nodes. Conditioning on the event that more than a small number of nodes are infected, the epidemic is likely to follow a trajectory given by the solution of an associated system of ordinary differential equations. These results also give the likely number of nodes infected during the course of the epidemic and the likely length in time of the epidemic. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The insulation sequence of a graph

In a graph G, a k-insulated set S is a subset of the vertices of G such that every vertex in S is adjacent to at most k vertices in S, and every vertex outside S is adjacent to at least k+1 vertices in S. The insulation sequencei₀,i₁,i₂,… of a graph G is defined by setting i_k equal to the maximum cardinality of a k-insulated set in G. We determine the insulation sequence for paths, cycles, fans, and wheels. We also study the effect of graph operations, such as the disjoint union, the join, the cross product, and graph composition, upon k-insulated sets. Finally, we completely characterize all possible orderings of the insulation sequence, and prove that the insulation sequence is increasing in trees.     

The neighborhood complex of a random graph

For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well-known result of Lovász that if ‖N[G]‖ is k-connected, then the chromatic number of G is at least k+3.We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(logd), compared to the expected dimension d of the complex itself.