The connected components

 

3 The connected components

 

Molloy and Reed [1995] showed that for a random graph with vertices of degree i, where  are non-negative values which sum to 1, the giant component emerges when

So long as the maximum degree is less than   They also show that almost surely there is no giant component when and maximum degree less than

Here we compute Q for our graphs.

We are thus led to consider the value  which is a solution to

If

We first summarize the results here:

1.   When  the random graph a. s. has no giant component. When  there is almost surely a unique giant component.

2.   When   almost surely the second largest components have size  there is almost surely a component of size x.

3.     When  almost surely the second largest components are of sizeFor any  there is almost surely a component of size x.

4.    When  the second largest components are a. s. of size  The graph is almost surely not connected.

5.      When 0 <β< 1, the graph is almost surely connected.

6.      For β = β0 = 3.47875 ..., this is a very complicated case. It corresponds to the double jump of random graph G(n, p) with p = 1 n. For β = 1, there is a nontrivial probability for either cases that the graph is connected or disconnected.

7.    For  this case is complicated case. It corresponds to the double jump of random graph  with .

8.    For , there is a nontrivial probability for either cases that the graph is connected or disconnected.

We remark that for β > 8, Molloy and Reed’s result immediately implies that almost surely there is no giant component. When β ≤ 8, additional analysis is needed to deal with the degree constraints. We will prove in Theorem 4.2 that almost surely there is no giant component when

 In section 5, we will deal with the range  We will show theorem5.1 that almost surely there is a unique giant component when furthermore, we will determine the size of the second largest components within a constant factor.

Comments

Post a Comment

Popular posts from this blog

General Statistical Models

  General Statistical Models The time has come to learn some theory. This is a preview of STAT 5101–5102. We don’t need to learn much theory. We will proceed with the general strategy of all introductory statistics: don’t derive anything, just tell you stuff. 3.1  Probability Models 3.1.1  Kinds of Probability Theory There are two kinds of probability theory. There is the kind you will learn in STAT 5101-5102 (or 4101–4102, which is more or less the same except for leaving out the multivariable stuff). The material covered goes back hundreds of years, some of it discovered in the early 1600’s. And there is the kind you would learn in MATH 8651–8652 if you could take it, which no undergraduate does (it is a very hard Ph. D. level math course). The material covered goes back to 1933. It is all “new math”. These two kinds of probability can be called  classical  and  measure-theoretic , respectively. The old kind (classical) is still very useful. For every 1000 people who know a lot of pr
Read more

Solution of a linear system

Image
  Solution of a linear system [ edit ] The steepest descent algorithm applied to the  Wiener filter [11] Gradient descent can be used to solve a system of linear equations � � − � = 0 reformulated as a quadratic minimization problem. If the system matrix  �  is real  symmetric  and  positive-definite , an objective function is defined as the quadratic function, with minimization of � ( � ) = � � � � − 2 � � � , so that ∇ � ( � ) = 2 ( � � − � ) . For a general real matrix  � ,  linear least squares  define � ( � ) = ‖ � � − � ‖ 2 . In traditional linear least squares for real  �  and  �  the  Euclidean norm  is used, in which case ∇ � ( � ) = 2 � � ( � � − � ) . The  line search  minimization, finding the locally optimal step size  �  on every iteration, can be performed analytically for quadratic functions, and explicit formulas for the locally optimal  �  are known. [5] [12] For example, for real  symmetric  and  positive-definite  matrix  � , a simple algorithm can be as follows, [5
Read more