Erdos-Renyi Random Graphs

针对graph的几个定义：
Girth（$\gamma(G)$): shortest cycle
Independence number ($\alpha(G)$): graph中vertices都没有相关关系（这里的定义是两个结点之间没有连接边）的最大簇（也就是说graph中没有相互关系边，结点数目最多的结点集合）。

\[\alpha(G)=max{|\textit{S}|: \textit{S}\ is\ an independent\ set}
\]

chromatic number（$\chi(G)$：类似于bipartite graph拥有两个颜色，这里说的是Graph G当中不同的结点分属于不同的k的颜色类别，每个颜色类类别中的结点都不互相相连。
chromatic number与independence number拥有相关关系

\[\alpha(G)\geq\frac{n}{\chi(G)}
\]

Erd¨os-R´enyi Model：
模型定义：图的结点数目$n$，一条边的概率$p$

markov\’s inequality（可以中期望的定义角度证明，从期望值会大于等于什么值反向证明）:

\[Pr[\textit{X}\geq\textit{k}]\leq\textbf{E}[\textit{X}]/\textit{k}
\]

一般用$Pr[\textit{X}\geq\textit{1}]\leq\textbf{E}[\textit{X}]$

Union Bound：

\[Pr[A\ or\ B]\leq Pr[A]+Pr[B]
\]

Independence Number(存在一个上限值）
如果graph中每个vertex的degree最多为$d$，那么independent set最少是$\frac{n}{d+1}$
按照上面的色图理解：如果是四色图，因为同样颜色的结点不能连接，所以四色图结点最大的个数为3，从上面每个结点的degree最多是$d$，如果认为是d+1图，那么最少每个independent set的大小为$\frac{n}{d+1}$
按照上面随即图的定义，总共n个结点，每条边存在的概率为p，那么每个结点的平均degree为$d=p(n-1)$；
令p=1/2,那么G的independence number最大为$3log_2n+1$的概率值很大。
proof：g
令$\varepsilon>0, k=[3log_2n+1],S_1, …, S_z为子集，结点数目都为k，那么z=\binom{n}{k}, X_i为随机变量（取值0,1，当S_i为independence\ set时为1）$
令

\[X=\sum_iX_i
由上面的定义可知，当$X<1$，那么$X_i$均取值为0，则$S_i$中最大的independence set的size比K小。
概率证明：
$$\textbf{E}[X_i]=Pr[X_i=1]\]

$S_i$表征的是independence set，而且我们假设每个大小都为k，如果要满足independence set的条件，那么这个集合当中，任意两个结点在原来的graph当中都应该不是相连的，其中任意两个结点都不连接的概率($p与k满足上面假设$)为：

\[(1-1/2)^{\binom{k}{2}} = ((1/2)^{(k-1)/2})^k = ((1/2)^{3log_2n/2})^k = (n^{-3/2})^k
\]

所以：

\[\textbf{E}[X]=\sum_i\textbf{E}[X_i]=\binom{n}{k}(n^{-3/2})^k=\leq n^k(n^{-3/2})^k = n^(-k/2) = （1/n)^(k/2)
\]

当n趋于无穷的时候，上述表达式趋向于0
所以：

\[Pr_{G\leftarrow \mathcal{g}(n, 1/2)}[\alpha(G) \geq (3log2n+1)] \leq n^{-k/2} \rightarrow 0
\]

事实上，$\alpha(G)更加接近与2log_2n$
更一般化而言：

\[Pr_{G\leftarrow \mathcal{g}(n, p)}[\alpha(G) \geq k] \leq (n(1-p)^{(k-1)/2})^k
\]

利用$1-p \leq e^{-p}$,当$k=\frac{3lnn}{p}+1$时

\[n(1-p)^{(k-1)/2} \leq ne^{-p(k-1)/2} = e^{lnn-p(3lnn)/2p} – e^{lnn-(3/2)ln} = n^{-1/2}
\]

所以：

\[Pr_{G\leftarrow \mathcal{g}(n, p)}[\alpha(G) \geq \frac{3lnn}{p}+1] \leq n^{-3lnn/2p} \rightarrow 0
\]

High Girth(graph的拥有high girth和high chromatic number）
$girth:\ g, chromatic number:\ x$，令$p=n^{1/2g-1}$
(举例说明）这样的随机生成的graph，可能包含小的cycles，但是不会有很多，如果我们一处cycle长度达到g中的一个vertex，那么余下的graph中不会再用有小的环，但是这个图至少还会有2/n个vertices。
$G^\prime=(V^\prime, E^\prime)$为上面以除了至多n/2个vertices之后的graph，G为原图，令$S\in V^\prime是G^\prime$中的independent set，因此

\[\alpha(G^\prime) \leq \alpha(G)
\]

而且，

\[\chi(G^\prime) \geq \frac{|V^\prime|}{\alpha(G^\prime)} \geq \frac{(n/2)}{\alpha(G^\prime)} \geq \frac{n}{2\alpha(G)}
\]

从independent number可以知道，至少有3/4(该概率值计算需要进一步理解）的概率，或者说接近于1，

\[\alpha(G) \leq 3n^(1-1/2g)lnn（可以根据上面的过程自行推倒概率最终大于这个值的概率值大小）
\]

当满足上述条件且$V^\prime \geq n/2$,

\[\chi(G) \geq \frac{n^{1/2g}}{6lnn}
\]

当g的大小固定时，上式中的分子增长速度大于分母的增长速度，因此对与足够大的$n$，$\chi(G^\prime) \geq x$

以下证明，G当中会存在少量长度为g的circle。
g-cycles: 有2g种描述，第一个结点有g个选择，可以走不同的两边,总共存在的组合数目：

\[n(n-1)…(n-g+1) \leq n^g
\]

由于每条边出现的概率为g，所以组合中每一个出现的概率值为$p^g$,因此g-cycles存在的数量的期望值：

\[n^gp^g = (np)^g = (n^{1/2g})^g = n^{1/2}(都符合前面的p的规定值）
\]

graph中存在长度为j的数量，当j<g时，期望数值会更少，当circle的长度，最长为g，那么期望存在的数目最多不会超过$gn^{1/2}$;
按照markov\’s inequality
因为上面cycles的长度不超过g的期望值是$gn^{1/2}$,那么在G中含有$4gn^{1/2}$个长度最长为g的cycles的概率值不会大于1/4($\frac{gn^{1/2}}{4gn^{1/2}}$)
当n足够大能够满足$4gn^{1/2} \leq n/2$时，那么至少有3/4的概率，$G^\prime$最少会有n/2个结点（根据上面$G^\prime$的剩余规则）。

通过上面的构造，$G^\prime$的girth最少为g，有3/4的概率$G^\prime$至少有n/2个结点，至少有3/4的概率G的independence number为$3n^{1-1/2g}lnn$。
union bounds定律可以知道，independence number和girth都满足上述条件的概率至少为1/2，也就是说，只有有1/2的概率$G^\prime$至少有$n/2个vertices，\alpha(G)至少为3n^{1-1/2g}lnn,所以\chi(G) \geq x(当n足够大时)$.

Giant Component:

Real-world graph通常会有一个component包含大部分的vertices，second-largest component会比这个小很多数量级。
这里用Erdos-renyi random graph来表明这个现象，这个large component叫做giant component。

model参数：$p = c/(n-1)$, c为常数项，n
可变，所以每个vertex的degree的期望值为$c(c/(n-1)*(n-1))$。当c<1时，每个component可能会很小，最多拥有$\textit{O}(logn)$个vertices，当c>1时，这个graph可能会包含a constant fraction of vertices的连通分量。
当c从0-1变化时，graph property的也会发生改变(threshold phenomenon)

Concenration and chenoff Bounds
Chernoff(and Hoeffding) bounds都是中央集中定理（central limit theorem)：所有的独立的随机变量的和都是指数集中在他们的均值附近，他们不等式的形式依赖于随机变量的类型。
Erdos-renyi model的随机变量为bernoulli random variables。
定理令$X_1,…,X_n为独立的Bernoulli（也就是说取值为0/1）\ random\ variables, 且Pr[X_i=1]=p_i。令X=\sum X_i，\mu=\sum p_i为X的期望值.那么对所有0<\delta<1，有$

\[Pr[X \leq (1-\delta)\mu] \leq exp(\mu\delta^2/2)
\]

和

\[pr[X \geq (1+\delta)\mu] \leq exp(\mu\delta^2/3)
\]

当$p=clnn/(n-1)$,c>6时，vertex的期望degree为\mu=cln(n)。如果我们设$\delta=\sqrt{6/c}<1$, 那么vertex的degree会超过$(1+\delta)\mu的概率值为:

\[exp(-c(lnn)\delta^2/3)=exp(-clnn)(6/c)/3)=exp(-2lnn)=n^{-2}
\]

degree大于$(c+\sqrt{6c})lnn以及degree小于(c-\sqrt{4c}）lnn$的概率都最多为$n^{-1}$.

Galton-Vaston process, binary case
通过细胞分裂的例子，分析后代存活数量。
每一次分裂，每一个个体的存活概率为$p$,所以，第一代细胞的存活数量的期望值为$2p$,第二代细胞的存活数量的期望值为$4p^2$.
以此类推，k-th代细胞存活数量的期望值为$2^kp^k=(2p)^k$.
当$p<1/2$时，存活梁会接近与0，$p>1/2$存活率为区域无穷（threshold phenomenon）。

$p<1/2$
令$X^k$为kth generation后代的counting number（random ariable），$X^k\geq 1$表明后代依旧存在:

\[Pr[X^k \geq 1] \leq E(X^k) =(这里的符号原来为\leq??) (2p)^k \xrightarrow[k\to\inf]{} 0
\]

$p>1/2$
$\theta_k(p)$为至少存在k-th generation的概率值，等同于k-1代至少存活一个后代。令$A$为first child存活到k-1代，$B$为second child存活到k-1代。
first child存活，并且至少有k-1个后代存活的概率为$p\theta_{k-1}(p)$,(A,B事件发生的概率值都为$\theta_k(p)$）。

\[\theta_k(p) \overset{Pr[A\ or\ B]=Pr[A]+Pr[B]-Pr[A\ and\ B]}{=} 2p\theta_{k-1}(p) – (p\theta_{k-1}(p))^2
\]

当$k$增长时，如果$\theta_k(p)$有一个增长上限$q=2pq-(pq)^2$，那么

\[q\overset{def}{=}\frac{2p-1}{p^2}(因为p>1/2,所以q>0)
\]

\[\theta_k(p) = f(\theta_{k-1}(p))-> f(x)=2px-(px)^2
\]

因为$\theta_0(p)=1, 从q的定义中可知，q能够取到的最大值为1（p==1是），p越小q值越小, 所以 1=\theta_0(p)\geq q$,
对$f(x)进行单调性分析可知，因为x的取值范围为（0，1]，f(x)在此范围内单调递增，令f(q)=q，可知当x\in (q,1]时，f(x)\geq q$
因为当$k \geq 0, \theta_k(p)\geq q$.

$a_n数列的下极限: lim\ inf\ a_n，上极限lim\ sup\ a_n$
$\lim\inf\limits_{k\to\infty}\theta_k(p)=q$

The Number of Descendants
现在每个细胞会分裂为k个后代，令$p=c/k$,当$c<1时属于sub-critical\ regime，c>1时为super-critical\ regime$
这里给每个后代进行编号，保证第j代的编号都小于第j+1代的编号。
$X_{j,1}, …, X{j,k}$为bernoulli random variable, $X_{j,i}=1$，表示cell j的第i个child存活下来。最终存活的数量为$u$.

\[1+\sum_{j=1}^u \sum_{i=1}^k X_{j,i}=u$$（这里指明1为最原始的祖先）
对于所有的$v<u$,有
$$1+\sum_{j=1}^u \sum_{i=1}^k X_{j,i}>v\]

chernoff bounds:

\[X^{(u)} = \sum_{j=1}^u \sum_{i=1}^k X_{j,i}
\]

$X^{(u)}$的期望值为

\[\mu=ukp=uk\frac{c}{k}=uc
\]

上述变量$X_{j,i}$暂时不考虑Galton-Waston process，只考虑存在与否。

$令Z为first organism的后代，加1是为了最开始的organism（也可以认为把自身看成一个后代）。

\[Pr[Z>u]\leq Pr[X^{(u)}\geq u]\leq exp(-\frac{1}{3}\delta^2\mu)
\]

c<1
$当c<1时，\mu会显著小于u值，并且Chernoff bounds也可以明显表明，X^{(u)}不大可能大于u$
根据chernoff bounds，可以计算出$\delta$取值，$\delta=\frac{1}{c}-1$,
最终得到：

\[Pr[Z >u] \leq exp(-\frac{1}{3}\frac{(1-c)^2}{c}u)
\]

This is why all the components of $g(n, p)$ in the sub-critical case probably have logarithmic size.

c>1
super-critical case, $对与Z=u(u足够大）的可能性非常小, 结论Z不小而且可能无穷大$。

\[Pr[Z=u] \leq Pr[X^{(u)} \leq u]\leq exp(-\frac{1}{2}\delta^2\mu)
\]

可以推出$\delta=1-\frac{1}{c}$
因此：

\[Pr[Z=u]\leq exp(-\frac{1}{2}\frac{(c-1)^2}{c}u)=(exp(-\frac{1}{2}\frac{(c-1)^2}{c}))^u
\]

令

\[\gamma=exp(-\frac{1}{2}\frac{(c-1)^2}{c})
\]

把所有有限series都相关，那么Z概率值花很大，但是还是有限值：

\[Pr[u\leq Z\leq \inf]=\sum_{w=u}^{\inf}Pr[Z=w]\leq \sum_{w=u}^{\inf}\gamma^{-w} = \frac{\gamma^{-u}}{1-\gamma^{-1}}
\]

This is part of why the second-largest component of $g(n,p)$ in the super-critical case probably has logarithmic size。
这意味着：

\[\sum_{w=1}^{\inf}Pr[Z=w]<1
\]

Galton Waston 总结
当$p=c/k$时
定理：
$令Y为first\ organism生存下来的后代数量可以reproduce（但是不包含first organism), 如果c<1，那么对所有的u>0,有$

\[Pr[Y \geq u] \leq (exp(frac{(1-c)^2}{3c})^{-u}
\]

$Y与前面Z的差别为Y=Z-1$
定理2：
$Y定义如上，如果c>1,并且存在常量\beta_c, 不依赖于k，那么$

\[Pr[Y=\infty] \geq \beta_c$$(这个的证明与上面的在k=2的情况下寻找下极限的证明一致）
$当c>1,那么对任意的u>0$
$$Pr[u \geq Y \geq \infty] \geq (exp(\frac{(c-1)^2}{2c}))^{-u}\]

以下分析，全部基于概率值$p=c/k$
c<1: all small components
将Erdos-renyi random graph与Galton-waston branching process结合，相当于选定一个vertex $v$，galton-waston过程有$k=n-1$,（breath-first fashion）。令$w$为$v$的一个邻居，$j$为$v$的邻居数目，考虑连通分量的特性，实际上，$w$是否还直接连接$v$的邻居对改连通分量没有贡献，所以此时$w$只需要关注其他的$n-j-1$个结点，也就是Galton-waston不是分裂成n-1，而是分裂成为n-j-1，这样的变化带了的影响就是该component更小了。对于$v$的其他邻居，我们考虑同样的他可分裂的后代不是$v$的潜在孩子。

\[Pr[C(v)\geq u]\leq Pr[Y\geq u]\leq (exp(\frac{(c-1)^2}{2c}))^{-u}$$（这里的分子不是3吗？？？）
对一些常量$\alpha$可以设置$u=\alpha lnn$,而这个component的大小等于这个值的概率为$1/n^2$:
$$Pr[G\ has\ a\ component\ with\ more\ than\ \alpha lnn\ vertices] \leq \sum_{v \in V}Pr[C(v) \geq \alpha lnn] \leq 1/n.\]

（下面这段有点奇怪，还是得重新理解一下）

c>1: the giant component
$p=c/n$在这种情况下，图中会出现很大的component，现在只考虑$c \leq 2$的问题。
从c<1 case中modified Galton-Watson process过程中已知，这个过程会减少component的大小，但是现在在c>1的情况下，我们想证明这个图当中还是会存在大的component。
为了解决这个问题，设$d=\sqrt{c}, 因为c>1, 所以d=c/n*n>1$, 这里会探索$当k=(2-d)n, p^\prime = d/(n-1)时，cell\ v\ 存活的情况$。
从上面已知，现在的$k=(2-d)n,那么已经发现的vertices为n-k=(d-1)n, 当已经发现的节点数目为(d-1)n, 那么至少还存在(2-d)n个vertices存在$。

（未完全理解）
v邻居的Galton-Waston process的分裂中，如果其中的某一些cell分裂多于k个children，那么存活率会增加（这里是不是表明v前面没有发现那么多个节点呢？？？）。这意为这他们更可能生成一个大的component，但是当发现了(1-d)n个节点之后，这个分析就无效了，但是也可以认为此时我们已经有了一个giant component。
当一个component的大小至少为(d-1)n的时候，存在constant chance, Galton-Watson process中会有一个无穷大的component。否则，size of component 大于$\alpha lnn$的概率最多为$1/n^2$。（我们可以假定这种情况下前者存在？？？）这种情况下，发现component中还没有被放置的一个节点，通过logarithmic number的时间，我们很大的可能发现一个大的component。更多的时，logarathmic
number of small component 只会移除O(log^2n) 个vertices，对与大的n而言，这个数量可以忽略不计。
（为什么不大可能出现两个大的component，是因为这两者中间可能有边连接。）

Graph with given degree distribution
Edos-renyi random graph的degree分布为binominal degree distribution，但是更多的graph的分布为长尾分布（heavy tails）。
这里甬道的图利用的时fixing degree distribution，也就是选择一个random graph，图符合$k_i个vertices用有i个degree, \sum_i k_i=n.
随机图生成方式：对$k_i$个节点设定i个socket，每次随机选择两个socket，进行边的连接，如果出现自环或者相同的边，那么就再重新sample（开销不大的时候)(Kim Wormald)

Diameter
事实上很多graph的周长都比较小。对于这种fixed degree distribution，只要最小的degree不是特别小，可能会拥有logarithmic diameter。只要最小的degree大于3就足够了。
令$\textit{S}$时节点子集，如果$|\textit{S}|\leq n/4$,那么$\textit{S}$的并集以及他的邻居可能至少大小为$2|\textit{S}|$。也就是说，每个节点至少会有一个neighbor，these togetherprobably have 2 neighbors。
所以，$只要满足2^k < n/2, 每个节点可能至少在他的距离k以内有2^k个节点$

本文链接：https://www.cnblogs.com/luxuriance-lily/p/13551113.html

Erdos-Renyi Random Graphs

Giant Component:

Erdos-Renyi Random Graphs的更多相关文章

随机推荐

热门专题

目录导航