Blog - 晨星博客

练习代码: HenryJi529/ClassicComplexNetworkAnalysis
网课资源: 复杂网络建模：基于Python+NetworkX的实现

图论基础

常见网络

蛋白质交互网络
社交网络
人类疾病网络
公交路线网

图论基础

网络对比图论的区别:

研究对象来源于现实
研究对象高复杂性

网络中常用的统计测度:

领接矩阵
度、平均度以及度分布
路径和距离(最短路径长度)
连通性: 无向网络中，任意节点之间至少存在一条通路，分为强连通(双向)和弱连通(单向)，这还引出了强连通分支(SCC, Strongly connected component)
集聚系数, 平均集聚系数, 全局集聚系数
集聚系数用来表达给定节点的邻居节点之间的连接程度
- 集聚系数 $$ C_i=\frac{2\left(L_i\right)}{k_i\left(k_i-1\right)} $$
- 平均集聚系数 $$ \langle C\rangle=\frac{1}{N} \sum_{i=1}^N C_i $$
- 全局集聚系数 $$ C_{\Delta}=\frac{3 \times \text { 三角形的个数 }}{\text { 连通三元组的个数 }} $$

复杂网络的统计特征

网络的基本静态几何特征

度分布与常见的度分布

度分布
- 规则网络: Delta分布(尖峰分布)
- 完全随机网络(每条边出现的概率相等): 二项分布$\Rightarrow$泊松分布
- 无标度网络(非均匀网络,异质网络): 幂指数分布 $P(k)\propto k^{-\gamma}$
- 指数度分布网络: $P(k)\propto e^{-k/\kappa}$
累计度分布
幂律分布: $P_k \propto \sum_{x=k}^{\infty} x^{-\gamma} \propto k^{-(\gamma-1)}$
指数分布: $P_k \propto \sum_{x=k}^{\infty} e^{-x / \kappa} \propto e^{-k / \kappa}$

网络的直径、平均距离、集聚系数以及度度相关性

距离: $d_{ij}$
效率: $1 / d_{i j}$ 称为节点 $\mathrm{v}_ i$ 和 $\mathrm{v}_ j$ 之间的效率，记为 $\varepsilon_{i j}$，用来反映节点之间的信息传递速度。两节点无连通时，$d_{i j} = \infty$， $\varepsilon = 0$，所以效率更适合度量非全连通网络。
- 局部效率: 是指一个点周围网络的传递效率。它是网络中每一个节点周围网络部分的平均传递效率。 $$ E_i = \frac{\sum d_{ij}^{-1}}{k_i * (k_i - 1)} $$ 局部效率代表了一个节点周围网络的效率，如果一个点周围网络效率越高，则说明该点在网络中的重要性也越高。
- 全局效率: $$ E_g = \frac{\sum d_{ij}^{-1}}{N * (N - 1)} $$
直径: $D=\max_ {1\leq i, j\leq N}d_ {i j}$
平均距离: $L=\frac{1}{N^2} \sum_{j=1}^N \sum_{i=1}^N d_{i j}$
- 对于无向图来说: $L=\frac{2}{N(N-1)} \sum_{i=1}^N \sum_{j=i+1}^N d_{i j}$
- 小世界效应: 节点数巨大，但平均距离小得惊人
集聚系数: 表示一个节点周围邻居节点的连接程度: $C_i=\frac{M_i}{M_{max}}=\frac{2M_i}{k_i(k_i-1)}$
- 平均聚集系数: $\langle C\rangle=\frac{1}{N} \sum_{i=1}^N C_i$
度-度相关性: 描述了网络中度大的节点和度小度的节点之间的关系。若度大的节点倾向于和度大的节点相连接，则网络时度-度正相关的；反之是度-度负相关。
- 基于最近邻平均度值的度-度相关性节点$v_i$的最近邻平均度值为:
  
  \[ k_{n n, i}=\left[\sum_j a_{i j} k_j\right] / k_i \]
  
  其中，$k_i$ 表示节点 $v_i$ 的度值， $a_{i j}$ 为邻接矩阵元素。所有度值为 $k$ 的节点的最近邻平均度值的平均值 $k_{\mathrm{nn}}(k)$ 定义为:
  
  \[ k_{n n}(k)=\left(\sum_{i, k_i=k} k_{n n, i}\right) /[N \cdot P(k)] \]
  
  如果 $k_{\mathrm{nn}}(k)$ 是随着 $k$ 上升的增函数，则说明度值大的节点倾向于和度值大的节点连接，网络具有正相关特性，称之为同配网络；反之网络具有负相关特性，称之为异配网络。
- 基于pearson相关系数的度-度相关性
  Newman利用边两端节点的度的Pearson相关系数 $r$ 来描述网络的度-度相关性，具体定义为：
  
  \[ r=\frac{E^{-1} \sum_{e_{i j}} k_i k_j-\left[E^{-1} \sum_{e_{i j}} \frac{1}{2}\left(k_i+k_j\right)\right]^2}{E^{-1} \sum_{e_{i j}} \frac{1}{2}\left(k_i^2+k_j^2\right)-\left[E^{-1} \sum_{e_{i j}} \frac{1}{2}\left(k_i+k_j\right)\right]^2} \]
  
  式中, $k_i, k_j$ 分别表示边 $\mathrm{e}_{i j}$ 的两个节点 $\mathrm{v}_i, \mathrm{v}_j$ 的度， $M$ 表示网络的总边数。
  容易证明 $r$ 的范围为：$0 \leq|r| \leq 1$ 。当 $r<0$ 时，网络是负相关的；当$r>0$ 时，网络是正相关的；当 $r=0$ 时，网络是不相关的。

介数与核数

介数：有的节点的度虽然很小，但它可能是两个社团的中间联络人，如果去掉该节点，那么就会导致两个社团的联系中断，因此该节点在网络中起到极其重要的作用。对于这样的节点，需要定义另一种衡量指标，这就引出网络的另一种重要的全局几何量：介数。介数分为节点介数和边介数两种，反映了节点或边在整个网络中的作用和影响力。
- 节点的介数 $B_i$ 定义为 $$ B_i=\sum_ {j \neq l \neq i}\left[N_ {j l}(i) / N_{j l}\right] $$ 式中，$N_{j l}$ 表示节点 $\mathrm{v}_ j$ 和 $\mathrm{v}_ l$ 之间的最短路径条数， $N_{j l}(i)$ 表示节点 $\mathrm{v}_ j$ 和 $\mathrm{v}_ l$ 之间的最短路径经过节点 $\mathrm{v}_ i$ 的条数。
- 边的介数 $B_{i j}$ 定义为 $$ B_{i j}=\sum_{(l, m) \neq(i, j)}\left[N_{l m}\left(e_{i j}\right) / N_{l m}\right] $$ 式中， $N_{l m}$ 表示节点 $\mathbf{v}_ l$ 和 $\mathbf{v}_ m$ 之间的最短路径条数， $N_{l m}\left(\mathrm{e}_ {i j}\right)$ 表示节点 $\mathbf{v}_ i$ 和 $\mathbf{v}_ m$ 之间的最短路径经过边 $\mathrm{e}_ {i j}$ 的条数。
核度
一个图的$k$-核是指反复去掉度值小于$k$的节点及其连线后，所剩余的子图，该子图的节点数就是该核的大小。若一个节点属于$k$-核，而不属于$(k+1)$-核，则此节点的核度为$k$。
节点核度的最大值叫做网络的核度。
节点的核度可以说明节点在核中的深度，核度的最大值自然就对应着网络结构中最中心的位置。 $k$-核解析可用来描述度分布所不能描述的网络特征，揭示源于系统特殊结构的结构和层次性质。

网络密度

网络密度指的是一个网络中各节点之间联络的紧密程度。网络G的网络密度$d(\mathbf{G})$ 定义为 $$ d(\mathbf{G})=2 M /[N(N-1)] $$ 式中， $M$为网络中实际拥有的连接数， $N$为网络节点数。网络密度的取值范围为 $[0,1]$ ，当网络内部完全连通时，网络密度为1，而实际网络的密度通常远小于1，实际网络中能够发现的最大密度值是0.5。

几种常见的中心性指标

度中心性

度中心性分为节点度中心性和网络度中心性。前者指的是节点在其与之直接相连的邻居节点当中的中心程度，而后者则侧重节点在整个网络的中心程度，表征的是整个网络的集中或集权程度，即整个网络围绕一个节点或一组节点来组织运行的程度。

节点 $\mathrm{v}_i$的度中心性$C_D\left(\mathbf{v}_i\right)$定义为 $$ C_D\left(\mathrm{v}_i\right)=k_i /(N-1) $$

介数中心性

介数中心性分为节点介数中心性和网络介数中心性。节点 $\mathrm{v}_i$ 的介数中心性 $C_B\left(\mathrm{v}_i\right)$ 定义为 $$ C_B\left(\mathrm{v}_i\right)=2 B_i /[(N-2)(N-1)] $$ 与度中心性类似，可得 $H=N-1$(也是星型网络，中心节点的介数中心性为1，其它节点的介数中心性为0)。

接近度中心性

对于连通图来说，节点 $\mathrm{v}_ i$ 的接近度中心性$C_C\left(\mathbf{v}_ i\right)$ 定义为

\[ C_C\left(\mathrm{v}_ i\right)=(N-1) /\left[\sum_{j=1, j \neq i}^N d_{i j}\right] \]

特征向量中心性

有着大特征向量中心性的节点连接着的节点必然也拥有较大的特征向量中心性。

\[ A x=\lambda x \]

通常，上式的各个特征向量对应不同的特征值 $\lambda$。在这里，一个额外的要求是特征向量的每个分量必须是正数。根据Perron-Frobenius定理，只有最大的特征值对应的特征向量才是中心性测度所需要的。求这个特征向量可采用幕迭代算法。在最后得到的特征向量中，第 $i$ 个分量 $x_i$ 就是节点 $\mathrm{v}_ i$ 的特征向量中心性 $C_ E\left(\mathrm{v} _ i\right)$。

存在以下公式成立:

\[ C_ E\left(v_ i\right)=x_i=\frac{1}{max(\lambda)} \sum_{j=1}^N A_{i j} x_j \]

为何要选最大特征值对应的向量:

在特征向量中心性的计算过程中，选择特征值最大的特征向量是为了确保计算结果是唯一的。在矩阵代数理论中，对于任何一个对称矩阵，它的特征向量可以被分解为正交矩阵和对角矩阵的乘积，其中对角矩阵的对角线上的元素是特征值。这个分解的过程又称为谱分解。在特征向量中心性的计算中，我们需要找到网络的特征向量，这个特征向量应该同时满足两个条件：一是它的特征值最大；二是它与相邻节点的特征向量中心性分数具有相关性。特征值最大的特征向量是唯一且正的(Perron-Frobenius Theorem)，而且它具有一些很好的数学性质，例如它对于随机游走等算法具有较好的收敛性质，因此在实际应用中被广泛采用。当然，在某些特殊情况下，特征值最大的特征向量可能并不是最合适的选择，例如在存在负权边或非对称连接的网络中，特征值最大的特征向量可能会出现异常情况。在这种情况下，可以考虑使用其他指标或算法来计算节点的中心性分数，或者对特征向量进行调整或修正。

PageRank中心性

PageRank中心性质是基于谷歌搜索引擎的排名算法。该算法认为，一个网页的重要性取决于指向该网页的其他网页的重要性和数量。这种思想被应用于图论中，用于计算网络中每个节点的重要性。

PageRank中心性算法的基本思想是，如果一个节点有很多其他节点指向它，那么这个节点就越重要。而如果这些指向它的节点本身也很重要，那么这个节点的重要性就更高。该算法考虑了整个网络的结构，而不只是每个节点的直接连接。

在实际应用中，通常会使用迭代算法来计算每个节点的PageRank中心性。需要注意的是，PageRank算法在实际应用中可能会面临一些问题，例如节点数量过多、网络结构复杂等，这些问题可能会影响算法的计算效率和准确性。因此，在实际应用中需要根据具体情况进行算法的优化和改进。

步骤如下:

创建初始的PageRank值：对于一个包含N个节点的网络，初始化每个节点的PageRank值为1/N。
计算每个节点的出度：对于每个节点i，计算它指向其他节点的数量（即出度）。
迭代计算PageRank值：重复执行以下步骤，直到收敛为止。
1. 对于每个节点i，计算它的PageRank值： $$ PR(i) = (1-d)/N + d * \sum PR(j)/outDegree(j) $$ 其中d是阻尼系数(通常取0.85，它模拟了随机用户在浏览网页时继续点击链接的概率)。$N$是网络中节点的总数，$j$是所有指向节点i的节点，$outDegree(j)$是节点j的出度。
2. 将每个节点的PageRank值进行归一化处理，保证它们的和等于$1$。
输出每个节点的PageRank值，按照从高到低的顺序排列，即可得到节点的PageRank中心性排名。

半局部中心性

\[ c_i^{sl}(r) = \sum_{j \in N_i(r)} w_{i,j} \sum_{k \in N_j(r) \setminus N_i(r)} w_{j,k} \]

其中，$N_i(r)$表示节点i的半径为r的邻域，$w_{i,j}$表示节点i与节点j之间的边权重，$w_{j,k}$表示节点j与节点k之间的边权重。公式中的第一个求和表示对于节点i的每个邻居节点j，计算i与j之间的边权重，并将其乘以后面的求和结果。后面的求和表示对于节点j的每个邻居节点k，计算j与k之间的边权重，但排除了在i的半径为r的邻域内的节点。最终将所有节点j的结果相加得到节点i的半局部中心性。

ClusterRank

是一种基于PageRank算法的局部集聚系数计算方法，用于衡量节点在局部图中的集聚程度。它的计算方式如下：

对于图中的每个节点，计算其在局部图中的聚集系数(clustering coefficient)，作为初始的PageRank分值；
对于每个节点，将其与其邻居连接的边权重作为出链的权重，计算其PageRank值；
对于每个节点，将其PageRank值除以其初始的聚集系数，得到最终的Clusterrank分值。

该算法的核心是将PageRank算法中的随机游走解释为节点在局部图中的聚集现象，从而将局部图的聚集系数作为初始分值。这样，Clusterrank算法可以同时考虑节点在全局图中的连接重要性和在局部图中的集聚程度。

有向网络和加权网络的静态特征

有向网络

入度和出度由于与有向网络某个节点相关联的弧有指向节点的，也有背向节点向外的，因此除了可以统计与某个节点相关联的弧数，也就是度之外，有必要分开统计两个方向的弧数，分别称为节点的入度和出度。节点 $\mathrm{v}_ i$ 的入度、出度和有向图的邻接矩阵以及度的关系为

\[ \begin{aligned} & k_i^{\mathrm{in}}=\sum_{j=1}^N a_{j i} \\ & k_i^{\text {out }}=\sum_{j=1}^N a_{i j} \\ & k_i=k_i^{\text {out }}+k_i^{\mathrm{in}} \end{aligned} \]
入度分布和出度分布
累积入度分布和累积出度分布
平均距离和平均效率

加权网络

点权(加权度)
单位权
基于节点的权-度相关性
基于边的权-度相关性
权重分布的差异性

随机网络

规则网络

常见规则网络:

ER随机网络的生成算法

两种生成方法:

$G(N, L)$ 模型
$N$ 个节点通过 $L$ 条随机放置的链接彼此相连。埃尔德什和雷尼在他们关于随机网络的系列论文中采用的是这种定义方式。构建步骤如下:
1. 从N个孤立节点开始。
2. 随机选择一对节点，如果两个节点不同且未连接，则连接两节点。
3. 当图中的边小于L，重复步骤2。
$G(N, p)$ 模型
$N$ 个节点中，每对节点之间以概率$p$彼此相连。
构建步骤如下:
1. 从N个孤立节点开始。
2. 选择一对节点，产生一个0到1之间的随机数。如果该随机数小于$p$，在这对节点之间放置一条链接；否则，该节点对保持不连接。
3. 对所有 $N(N-1)/2$ 个节点对，重复步骤2。

ER随机网络结构特性

随机网络恰好有 $L$ 条链接的概率，是如下三项的乘积:

$L$个点对之间存在链接的概率，即$pL$。
剩余$N(N-1)/2-L$个点对之间没有链接的概率，即 $(1-p)N(N-1)/2-L$ 。
在所有 $N(N-1)/2$个点对中选择$L$个点对放置链接，所有可能的选择方式数为:

\[ \left(\frac{N(N-1)}{2}\right) \]

因此，随机网络恰好有 $L$ 条链接的概率为:

\[ p_L=\left(\frac{N(N-1)}{2}\right) p^L(1-p)^{\frac{N(N-1)}{2}-L} \]

上式是一个二项式分布，因此随机网络的期望链接数为:

\[ \langle L\rangle=\sum_{L=0}^{\frac{N(N-1)}{2}} L p_L=p \frac{N(N-1)}{2} \]

在连接概率为 $p$ 的ER随机图中，可知其平均度为:

\[ \langle k\rangle=\frac{2\langle L\rangle}{N}=p(N-1) \approx p N \]

度分布

随机网络中，一个节点 $i$ 恰好有 $k$ 个链接的概率是下面三项的乘积:

$k$个链接出现的概率，即$pk$。
剩下 $(N-1-k)$ 个链接不出现的概率，即 $(1-p) N-1-k$ 。
节点$i$的 $N-1$ 个可能存在的链接中选出 $k$ 个，选择方式的总数为:
$$ \left(\begin{array}{c} N-1 \ k \end{array}\right) $$

因此，随机网络的精确度分布服从二项分布:

\[ p_k=\left(\begin{array}{c} N-1 \\ k \end{array}\right) p^k(1-p)^{N-1-k} \]

大部分真实网络是稀疏的，意味着这些网络的平均度远小于网络大小。当$\boldsymbol{N} \gg\langle\boldsymbol{k}\rangle$时，二项分布可近似为泊松分布: $$ p_k=e^{-\langle k\rangle} \frac{\langle k\rangle^k}{k !} $$ 上式通常被称为随机网络的度分布。

性质总结

平均度
$$ \langle k\rangle=p(N-1) $$
平均链接数
$$ \langle L\rangle=\frac{p N(N-1)}{2} $$
度分布
- 二项形式: $\quad p_k=\left(\begin{array}{c}N-1 \\ k\end{array}\right) p^k(1-p)^{N-1-k}$
- 泊松形式： $\quad p_k=e^{-\langle k\rangle} \frac{\langle k\rangle^k}{k !}$
平均距离短
$$ \langle d\rangle \propto \frac{\ln N}{\ln \langle k\rangle} $$
集聚系数小
$$ \langle C\rangle=\frac{\langle k\rangle}{N} $$
巨连通分支: $\langle k \rangle = 1$ 为临界条件
$$ \begin{gathered} \langle k\rangle<1: \mathbf{N}_ {\mathrm{G}} \sim \ln N ; \ 1<\langle k\rangle<\ln N: N_G \sim N^{\frac{2}{3}} \ \langle k\rangle>\ln \mathrm{N}: \mathrm{N}_ {\mathrm{G}} \sim\left(\mathrm{p}-\mathbf{p}_{\mathrm{c}}\right) \mathbf{N} \end{gathered} $$

小世界网络

小世界网络模型

小世界现象：六度分隔

小世界性质定义为 $d_{\max } \approx \frac{\ln N}{\ln \langle k\rangle}$ “小世界现象”中的“小”是指，平均路径长度或网络直径和网络大小的关系是对数关系。因此, “小”的意思是，$\langle d \rangle$ 正比于$\ln N$，而不是正比于 $N$ 或者 $N$ 的幂。

小世界模型构建算法

WS小世界模型构建算法
1. 从规则图开始: 考虑一个含有 $N$ 个节点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各 $K/2$ 个节点相连，$K$是偶数。参数满足$N>>K>>\ln (N)>>1$。
2. 随机化重连: 以概率 $p$ 随机地重新连接网络中的每条边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，且每个节点都不能有边与自身相连。
NW小世界模型构建算法(“随机化加边”取代WS小世界模型构造中的“随机重连”)
1. 从规则图开始: 考虑一个含有$N$个点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各$K/2$个节点相连，$K$是偶数。参数满足 $N \gg>K \gg \ln (N)\gg 1$。
2. 随机化加边：以概率 $p$ 在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。

在现实朋友关系网络中，小世界网络模型反映了如下一种特性: 大部分人的朋友都是和他们在一条街上的邻居或在同一单位工作的同事；另一方面，也有些朋友住得较远，甚至远在异国他乡，这种情景对应于WS小世界模型中通过重连或在NW小世界模型中通过加入连线产生远程连接。

实际上，除了WS小世界模型和NW小世界模型，还有许多改进模型: 加点，加边，去点，去边及不同形式的交叉，可产生多种形式的小世界模型。

小世界网络的结构特性

平均度

根据构建原理:

WS小世界网络: $\langle k \rangle = \mathrm{k}$
NW小世界网络:
$$ L = k * N / 2 + \mathrm{p} * N(N-1)/2 $$ $$ \langle k \rangle = 2 * L / N \approx k + \mathrm{p}N $$

平均距离

到目前为止，人们还没有关于WS小世界模型的平均距离$L$的精确解析表达式。不过，Newman和Watts利用重整化群分析方法得到如下公式:

\[ L(p)=\frac{2 N}{K} f(N p K / 2) \]

式中, $f(u)$ 为一普适尺度函数，满足

\[ f(u) \sim\left\{\begin{array}{cc} \text { 常数 } & u<<1 \\ (\ln u) / u & u>>1 \end{array}\right. \]

Newman等人利用基于平均场方法给出了如下的近似表达式:

\[ f(u) \approx \frac{1}{2 \sqrt{u^2+2 u}} \tanh ^{-1} \sqrt{\frac{u}{u+2}} \]

但目前为止还没有精确的显式表达式。

集聚系数

WS模型
对于WS模型来说，当重新连接概率 $p=0$ ，对应的最近邻耦合规则网络的集聚系数不受网络阶数 $N$ 大小的影响，而仅仅受其拓扑连接方式影响。此时，每个节点在右两边各有 $K/2$ 个邻近节点，容易得到这些邻近节点间的连接数为 $N_0=3(K/2)[K/2-1]/2$ ，于是对应的集聚系数$C(0)=N_0 /[K(K-1) / 2]=3[K / 2-1] /[2(K-1)]$。对于 $p>0$ ，原先 $p=0$ 时连接节点 $\mathrm{v}_i$ 的两个邻近节点仍然作为节点 $\mathrm{v}_i$ 的邻近节点相连的概率为 $(1-p)^3$ ，偏差不超过$O\left(N^{-1}\right)$ 。于是一个节点的邻近节点之间的平均连接数为 $N_0(1-p)^3+O\left(N^{-1}\right)$。若定义近似平均集聚系数，则得: $$ C(p)=\frac{3(K-2)}{4(K-1)}(1-p)^3 $$
NW模型
$$ C(p)=\frac{3(K-2)}{4(K-1)+4 K p(p+2)} $$

WS小世界网络性质总结

对于WS小世界网络，有如下结论:

平均度:
$$ \langle\boldsymbol{k}\rangle=\boldsymbol{K} $$
链接数:
$$ L=\frac{K N}{2} $$
度分布：近似的泊松分布
平均距离：短
集聚系数：高

一方面，只要几条边的随机重连就足以减小网络的平均距离; 另一方面，几条随机重连的边并不足以改变网络的局部集聚特性。这类既具有较短的平均距离又具有较高的集聚系数的网络就是典型的小世界网络。

无标度网络

枢纽节点标志着网络中的无标度(幂律分布)性，度分布服从幂律分布的网络被称为无标度网络(一般$2 \lt \gamma \lt 3$ )

"无标度性" 指的是一个系统或过程在不同尺度下具有相同的统计特征。这意味着，如果在一个尺度下系统具有某种性质，那么在任意尺度下都将具有这种性质。例如，在一张图中看到的某些图案可以在放大后仍然看到。在这里是指网络没有内在的标度。

幂律分布的离散和连续形式

离散形式

由于节点的度是正整数， $k=0,1,2, \ldots ，$ 因此，表示一个节点正好有 $k$ 个链接的概率 $p_k$ 是一种离散形式的幂律分布: $$ \boldsymbol{p} _ {\boldsymbol{k}}=\boldsymbol{C} \boldsymbol{k}^{-\gamma} $$ 常数 C由如下归一化条件来确定: 即:

\[ \sum_ {k=1}^{\infty} p_k=1 \]

$$ C \sum_ {k=1}^{\infty} k^{-\gamma}=1 $$ 因此，

\[ C=\frac{1}{\sum_ {k=1}^{\infty} k^{-\gamma}}=\frac{1}{\zeta(\gamma)} \]

其中, $\zeta(\gamma)$ 是黎曼泽塔函数。因此，对于任意 $\boldsymbol{k}>\mathbf{0}$ ，离散形式的幂律分布为: $$ p_k=\frac{k^{-\gamma}}{\zeta(\gamma)} $$

连续形式

连续形式: 方便起见, 在进行解析计算时, 通常会假设度可以是任意正实数。在这种情况下, 可以把幂律度分布写成:

\[ \boldsymbol{p}(\boldsymbol{k})=C k^{-\gamma} $$ 使用归一化条件 $$ \int_{k_ {\min }}^{\infty} p(k) d k=1 $$ 可以得到 $$ C=\frac{1}{\int_{k_{\min }}^{\infty} k^{-\gamma} d k}=(\gamma-1) k_{\min }^{\gamma-1} $$ 因此, 度分布的连续形式为: $$ p(k)=(\gamma-1) k_{\min }^{\gamma-1} k^{-\gamma} \]

最大度

为了得到最大度的期望大小，先对指数分布进行计算:

\[ \boldsymbol{p}(\boldsymbol{k})=\boldsymbol{C} \mathrm{e}^{-\lambda \mathbf{k}} \]

对于最小度为 $k_ {\min }$ 的网络，由归一化条件 $\int_{k_{\min }}^{\infty} p(k) d k=1$ 可以得出 $C=$ $\lambda e^{\lambda k_{\min }}$ 为了计算 $k_{\max }$, 我们假设大小为 $\mathrm{N}$ 的网络中最多有一个节点在范围 $\left(k_{\text {max }}, \infty\right)$内。换句话说，假设观察到有一个节点的度超过 $k_{\text {max }}$ 的概率为 $1 / N$ :

\[ \int_{k_ {\max }}^{\infty} p(k) d k=\frac{1}{N} \]

由上述公式可以得到:

\[ k_{\max }=k_{\min }+\frac{\ln N}{\lambda} \]

由于 $\ln N$ 关于系统大小 $N$ 增长的很缓慢，因此最大度 $k_{\text {max }}$ 和最小度 $k_{\min }$ 之间的偏差并不明显。

当度分布为泊松分布时，上述计算较为复杂，但得到的 $k_{\text {max }}$ 关于 $N$ 的依赖关系甚至比对数依赖增长的更慢。
对于无标度网络，根据上述公式可以得出自然截断为:

$$ \boldsymbol{k}_ {\max }=\boldsymbol{k}_ {\min } N^{\frac{1}{\gamma-1}} $$ 因此，网络越大，其最大枢纽节点的度就越大。$k_{\text {max }}$对于$N$的多项式依赖意味着，在大型无标度网络中，最大度 $k_{\text {max }}$ 和最小度 $k_{\min }$ 之间可能存在几个数量级的差异。

平均距离(超小世界性质)

同等条件下, 无标度网络中节点间的平均距离比随机网络中节点间的平均距离要小。

\[ \langle d\rangle \sim\left\{\begin{array}{cc} \text { const. } & \gamma=2 \\ \ln \ln N & 2<\gamma<3 \\ \frac{\ln N}{\ln \ln N} & \gamma=3 \\ \ln N & \gamma>3 \end{array}\right. \]

度指数

异常情形 $(\gamma<2)$
无标度情形 $(2<\gamma<3)$: $\langle k\rangle$ 是有限的, $\left\langle k^2\right\rangle$ 是发散的。
随机情形 $(\gamma>3)$ $\langle k\rangle$ 和 $\left\langle k^2\right\rangle$ 都是有限的。

编程实践

生成符合幂律分布的随机序列
利用配置模型生成给定度分布指数的无标度网络
利用隐参数模型生成给定度分布指数的无标度网络
度保持的网络随机化
幂律分布绘制与估计: 对数分箱

BA无标度网络

Barabási和Albert指出现实中的网络有两个方面在以前的网络模型中末包含进去。首先，决有考虑现实网络的增长特性 (网络的规模是不断扩大的）。其次，没有考虑现实网络的优先连接特征(新的节点更倾向于与那些具有较高度的 “大" 节点相连接)。

他们证明了在这两个基本假定的基础上，网络必然最终发展成无标度网络，即BA网络模型。基于网络的增长和优先连接特征，BA无标度网络模型的构造算法如下:

增长：从一个具有 $m_0$ 个节点的网络开始，每次引入一个新的节点，与 $m$ 个已存在的节点相连，这里 $m \leq m_{0}$ 。
优先连接: 一个新节点与一个已经存在的节点 $\mathrm{v}_i$ 相连接的概率 $\Pi_i$ 与节点 $\mathrm{v}_i$ 的度 $k_i$ 成正比，即 $$ \Pi_i=\frac{k_i}{\sum_j k_j} $$

BA无标度网络的动力学

根据增长性和择优选择，网络将最终演化成一个标度不变的状态，即网络的度分布不随时间而改变 (同样也就是不随网络节点数 $N$ 而改变 )，经计算得到度值为 $k$ 的节点的概率正比于幂次项 $k^{-3}$ 。下面对该结论作适当的证明。在BA模型中，从网络中某一节点 $\mathrm{v}_i$ 的度值 $k_i$ 随时间变化的角度出发，假设其度值连续，有如下方程

\[ \frac{\partial k_i}{\partial t}=m \prod_i=m \frac{k_i}{\sum_j k_j} \]

由于每一时间步，我们加入 $m$ 条边，即网络总度值增加 $2 m$ ，于是第$t$步的总度值为

\[ \sum_j k_j=2 m t \]

因此， $$ \frac{\partial k_i}{\partial t}=\frac{k_i}{2 t} $$ 解方程得 $$ \ln k_i(t)=C+\ln t^{\frac{1}{2}} $$ 由初始条件，节点 $v_i$ 在时刻 $t_i$ 以 $k_i\left(t_i\right)=m$ 加入到系统中，可以得到

\[ C=\ln \frac{m}{t_i^{1 / 2}} $$ 因此， $$ k_i(t)=m\left(\frac{t}{t_i}\right)^{1 / 2} \]

可以得到节点连接度 $k_i\left(t_i\right)$ 小于某定值 $k$ 的概率为

\[ P\left(k_i(t)<k\right)=P\left(t_i>\frac{m^2 t}{k^2}\right) \]

假设我们等时间间隔地向网络中增加节点，则 $t_i$ 值就有一个常数概率密度

\[ P_i\left(t_i\right)=\frac{1}{m_0+t} \]

综合上式，可以得到

\[ P\left(t_i>\frac{m^2 t}{k^2}\right)=1-P\left(t_i \leq \frac{m^2 t}{k^2}\right)=1-\sum_{t_i=1}^{\frac{m^2 t}{k^2}} P\left(t_i\right)=1-\frac{m^2 t}{k^2\left(m_0+t\right)} \]

所以度值的分布 $P(k)$ 为

\[ P(k)=\frac{\partial P\left(t_i>\frac{m^2}{k^2} t\right)}{\partial k}=\frac{2 m^2 t}{m_0+t} \cdot \frac{1}{k^3} \]

当 $t \rightarrow \infty$ 时， $P(k)=2 m^2 k^{-3}$ ，完全符合幂律分布。

根据前面的理论可得，BA无标度网络的度分布满足 $$ p(k) \approx 2 m^{1 / \beta} k^{-\gamma} $$

其中 $$ \gamma=\frac{1}{\beta}+1=3 $$ 即 $p(k) \sim k^{-3}$

生长或偏好连接的缺失(生长+随机连接)

一个新节点和度为 $k_i$ 的节点相连的概率为: $$ \Pi\left(k_i\right)=\frac{1}{\left(m_0+t-1\right)} $$

也就是说， $\Pi\left(k_i\right)$ 和节点度 $k_i$ 无关。这表明，新节点是随机选择节点进行连接的。根据连续介质理论可以推出, 模型 $\mathrm{A}$ 中 $k_i(\mathrm{t})$ 随时间呈对数增长:

\[ k_i(t)=m \ln \left(e \frac{m_0+t-1}{m_0+t_i-1}\right) \]

这比幂律增长要慢得多。模型所得的度分布服从指数分布:

\[ p(k)=\frac{e}{m} \exp \left(-\frac{k}{m}\right) \]

非线性偏好连接

$$ \Pi_i=\frac{k_i^\alpha}{\sum_j k_j^\alpha} $$

直径和集聚系数

直径
对于BA网络而言, 当 $m>1$ 并且 $N$ 较大时, 网络直径为: $\langle d\rangle \sim \frac{\ln N}{\ln \ln N}$

因此，网络直径的增长要比$\ln N$慢，也就是说，BA网络的直径要比同等大小的随机网络的直径小, 当 $N$ 较大时, 这一差异更加明显。网络平均距离 $\langle d\rangle$ 的情形也与之类似。
集聚系数
BA网络的集聚系数为:

$$ \langle C\rangle \sim \frac{(\ln N)^2}{N} $$ 上式和随机网络中集聚系数对 $1 / \mathrm{N}$ 的依赖关系大不相同。差异主要来自 $(\ln N)^2$, 这一项在 $\mathrm{N}$ 较大时大大增加了集聚系数。因此, BA网络的集聚系数比随机网络的集聚系数要高。

性质总结

节点数: $N=t$
链接数: $N=mt$
平均度: $\langle k\rangle=2 \mathrm{~m}$
度动力学: $k_i(\mathrm{t})=\mathrm{m}=\left(\frac{\mathrm{t}}{t_i}\right)^\beta \quad$
动态指数: $\beta=1 / 2$
度分布: $p_k \sim k^{-\gamma}$
度指数: $\gamma=3$
平均距离: $\langle d\rangle \sim \frac{\ln N}{\ln \ln N}$
集聚系数: $\langle C\rangle \sim \frac{(\ln N)^2}{N}$

网络鲁棒性

渗流理论

移除单一节点对网络完整性的影响是有限的。然而，如果移除网络中的多个节点，就可以把一个网络拆分成多个独立的连通分支。于是，我们不禁要问: 要移除多少个节点，我们才能把一个网络分解成一些相互独立的连通分支呢? 例如：在互联网中，要破坏多少路由器，我们才能把互联网分解成相互不能沟通的计算机集群(簇)呢? 若想回答这些问题，我们必须先熟悉研究网络鲁棒性的数学基础一一渗流理论 (percolation theory).

为了量化这个相变的性质，我们专注于三个量:

簇的规模平均值: $\langle s \rangle$
根据渗流理论，全体有限规模的簇的规模的平均值遵循: $$ \langle\boldsymbol{s}\rangle \sim \left|\boldsymbol{p}-\boldsymbol{p}_ c\right|^{-\gamma_p} $$ 换句话说, 在接近 $\mathrm{p}_ {\mathrm{c}}$ 时，簇的规模的平均值是发散的。
序参量: $P_{\infty}$
随机选择一个石子，序参量 $\mathrm{P}_ {\infty}$ 是这个石子属于最大簇的概率，它遵循: $$ \boldsymbol{P}_ {\infty} \sim\left(\boldsymbol{p}-\boldsymbol{p}_ c\right)^{\beta_p} $$ 因此，当 $p$ 逐渐咸小到 $p_c$ 时，一个石子属于最大簇的概率降为零。
关联长度： $\xi$
属于同一簇的两颗石子之间的平均距离，它遵偱: $$ \xi \sim\left|\boldsymbol{p}-\boldsymbol{p}_{\boldsymbol{c}}\right|^{-v} $$

逆渗流相变与鲁棒性

综上所述，随机移除节点对网络造成的破坏并不是一个渐进的过程。相反，移除一小部分节点对网络完整性的影响非常有限。但一旦被移除节点的比例达到一个临界阈值，网络就会迅速地分解为不相连的连通分支。换言之，随机移除节点引发了网络从连通到碎片的相变。

在规则网络和随机网络中，我们都可以使用渗流理论的工具来刻画这种相变。然而，对无标度网络来说，上述现象的核心部分发生了变化。

网络鲁棒性

牵一发而动全身，网络中的某些节点(或节点集)一旦被移除(或攻击)，就会对网络的连通性(或鲁棒性)产生雪崩式的影响。如何寻找到这样的节点(或节点集)是网络科学中非常重要的课题。

网络的鲁棒性：也称健壮性，是指网络在受到外界攻击的情况下，是否能够保持其功能的正常运转，如果能，就称网络是鲁棒的。复杂系统的鲁棒性是许多领域的一个重要问题。

经典方法及其效果:

初始网络的最大度(High Degree, HD)
当前网络的最大度(High Degree Adaptive, HDA): 不断从网络中移除度值最高的节点及其连边作为影响力节点，同时更新计算所有节点的度排序
当前网络的最大介数(HBA)
网络的k-核(k-core)
集体影响度量(Collective Influence, CI)

\[ \mathrm{CI}_ {\ell}(i)=\left(k_i-1\right) \sum_{j \in \partial \operatorname{Ball}(i, \ell)}\left(k_j-1\right) \]
ER随机网络与无标度网络下的实验结果
真实网络下的实验结果

网络上的传播现象

流行病建模

两种假设

可划分性假设: 流行病模型按照个体所处的发病阶段对其进行分类，最简单的划分方式假设每个个体都处于以下三种阶段之一:
1. 易感染(S): 尚末接触病原体的健康个体
2. 已感染(I): 已接触病原体并能感染他人的个体
3. 已康复(R): 感染后康复的个体，不具备感染能力
均匀混合假设: 认为每个个体将以相同的概率接触已感染的个体。这一假设使得我们不必知道确切的疾病传播所依赖的接触网络，而认为任何人都可以感染其他人。

SI模型

SIS模型

SIR模型

网络上的流行病模型

对于接触网络，显然均匀混合假设是错的，且由于网络是无标度的，平均度$\langle k\rangle$也没有意义。【推荐使用EoN(Epidemics on Networks)库做仿真】

SI模型

SIS模型

网络中的社团结构

在网络科学中，如果一组节点内部链接紧密，外部链接稀疏，那么我们称这组节点为一个社区或社团 (community)。

两个假设:

基础假设: 网络的社区结构仅由其连接模式决定
根据该假设，网络的社区结构可以通过检查网络邻接矩阵 $A_{i j}$ 来发现。
连通性和密度假设: 社区是网络中局部紧密连接的子图
一个社区中的所有成员都可以通过同一社区中的其他成员到达（连通性）。同时，我们希望一个社区内部的节点连接到同一社区中其他节点的概率高于连接到不在同一社区的节点的概率 (密度)。

社团基础知识:

常见的社团划分/节点聚类算法:

Louvain算法
Louvain算法是一种基于模块度(Modularity)的节点聚类方法，通过不断合并具有高模块度的节点 communities，直到不能再进行有意义的合并为止。Louvain算法并不需要预设节点数目，且运行速度快。在networkx库中，可以使用community_louvain函数实现Louvain算法。
Girvan-Newman算法 Girvan-Newman算法也是一种常用的节点聚类方法，其思想是“边介数减少”(Betweenness)计算边介数，并按照从高到低的顺序逐步删除边，从而将网络划分为多个连通组件。具有高边介数的边，往往连接了两个不同社区的节点，其删除可以将两个社区分离。在networkx库中，可以使用girvan_newman函数实现Girvan-Newman算法。
Label Propagation算法 Label Propagation算法也是一种基于社区传播的聚类方法，在该算法中，每个节点被分配一个标签，该标签将在社区中传播，直到没有新节点可以转变为另一个社区为止。在networkx库中，可以使用label_propagation_communities函数实现Label Propagation算法。
活性子群算法（Active Group）算法活性子群算法也是一种基于社区传播的聚类方法。该算法将网络划分为一些子集，每个子集中的节点与其他节点的连接强度更高，即“聚在一起”。在networkx库中，可以使用asyn_fluidc函数实现活性子群算法。

本站服务

图论基础

常见网络

图论基础

复杂网络的统计特征

网络的基本静态几何特征

度分布与常见的度分布

网络的直径、平均距离、集聚系数以及度度相关性

介数与核数

网络密度

几种常见的中心性指标

度中心性

介数中心性

接近度中心性

特征向量中心性

PageRank中心性

半局部中心性

ClusterRank

有向网络和加权网络的静态特征

有向网络

加权网络

随机网络

规则网络

ER随机网络的生成算法

ER随机网络结构特性

度分布

性质总结

小世界网络

小世界网络模型

小世界现象：六度分隔

小世界模型构建算法

小世界网络的结构特性

平均度

平均距离

集聚系数

WS小世界网络性质总结

无标度网络

幂律分布的离散和连续形式

离散形式

连续形式

最大度

平均距离(超小世界性质)

度指数

编程实践

BA无标度网络

BA无标度网络的动力学

生长或偏好连接的缺失(生长+随机连接)

非线性偏好连接

直径和集聚系数

性质总结

网络鲁棒性

渗流理论

逆渗流相变与鲁棒性

网络鲁棒性

网络上的传播现象

流行病建模

两种假设

SI模型

SIS模型

SIR模型

网络上的流行病模型

SI模型

SIS模型

网络中的社团结构

网络科学的研究方向