Recently, in the course of MAP554, we talk about different types of random graphs, a branch very active in maths and its applications since the appearance of the social network. In fact, there exists various types of random graphs to simulate different situations, we will start one by one and in this post we concentrate on Erdos-Renyi Graph
Definition of Erdos-Renyi graph
The definition of Erdos-Renyi graph is very simple. In graph $G(n, p)$, each edge between vertex $u,v$ has probability $p$ to appear, and for different edges, they are independent. This model simulates well the situation the propagation of virus in the society, or the diffusion of message in a small environment, where every one is same and no limit of distance.We consider a concrete question: Now the ads is diffused, what's the probability that all the people are influenced? What's the possible size of the largest connected component?
The emergence of great connected component
We simulate the propagation of the information in the way like the random walk associated with Watson-Galton branching movement. Each step, we deactiver a vertex and add all the vertex non-explored who has connection with that one. If we note $A_k$ the number active and $D_k$ the number explored in the k-th time. That is$$
A_k = A_{k-1} + D_{k} - 1
$$
where $D_k$ follows the distribution of $Bin(n - A_{k-1} - k + 1)$.
This description is the most important way and we will repeat that many and many times in the proof. The estimation about the size of Watson-Galton is very standard by the Chernoff inequality:
$$
\mathbb{P}(C > k) \leq \mathbb{P}(A_k > 0) = \mathbb{P}(D_1 + D_2 + \dots D_k > k)
\leq e^{-\theta k } \mathbb{E}[e^{\theta(D_1 + D_2 + \dots D_k )}]
$$
Then, we use the technique to minimize the right term.
We declare directly the conclusion : In the case sub-critical, $np < 1$, the largest connected component is of the order $\log{n}$ with a large probability. In the case super-critical, $np > 1$, with large probability, the largest connected component is of the order $O(n)$, but the second one is of the order $\log{n}$.
The probability of a connected graph
The conclusion: $\lim_{n \rightarrow \infty} np - \log{n} = c$, then the probability that the graph is connected is $e^{-e^{-c}}$.
The proof of this theorem uses the first and second moment method, the approximation of Poisson distribution (little number theorem). Something amazing is that in fact, this probability is very close to that of non isolated vertex in the graph. That is to say, when $n$ is big enough, we can consider the two equivalent.
Conclusion: The Erdos-Renyi graph is the simplest model of random graph, since there are no geometric structures, which makes it simple and accessible. When the probability is so small, there are high probability that the graph isn't connected and when it rises, the probability of connectivity climbs, the biggest connected component will also grow from the $\log{n}$ to $O(n)$. Moreover, in some more complicated model like Ising model or percolation, there are also the similar conclusion like sub-critical and super-critical.
Phase transition, the critical point, the asymptotic behavior, scaling limit and continuous model associated, the random walk on the random graph, the mixing time of the former...These will compose my future research. Exciting!
The proof of this theorem uses the first and second moment method, the approximation of Poisson distribution (little number theorem). Something amazing is that in fact, this probability is very close to that of non isolated vertex in the graph. That is to say, when $n$ is big enough, we can consider the two equivalent.
Conclusion: The Erdos-Renyi graph is the simplest model of random graph, since there are no geometric structures, which makes it simple and accessible. When the probability is so small, there are high probability that the graph isn't connected and when it rises, the probability of connectivity climbs, the biggest connected component will also grow from the $\log{n}$ to $O(n)$. Moreover, in some more complicated model like Ising model or percolation, there are also the similar conclusion like sub-critical and super-critical.
Phase transition, the critical point, the asymptotic behavior, scaling limit and continuous model associated, the random walk on the random graph, the mixing time of the former...These will compose my future research. Exciting!
没有评论:
发表评论