共查询到20条相似文献,搜索用时 15 毫秒
1.
Zbigniew Palka 《Journal of Graph Theory》1987,11(2):121-134
Let G* be a simple undirected graph on n labeled vertices. A general approach to the investigation of the probability distribution of extreme degrees in a random subgraph of G* is given. As an example of the application of the method, we consider the case when G* is a complete bipartite graph. 相似文献
2.
Remco van der Hofstad Gerard Hooghiemstra Piet Van Mieghem 《Random Structures and Algorithms》2005,27(1):76-123
In this paper we study a random graph with N nodes, where node j has degree Dj and {Dj} are i.i.d. with ?(Dj ≤ x) = F(x). We assume that 1 ? F(x) ≤ cx?τ+1 for some τ > 3 and some constant c > 0. This graph model is a variant of the so‐called configuration model, and includes heavy tail degrees with finite variance. The minimal number of edges between two arbitrary connected nodes, also known as the graph distance or the hopcount, is investigated when N → ∞. We prove that the graph distance grows like logν N, when the base of the logarithm equals ν = ??[Dj(Dj ? 1)]/??[Dj] > 1. This confirms the heuristic argument of Newman, Strogatz, and Watts [Phys Rev E 64 (2002), 026118, 1–17]. In addition, the random fluctuations around this asymptotic mean logν N are characterized and shown to be uniformly bounded. In particular, we show convergence in distribution of the centered graph distance along exponentially growing subsequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 相似文献
3.
We study random graphs with an i.i.d. degree sequence of which the tail of the distribution function
is regularly varying with exponent
. In particular, the degrees have infinite mean. Such random graphs can serve as models for complex networks where degree
power laws are observed. The minimal number of edges between two arbitrary nodes, also called the graph distance or the hopcount,
is investigated when the size of the graph tends to infinity. The paper is part of a sequel of three papers. The other two
papers study the case where
, and
, respectively. The main result of this paper is that the graph distance for
converges in distribution to a random variable with probability mass exclusively on the points
and
. We also consider the case where we condition the degrees to be at most
for some
, where
is the size of the graph. For fixed
and
such that
, the hopcount converges to
in probability, while for
, the hopcount converges to the same limit as for the unconditioned degrees. The proofs use extreme value theory.
AMS 2000 Subject Classifications Primary—60G70; Secondary—05C80 相似文献
4.
Svante Janson 《Random Structures and Algorithms》2020,56(4):1070-1116
We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph. 相似文献
5.
We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ1 (λ2) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ1 = λ2, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ1 ≠ λ2, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence. 相似文献
6.
We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by ?erný and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs. 相似文献
7.
It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph. 相似文献
8.
9.
10.
11.
Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
12.
Yilun SHANG 《Frontiers of Mathematics in China》2012,7(1):117-124
Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability
generating function for degrees of G
active(n, m, p) and G
passive(n, m, p), which are generated by a random bipartite graph G*(n, m, p) on n + m vertices. 相似文献
13.
In 2007, we introduced a general model of sparse random graphs with (conditional) independence between the edges. The aim of this article is to present an extension of this model in which the edges are far from independent, and to prove several results about this extension. The basic idea is to construct the random graph by adding not only edges but also other small graphs. In other words, we first construct an inhomogeneous random hypergraph with (conditionally) independent hyperedges, and then replace each hyperedge by a (perhaps complete) graph. Although flexible enough to produce graphs with significant dependence between edges, this model is nonetheless mathematically tractable. Indeed, we find the critical point where a giant component emerges in full generality, in terms of the norm of a certain integral operator, and relate the size of the giant component to the survival probability of a certain (non‐Poisson) multi‐type branching process. While our main focus is the phase transition, we also study the degree distribution and the numbers of small subgraphs. We illustrate the model with a simple special case that produces graphs with power‐law degree sequences with a wide range of degree exponents and clustering coefficients. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 269–323, 2011 相似文献
14.
《Discrete Mathematics》2007,307(3-5):386-392
In a series of papers, we have classified the complexity of list homomorphism problems. Here, we investigate the effect of restricting the degrees of the input graphs. It turns out that the complexity does not change (except when the degree bound is two). We obtain similar results on restricting the size of the lists.We contrast these results with facts about variants of the list homomorphism problem, where restricting the degrees can have an important effect on the complexity. 相似文献
15.
David Aldous 《Random Structures and Algorithms》1990,1(4):383-402
Grow a tree on n vertices by starting with no edges and successively adding an edge chosen uniformly from the set of possible edges whose addition would not create a cycle. This process is closely related to the classical random graph process. We describe the asymptotic structure of the tree, as seen locally from a given vertex. In particular, we give an explicit expression for the asymptotic degree distribution. Our results an be applied to study the random minimum-weight spanning tree question, when the edge-weight distribution is allowed to vary almost arbitrarily with n. 相似文献
16.
17.
18.
Tomasz
uczak 《Discrete Applied Mathematics》1991,30(2-3):213-219
It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G(n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − )n log c/c, provided c(n) = (n − 1)p(n)→∞. 相似文献
19.
A graph H is Ks ‐saturated if it is a maximal Ks ‐free graph, i.e., H contains no clique on s vertices, but the addition of any missing edge creates one. The minimum number of edges in a Ks ‐saturated graph was determined over 50 years ago by Zykov and independently by Erd?s, Hajnal and Moon. In this paper, we study the random analog of this problem: minimizing the number of edges in a maximal Ks ‐free subgraph of the Erd?s‐Rényi random graph G (n, p ). We give asymptotically tight estimates on this minimum, and also provide exact bounds for the related notion of weak saturation in random graphs. Our results reveal some surprising behavior of these parameters. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 169–181, 2017 相似文献
20.
Threshold probabilities for the existence in a random graph on n vertices of a graph isomorphic to a given graph of order Cn and average degree at least three are investigated. In particular it is proved that the random graph G(n, p) on n vertices with edge probability contains a square grid on En/2 vertices. © 1994 John Wiley & Sons, Inc. 相似文献