随机网络和相关统计量

上课所指的是G(N, p)模型的生成

假设有N个节点，每次选中其中两个节点，然后生成一个0到1之间的随机数，如果这个随机数小于p，则在这两节点直接增加一个链接，否则不放置链接

统计量：

  • 度：邻居数量

  • 平均度：所有节点度的平均数

  • 度分布：随机选取一个节点，其度值恰好为k的概率

  • 路径

  • 距离与网络直径：网络中的最大距离称为网络直径

  • 介数：通过该节点的最短路径条数（或一个节点在网络中所有最短路径中出现的频率），条数越多，说明这个节点越重要

  • 集聚系数：刻画某个节点相邻的两个节点彼此也相邻的概率

    一个度为$k_i$的节点i的聚类系数$C_i$定义为$C_i=\frac{2E_i}{(k_i(k_i-1))}$，其中$E_i$是节点i的$k_i$个邻居节点之间实际存在的邻居对的数目

    整个网络的集聚系数就是所有节点聚类系数的平均值，是一个0到1之间的值，越偏向0说明网络越松散，否则越集聚（每个节点都相连）

  • 同配性：考察度值相近的节点是否倾向于互相连接

    如果总体上度大的节点倾向于连接度大的节点（趋于和它近似的节点相连），那么就称网络的度正相关的，或称网络是同配的；如果总体上度大的节点倾向于连接度小的节点，那么就称网络的度负相关的，或者称网络是异配的

    用同配系数来度量，-1为负相关（异配性），+1为正相关（同配性），0为不存在相关

  • 邻接矩阵：描述一个网络拓扑结构

网络模型

无标度网络：是一种度分布（即对复杂网络中节点度数的总体描述）服从或者接近幂律分布（一个量是另一个量的幂次方）的复杂网络

  • BA无标度网络：首先，过去的网络没有考虑现实网络的增长特性（网络的规模是不断扩大的）；其次，没有考虑现实网络的优先连接特征（新的节点更倾向于与那些具有较高度的“大”节点相连接），基于此提出BA无标度网络，其中包含了网络的增长和优先连接特点

    • 增长：在网络中每次增加一个节点，这个节点与网络中的一部分原有节点连接（可以是全部原有，也可以仅仅是一部分）
    • 优先连接：一个新节点与一个已经存在的节点相连接的概率与节点的度成正比

  • 拷贝模型：主要是考虑到例如互联网中互相引用的静态网页，当新增一个网页，大概率是会与其他类型相似的静态网页引用相同的内容，此时就需要对网络结构进行拷贝复制

    无标度性、高聚类系数、层次结构和模块化

    • 每次增加一个新节点，对于这个新节点，选择一个母节点并复制其所有连接，最后再以一定概率删除一部分连接
    • 复制模型更加自然地模拟了基于“模仿”的连接机制，而 BA 模型强调“富者愈富”的优先连接原则

  • 配置模型：在复杂网络研究中用于生成具有特定度分布（但边的具体连接方式随机）的随机网络模型

    度分布、随机连接、无偏结构（在给定度分布的条件下具有最大随机性）

    • 给定一个网络度序列$\{k_1,k_2,\ldots,k_N\}$，然后为每一个独立的节点配置数量为$k_i$的半边，最后将所有的半边与另一节点的半边随机两两连接起来
    • 可以生成任意指定的度分布，不要求是幂律的；是一种静态模型，只需要输入度序列，无需生长机制
    • 仅能保证度的分布，但无法生成复杂结构；此外还可能会有自环和多重边的出现

  • 隐藏参数模型：通过引入一些未直接观察到的“隐藏参数”来解释节点之间的连接概率，这些隐藏参数通常代表节点的某些潜在特性或属性，这些特性影响节点之间形成连接的可能性

    灵活性、解释性、适用性

    • 为每个节点分配一个或多个隐藏参数$\theta_i$，再定义一个连接概率函数（通常就是隐藏参数的函数）$P(i,j)=f(\theta_i,\theta_j)$，然后再根据这个连接概率函数在两个节点之间生成边
    • 更关注节点的隐藏属性
    • 选择合适的隐藏参数和连接函数可能较为复杂；计算和优化隐藏参数可能需要大量的计算资源

评价网络是否同配

同配是指网络中度数大的节点更倾向于与同样度数大的节点连接

  1. 全统计描述（Full Statistical Description）

    • 使用 $e_{jk}$ 矩阵表示随机选择的边两端的节点分别具有度数 $j$ 和 $k$ 的概率

    • 如果网络没有度相关性，$e_{jk}$ 应满足特定的公式：$e_{jk} = q_j q_k$，其中 $q_k$ 是具有度数 $k$ 的节点出现在边上的概率

      也就是说，如果网络没有同配关系，那么理应有【左右两端节点概率】等于【左端节点概率】乘【右端节点概率】

    • 偏离该预测的情况可以作为度相关性的标志，即同配 / 异配

  2. 度相关函数（Degree Correlation Function）

    • 表示为 $k_{\text{annd}}(k)$，即具有度数 $k$ 的节点的邻居的平均度数
    • 这是一个度数依赖的函数，相较于全统计描述，它的参数更少且更易于解读

  3. 相关系数（Correlation Coefficient）

    • 提出者为 M. E. J. Newman，用以量化网络的度相关性。其公式是：

      $$ r = \frac{\langle jk \rangle - \langle j \rangle \langle k \rangle}{\text{normalization factor}} $$

    • $r > 0$ 表示网络是同配的（assortative），即高度节点倾向于连接其他高度节点；$r < 0$ 表示网络是异配的（disassortative），即高度节点倾向于连接低度节点

这些方法分别从不同的角度（概率分布、邻居关系和全局关联性）来分析网络的同配性和度相关性特点

加权网络

加权网络就是边有权值的网络

权值的定义很广泛，包括相异权、相似权、相关物理量、相互作用的属性等等

权统计量：

  • 权相关性

    点权：一个点所有连线权重之和

    单位权：一个点所有连线的平均权重

    权重差异性：差异性越大，离散程度越大

    • 度相关性：同向匹配网络 / 负向匹配网络（度数大小节点之间连接的倾向）

    • 点权相关性：节点的加权平均近邻度：

      $$ k_{nn,i}^w=\frac {1}{s_i} \sum_{j \in N_j}a_{ij}w_{ij}k_j $$

    • 权与度相关性：较大权重的边倾向于连接较大 / 较小度值的点

  • 最短路径：两点之间的距离与权重的关系，在无权网络中，边数最少的路径即是最短路径；在加权网络中，边的权即是路径距离

  • 集聚系数：聚类系数越大说明节点之间联系越紧密

网络鲁棒性

当复杂网络中的若干节点失能时，整个网络依然能够保持正常功能的能力称为网络的鲁棒性

  • 最大连通子图：在节点或边失效后，网络中最大的连通子图的大小可以用于衡量网络的鲁棒性，较大的连通子图意味着更高的鲁棒性
  • 平均路径长度：衡量网络中任意两个节点之间的平均最短路径长度，较短的平均路径长度通常意味着网络更具鲁棒性
  • 聚类系数：高聚类系数的网络通常更具鲁棒性
  • 连通性：高连通性的网络在节点或边失效时更不容易分裂
  • 节点和边的冗余度：冗余度高的网络在某些节点或边失效时仍能保持功能
  • 度分布：分析网络中节点的度（连接数）的分布情况，某些度分布（如幂律分布）可能使网络在特定攻击下更脆弱

社团

社团结构指的是网络中内部连接比其余部分更加密集的节点组，即社团内部的连接关系相较外部更加紧密

社团检测与划分

存在多种社团检测与划分方式，以下仅介绍几种：

最小割法

将网络分割成预定数量且大小相似的部分，选择这些部分使得节点组之间的边数达到最小

基于团结构的社团检测

团是一个无向图的完全子图，团中的每个节点都与团中的其他节点相连，节点之间的联系不可能比团更紧密。在基于团结构的社团检测中，一个节点可以同时属于多个社团

如果一个团不被其他任一团所包含，则称该团为图的极大团

基本步骤是：生成原始图的所有子图→判断这些子图是不是团→删除非极大团的其他团，将这些极大团的联合定义为子图，将其组件（断开的部分）定义为社团

自底而上的方法（层次聚类）

从网络的局部结构出发，逐步将节点或小社团合并成更大的社团的过程。这种方法从网络中的最基本单元（通常是单个节点或很小的子图）开始，通过不断合并，构建出整个网络的社团结构

定义一种相似性度量，然后量化节点对之间的相似性，按照相似性从高到低的顺序依次合并节点，构建社团结构

  • 单连接聚类：在不同群组中的所有节点对的相似度小于给定的阈值的情况下，将两个群组视为独立的社团
  • 完全连接聚类：在每个群组中的所有节点对的相似度大于给定的阈值的前提之下进行分组

自顶而下的方法

从整体网络出发，逐步将网络划分为更小社团的过程。这种方法从将整个网络视作一个大社团开始，逐渐细化划分，直到满足某种社团划分标准

典型例子就是Girvan-Newman算法，通过删除网络中重要的边来实现网络分裂：

  1. 计算网络中各边的“边介数”（此边在所有最短路径中出现的频率）
  2. 删除边介数最大的边（此边一般都是社团之间的桥梁）
  3. 递归地删除这些边，使整个网络分裂为多个子社团

此外，还有基于模块度的划分（尽力使划分后的模块度增量最大）、基于谱的划分（利用网络的拉普拉斯矩阵）等等，核心思想都是自顶而下，递归划分

节点重要性评估

评估一个节点的重要性有很多指标

  • 度中心性：一个节点的邻居数目越多，影响力就越大

    $\text{DC}(i)=\frac{k_i}{n-1}$，其中$i$指节点的度，$n$指图中节点个数，$n-1$为一个节点所能拥有的最大度数

  • 介数中心性：这个概念出现很多次了不解释，介数越大说明越重要

  • 接近中心性：一个节点与其他各节点的接近距离的平均值，越小则说明越接近其他节点、也就越重要

  • 特征向量中心性：一个节点的重要性既取决于其邻居节点的数量（即该节点的度），也取决于其邻居节点的重要性

病毒传播模型

所谓的SI模型即感染（Infection）状态与易感染（Susceptible）状态。有些还会引入移除（Recovery）状态，此时就称为SIR模型

在SI模型中，每一个易感染个体在单位时间内与感染个体发生关联且被传染的概率为β；每一个感染个体以定长速率γ再变为易感染个体，记$s(t)$为t时刻易感染个体所占比例，$i(t)$为t时刻感染个体所占比例，有：

$$ \begin{cases}\frac{ds\left(t\right)}{dt}=\gamma i\left(t\right)-\beta s\left(t\right)i\left(t\right)\\\\\frac{di\left(t\right)}{dt}=\beta s\left(t\right)i\left(t\right)-\gamma i\left(t\right)&\end{cases} $$

在这种情况下，感染个体数量的增长曲线呈S型上升，易感染个体曲线与之相对地下降

免疫策略

  • 随机免疫：完全随机地选取网络中的一部分节点进行免疫

    如果对大规模无标度网络采取随机免疫策略，需要对网络中几乎所有节点都实施免疫才能最终消灭病毒传染

  • 目标免疫：希望通过有选择地对少量关键节点进行免疫以获得尽可能好的免疫效果

    对于均匀网络，每个节点都差不多，目标免疫效果期望不高；但对于无标度网络，可以选择度数较大的节点实施免疫，如此可以将网络被分裂为碎片，使得病毒的传播存在有限的临界阈值

  • 熟人免疫

    从网络中选取 p 比例的个体进行免疫，再从被选择的个体中，随机选择他们邻居中的节点进行免疫

    在无标度网络中，度大的节点表明有许多的节点与之相连；若随机选取一个节点，在选择其邻居时，度大的节点被选中的概率要高于度小的节点。因此熟人免疫策略的可操作性要高于目标免疫，且免疫效果要高于随机免疫

参考

ChatGPT

复杂网络基础概念总结

复杂网络第八讲-加权网络

社团结构

复杂网络节点重要性算法之度和度中心性

复杂网络和传播动力学基本知识