A RANDOM GRAPH MODEL

 A RANDOM GRAPH MODEL 

LEMMA:1.1

A random graph G_(n,p), given that its number of edges is m, is equally likely to be one of the (((n¦2))¦m) graph that have m edges.

Proof:

Let G_0  be any labelled graph with m edges. Then since

{G_(n,p)= G_0  }⊆{|E_(n,p) |=m}

We have 

P(G_(n,p)= G_0 |E_(n,p) |=m)=  (P(G_(n,p)= G_0 |E_(n,p) |=m))/(P(|E_(n,p) |=m))  

=  P(G_(n,p)= G_0 )/((|E_(n,p) |=m) )

=  (p^m (1-p)^((n¦2)-m ))/(〖(((n¦2))¦m)  p〗^m (1-p)^((n¦2)-m ) )

= (((n¦2))¦m)^(-1).

Thus G_(n,p) conditional on the event {G_(n,p) has m edges} is equal in distribution to G_(n,m), the graph chosen uniformly at random from all graphs with m edges. Obviously, the main difference between those two models of random graph is that in G_(n,m.)we choose its number of edges, while in the case of G_(n,p) the number of edges is the binomial random variable with the parameters and p. intuitively, for large n random graphs G_(n,m) and G_(n,p)  should behave in similar fashion when the number of edges m in G_(n,m) equals or is “ close” to the expected number of edges of G_(n,p)ie., when m= (n¦2)p≈(n^2 p)/2,

Or, equivalently, when the edge probability in G_(n,p)

p≈2m/n^2 .

Throughout the book, we will use the notation f≈g to indicate that f=(1+o(1)g, where the o(1) term will depend on some parameter going to 0 or ∞.

We next introduce a useful “coupling techniques” that generates the random graph G_(n,p)in two independent steps. We will then describe a similar idea in relation to G_(n,m). Suppose that p_1<p and p_2 is defined by the equation

1-p=(1- p_1 )(1-p_2 ),

Or equivalently,  

p= p_1+p_2-p_1 p_2.

Thus, an edge is not included in G_(n,p) if it is not included in either of G_(n,p1)  or G_(n,p2.)

 It follows that 

G_(n,p)=G_(n,p1)  ∪ G_(n,p2.)

Where the two graph G_(n,p1)  ,G_(n,p2.)   are independent .so when we write

G_(n,p1)  ⊆ G_(n,p),

We mean that the two graph are coupled so that G_(n,p) is obtained from G_(n,p1)by super imposing it with  G_(n,p2.)and replacing eventual double edges by a single one. 

We can also couple random graph G_(n,m_1 )  or G_(n,m_2.)  where m_2≥ m_1 via 

G_(n,m_2 )  = G_(n,m_1 )∪H.

Here H is the random graph on vertex set [n] that has m = m_2  -m_1 edges chosen uniformly at random from ((([n])¦2))⁄E_(n,m_1 ) 

Consider now a graph property P defined as a subset of the set of all labelled graphs on vertex set [n], i.e.,,P ⊆2^((n¦2) ). 

 For example, all connected graphs (on n vertices), graphs with a Hamiltonian cycle, graphs containing a given subgraph, planar graphs, and graphs with a vertex of given degree form a specific “graph property”.

We will state below two simple observations which show a general relationship between G_(n,m) and G_(n,p)in the context of the probabilities of having a given graph property P. The constant 10 in the next lemma is not best possible, but in the context of the usage of the lemma, any constant will suffice.

LEMMA:1.2 

Let  P be any graph property and p=  m⁄((n¦2)  where m=m(n)→∞,(n¦2)  →∞,then,for all large n,)

P(G_(n,m)∈P)≤10m^(1⁄2) P(G_(n,m)∈P)

Proof:

By the law of total probability, 

P(G_(n,m)∈P)= ∑_(k=0)^((n¦2))▒P(G_(n,m)∈P)  (|E_(n,p) |=k P(E_(n,m)=k))

= ∑_(k=0)^((n¦2))▒〖P(G_(n,m)∈P)P(E_(n,m)=k)     1.4〗

≥P(G_(n,m)∈P)P(E_(n,m)=m)

To justify (1.4), we write

P(G_(n,m)∈P)|E_(n,p) |=k)=  (P(G_(n,m)∈P)∧|E_(n,p) |=k) )/P(|E_(n,p) |=k ) 


= ∑_█(G∈P@|E(G)|=k)▒(p^k (1-p)^(N-K))/((N¦K)  p^k (1-p)^(N-K) )

= ∑_█(G∈P@|E(G)|=k)▒1/((N¦K)  )

=P(G_(n,k)∈P)

Next recall that the number of edges |E_(n,p) | of a random graph G_(n,p) is a random variable with the binomial distribution with parameters(n¦2)  and p. Applying Stirling’s formula:

 k!=(1+o(1)) (k/e)^k √2πk,                                          (1.5)

 Putting, 

N= (n¦2),we get,after substituting (1.5)for the factorials in (N¦m),

 P(|E_(n,p) |=m )=(N¦m) p^m (1-p)^((n¦2)-m)  

=   (1+o(1))  ((N)^k √2πN p^m (1-p)^(N-m)  )/(m^m (N-m)^(N-m)  √(2πm(N-m) ))  (1.6)

    =   (1+o(1)) √(N/2πm(N-m) ,)

  hence,                   P(|E_(n,p) |=m )≥1/(10√m),  

so,       P(G_(n,m)∈P)≤10m^(1⁄2) P(G_(n,m)∈P)

we call a graph property P monotone increasing if G∈P implies G+e∈P, ie., adding an edge e to a graph G does not destroy the property. For example, connectivity and Hamilton city are monotone increasing properties. A monotone increasing property is non – trivial if the empty graph K ̅_n∉P and the complete graph K_n∈P.

P monotone decreasing if G∈P implies G-e∈P, ie., adding an edge e to a graph G does not destroy the property. Properties of a graph not being connected or being planar are examples of monotone decreasing graph properties. Obviously, a graph property Pis monotone increasing if and only if its complement is monotone decreasing. Clearly not all graph property monotone. For example, having at least half of the vertices having a given fixed degree d is not monotone.

From the coupling argument it follows that if P is monotone increasing property then, whenever p<p^' or m<m^',

P(G_(n,p)∈P)≤P(G_(n,p^' )∈P),   (1.7)

P(G_(n,m)∈P)≤P(G_(n,m^' )∈P),   (1.8)

Respectively, for monotone increasing graph properties we can get a much a better upper bound on  P(G_(n,m)∈P), in terms of P(G_(n,m)∈P),than that given by lemma1.2.

LEMMA:1.3 

 Let P be an monotone increasinggraph property and p=  m⁄(N ,then,for all large n and p=o(1)such that Np,N(1-p)/〖(NP)〗^(1/2)→∞,)

P(G_(n,m)∈P)≤3P(G_(n,p)∈P)

Proof:

Suppose P be an monotone increasing and   p=m/N  N=(n¦2)then, 

P(G_(n,m)∈P)= ∑_(k=0)^N▒P(G_(n,k)∈P)  P(E_(n,p)=k)

≥ ∑_(k=0)^N▒〖P(G_(n,m)∈P)P(E_(n,m)=k)     〗

However, by the coupling property we know that k≥m.

P(G_(n,k)∈P)≥P(G_(n,m)∈P)

The number of edges |E_(n,p) |  in〖 G〗_(n,p)  has the binomial distribution with parameters N, p. hence, 

P(G_(n,p)∈P)≥ P(G_(n,m)∈P) ∑_(k=m)^N▒P(|E_(n,p) |=k ) 


=P(G_(n,m)∈P) ∑_(k=m)^N▒u_(k   ) (1.9)

u_k=(N¦K)  p^k (1-p)^(N-K)

Applying Stirling’s formula:

 u_m=(1+o(1))  (N^N p^m (1-p)^(N-m)  )/(m^m (N-m)^(N-m) (2πm)^(1/2) )   =((1+o(1)))/(2πm)^(1/2)       

furthermore,ifk=m+t where 0≤t≤m^(1/2)  then,

 u_(k+1)/u_k =  (N-k)p/(k+1)(1-p) =  (1- t/(N-m))/(1+(t+1)/m  )≥exp⁡{-t/(N-m-t)-(t+1)/m},

After using lemma23.1(a), (b) to obtain the inequality. And our assumptions on N, p to obtain to second.

It follows that for 0≤t≤m^(1/2),

u_(m+t)≥((1+o(1)))/(2πm)^(1/2)   exp{-∑_(s=0)^(t-1)▒〖s/(N-m-s)-(s+1)/m〗}

≥exp⁡{-t^2/2m-o(1)}/(2πm)^(1/2)   ,

Where we have used the fact that m=o(N).

It follows that 

∑_(k=m)^(m+m^(1/2))▒u_k ≥((1+o(1)))/(2πm)^(1/2)  ∫_(x=0)^1▒〖e^(-x^2⁄2) dx〗≥1/3

 And lemma follows from (1.9).

Lemmas 1.2 and 1.3 are surprisingly applicable. In fact, since the G_(n,p)model is computationally easier to handle than G_(n,m), we will repeatedly use both lemmas to show that P (G_(n,p)∈P)  → 0 implies that P (G_(n,m)∈P) → 0 when n → ∞. In other situations, we can use a stronger and move widely applicable result. The theorem below, which we state without proof, gives precise conditions for the asymptotic equivalence of random graph G_(n,p)  and G_(n,m).it is due to Lucak [557].


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