Real World Networks

很长时间内，人们习惯于将所有复杂网络都看作是随机网络。在1999年研究描绘万维网(以网页为节点、以超级链接为边)的项目时，学者们原以为会发现一个随机网络：人们会根据自己的兴趣，来决定将网络文件链接到哪些网站，而个人兴趣是多种多样的，可选择的网页数量也极其庞大，因而最终的链接模式将呈现出相当随机的结果。

然而，事实并非如此。因为在万维网上，并非所有的节点都是平等的。在选择将网页链接到何处时，人们可以从数十亿个网站中进行选择。然而，我们中的大部分人只熟悉整个万维网的一小部分，这一小部分中往往包含那些拥有较多链接的站点，因为这样的站点更容易为人所知。只要链接到这些站点，就等于造就或加强了对它们的偏好。这种“择优连接(Preferential Attachment)”的过程，也发生在其他网络中。在Internet上，那些具有较多连接的路由器通常也拥有更大的带宽，因而新用户就更倾向于连接到这些路由器上。在美国的生物技术产业内，某些知名公司更容易吸引到同盟者，而这又进一步加强了它在未来合作中的吸引力。类似地，在论文引用网络(论文为节点，引用关系为边)中，被引用次数较多的科学文献，会吸引更多的研究者去阅读并引用它。针对这些网络的“择优连接”的新特性，引出了以下的内容。

Background

ER随机图与很多实际网络具有很多共性，例如稀疏性，巨片，平均距离等，但在度分布上，两者具有显著差异，ER随机图告诉我们度分布可近似Possion分布，该分布在$<k>$处有一个峰值，然后呈指数快速衰减。但实际网络中会呈现一种长尾分布，存在少量度很大的节点。

Preferential Attachment Graph

Defination

优先连接网络相较于ER随机图有两个特性，一个是允许点增加，一个是优先连接
记$G_1,G_2\dots G_t$为一列随机图，固定一个整数$m$为每次新加点携带的度。初始时刻，$G_1$为1个点，$m$条自环的图，$G_{t+1}$是通过$G_t$添加点$v_{t+1}$以及$m$条边得到。
这里，对于$m$条边的添加为从$G_t$中依据概率$P$选择$m$个点并将他们与$v_{t+1}$相连，其中

$$\mathbb{P}(y_i=w)=\frac{\mathrm{deg}(w,G_t)}{2mt},$$

这反应在现实生活中可以说是一个新人进入了一个社区，他首先与社区中有名的人认识。接下来，对随机图模型性质进行研究。

Expected Degree Sequence: Power Law

本小节的主要结论，

$${\tilde{D}}_k(t)\approx \frac{2m(m+1)}{k^3}t.$$

度序列的期望值服从幂律分布，$k^{-3}$。推导过程大致如下

$$\begin{array}{}\end{array}$$

对上式的解释:$G_t$总点度为$2mt$所以$\frac{(k-1)D_{k-1}(t)}{2mt}$代表$y_i$是度$k-1$的点加边变成新的$k$度点的概率。相似的 $(\frac{k{D}_k(t)}{2mt})$表示$y_i$为一个$k$度点因加边导致$k$度点减少的概率。若$m=k$，本身加进去的$t+1$有$m$度，这解释了$1_{k=m}$项。$ϵ(k,t)$是一个误差项，它解释了对于某些$y_i=y_j$ $(i\ne j)$的可能性。

$$\begin{array}{}\end{array}$$

在对(19.1)两边做期望，能得到关于$\overline{D}$的一个递推

$$\begin{array}{}\end{array}$$

在假设${\overline{D}}_k(t)\approx d_{k}t$成立的条件下，可以得到一个关于$d_k$的递推式，

$$\begin{array}{}\end{array}$$

或者

$$d_k=\{\begin{array}{l}\frac{k-1}{k-2}{d}_{k-1}+\frac{2\cdot 1_{k=m}}{k+2}\text{ if }k\ge m\text{,}\\ 0\text{if }k<m\text{.}\end{array}$$

最终可以得到当$k$足够大$\overline{D}$的表达式。
定理一对假设${\overline{D}}_k(t)\approx d_{k}t$的正确性给出了说明，定理一可由归纳假设进行证明。

Maximum Degree

固定$s\le t$，设$X_l$ 为$s\le l\le t$时$G_l$中点$s$的度。引理2说明了顶点$s$的度高概率下具有以下上界。
对于引理2的证明很自然想到一阶矩方法，但这里证明非常巧妙， 通过一些放缩可以得到

$$\mathbb{E}(e^{\lambda X_{l+1}}|X_l)\le e^{\lambda (1+\frac{(1+m\lambda )}{2l})}{X}_l.$$

在设置适当的$\lambda$形式之后，

$${\lambda }_{j+1}=(1+\frac{1+m{\lambda }_j}{2j}){\lambda }_j<{ϵ}_i.$$

可以得到一个有关$\mathbb{E}(e^{{\lambda }_s{X}_l})$递推，注意到这里$X_s=m$，再根据$\lambda$递推式便可得到以下结论。

$$\mathbb{E}(e^{{\lambda }_s{X}_l})\le \mathbb{E}(e^{{\lambda }_{s+1}{X}_{t-1}})\cdots \le \mathbb{E}(e^{{\lambda }_t{X}_s})\le 1+o(1).$$

则，引理能够得到证明。这并非是最好的可能。

Concentration of Degree Sequence

为顶点度数固定一个$k$值。定理三证明了$D_k(t)$集中在它的期望值${\overline{D}}_k(t)$附近。
证明定理3借助定理23.16，

Degrees of early vertices

早期加入节点的度，这小节主要有两个重要结论

$$\begin{array}{}\end{array}$$

课本上19.11有错误。这个式子给出了点$s$在$G_t$中度期望。定理7给出了$s=O(1)$，及较早时刻出现的节点度的下界。

Spatial Preferential Attachment

空间优先连接模型，显然它结合了优先连接的概念以及对每个点引入了一个影响范围。图是有向的，影响范围与点入度有关。
设$m\in \mathbb{N}$为空间${\mathbb{R}}^m$的维度，$p\in [0,1]$为链接(弧)概率，并固定两个附加参数$A_1,A_2$，其中$A1<1/p$而$A2>0$。设$S$为${\mathbb{R}}^m$中的单位超立方体，其范数$d(·，·)$由$L^{\mathrm{\infty }}$范数导出。特别地，对于$S$中的任意两点$x$和$y$，

$$\begin{array}{}\end{array}$$

对于每一个正实数$\alpha <1$，且$u\in S$，定义$u$周围体积为$\alpha$的球

$$B_{\alpha }(u)=\{x\in S:d(u,x)\le r_{\alpha }\},$$

其中$r_a={\alpha }^{1/m}/2$,因此，$r_{\alpha }$的选择使得$B_{\alpha }$的体积为$\alpha$。 SPA 模型生成一个有向图{$G_t$}的随机序列，其中 $G_t=(V_t,E_t)$和 $V_t\subset S$, 即所有顶点都位于 $m$ 维超立方体 $S=[0,1{]}^m$中。\ 设 $de{g}^{-}(v;t)$为顶点 $\nu$ 在 $G_t$ 中的入度，$de{g}^{+}(\nu ;t)$为它的出度。则，在 t$⩾1$ 时刻，顶 点$\nu$的影响范围 S$(\nu ;t)$是以 $\nu$为圆心的球，体积如下：

$$\begin{array}{}\end{array}$$

为了构造一个图序列，我们从$t=0$开始，$G_0$为空图。在每一个时间步$t$，我们从$G_{t-1}$出发构造$G_t$，首先，从立方体$S$中均匀随机地选择一个新的顶点$v_t$并将其添加到$V_{t_1}$中以创建$V_t$。然后，独立地，对于每个顶点$u\in V_{t-1}$满足$v_t\in S(u_t,t-1)$，以概率$p$创建一个有向链接$(v_t,u)$。因此，在时间步$t$中添加一个链接$(v_t,u)$的概率等于$p|S(u,t-1)|$。

Power law and vertex in-degrees

定理8给出$t=n$时入度为$i$的点数量期望的一个估计。

$$\begin{array}{}\end{array}$$

注意这个式子有错误！！借助引理9证明。
定理10使得我们对于一个点，当给定了他的年龄后，我们能够得知其入度的期望值。这是对于SPA模型是十分有意义的，得知入度可以分析它的影响范围进而分析SPA的几何性质。证明纯计算，条件期望后期望的算法。

Directed diameter

有向直径定义为任意两点间最短路径的最大值。定理11给出了SPA模型$G_t$高概率下的直径的一个上界。

PA with Deletion

带删除的优先连接。在本节中, 我们将考虑随着过程的继续而删除或添加边或顶点的模型． Chung 和 Lu[5] 以及 Cooper、Frieze 和 Vera[8] 都考虑了随机顶点删除．这些 论文表明, 假设顶点到达的速度大于顶点被删除的速度, 度序列的幂律仍然存 在．这些论点是基于 (19.1) 等方程的分析．由于边的数量现在是一个随机变 量, 这就变得复杂了。

Random Edge Deletion

这里我们考虑的模型如下:假设$\alpha <1$满足$\alpha m$为整数。假设在添加顶点$t+1$及其$m$条关联边后，我们从当前图中随机删除$\alpha m$条边。这里的误差$ϵ(k,t)$还必须考虑到我们删除边与$t+1$关联的可能性。

Adversarial Vertex Deletion

随机删除点。这一小节的主要结论为定理12。
对于任何足够小的常数$\delta$，存在一个足够大的常数$m=m(\delta )$和一个常数$\theta =\theta (\delta ，m)$，使得高概率下$G_n$有一个大小至少为$\theta n$的“巨大”连通分量。
这个结论事实上对应了现实生活中，无针对性的随机攻击一些节点，该图的连通的性质不变，证明其具有很好的鲁棒性。

定理13给出耦合用的导出子图的相关描述，定理15给出了好顶点数的下界。利用定理13、14、15可以证明定理12。

定理13对于任何足够小的常数$\delta$，存在一个足够大的常数$m=m(\delta )$，使得我们可以耦合$G_n$和随机图$H_n$，其顶点集${\mathrm{\Gamma }}_n$ ，使得$H_n\sim G({\gamma }_n，p)$以及高概率下$|E(H_n)\mathrm{\setminus }E(G_n)|\le {10}^{-3}{e}^{-2{\delta }^{2}m/{10}^7}mn$。
为了描述我们耦合中的诱导子图，我们现在做一些定义。我们说$G_t$的顶点$v$是好的，如果它是在时间$t/2$之后创建的，并且它未被删除的原始边的数量超过$m/6$。说到$v$的原始边，我们指的是添加$v$时创建的$m$条边。设${\mathrm{\Gamma }}_t$表示$G_t$的好顶点集，并且${\gamma }_t=|{\mathrm{\Gamma }}_t|$。如果一个$G_t$的顶点不是好的 ，我们就说它不好。注意，一旦一个顶点变坏，它在剩下的过程中仍然是坏的。另一方面，一个在$t_1$时间点是好的顶点，在之后的$t_2$时间点可能会变坏，原因很简单，因为它是在$t_2/2$之前创建的。
定理14设$G$通过从$G_{n,c/n}$中删除少于$n/100$条边得到。如果$c\ge 10$，则高概率下$G$有一个大小至少为$n/3$的连通分支。
定理15高概率的意义下，对于所有$n/2<t\le n$的$t$，我们有${\gamma }_t\ge t/10$。

prove of 12

令

$$p=\frac{m}{1500n}$$

令$G=G_n$,$H=G({\gamma }_n，p)$为定理19.13构造的图。设$G^{\prime }=G\cap H$。然后$E(H)\mathrm{\setminus }E(G^{\prime })=E(H)\mathrm{\setminus }E(G)$所以高概率下$|E(H)\mathrm{\setminus }E(G^{\prime })|\le {10}^{-3}e-{\delta }^{2}m/{10}^{7}mn$。根据引理19.15，$|G^{\prime }|={\gamma }_n\ge n/10$ w.h.p，由于$m$足够大，$p=m/1500n>10/{\gamma }_n$和${10}^{-3}{e}^{-{\delta }_{2}m/{10}^7}mn<n/1000\le {\gamma }_n/100$。那么，根据引理19.14,w.h.p. $G^{\prime }$(因此G)有一个大小至少为$|G^{\prime }|/3\ge n/30$的分量。