【文献阅读】网络复杂系统演化历史的重建

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

导读：

想象一下，你是一位
侦探
，面前放着一张庞大的、已完成的
社交网络图
。你清楚谁与谁是朋友（这便是
“最终结构”
）。然而，你并不知道他们是如何成为朋友的，谁先结识了谁（这便是
“发展历史”
）。传统的侦探只能猜测：“或许人际关系好的人朋友较多？”（这类似于以往的理论只能解释“偏好链接”这一现象）。但现在，你发明了一台
“社交关系时光机”
。这台时光机的工作原理如下：

1. 选取一个“参考区域”作为训练：
   你首先选定一个你非常熟悉的区域（我们称之为
   A区
   ），你了解这个区域内部分人群成为朋友的时间顺序。你让这台“时光机”深入学习A区的数据，学习的目标十分明确：
   随机选取两对朋友关系，它能够判断出哪一对关系建立得更早。
   它是如何判断的呢？
   它会关注许多细节，例如：
   这两人是否有大量的共同好友？（
   共同邻接
   ）
   这两人是否都是社交核心？（
   节点度
   ）
   他们是否处于同一个紧密的小团体中？（
   社群结构
   ）
   通过分析成千上万对类似的关系，这台“时光机”自行总结出一套
   “评估朋友关系新旧的隐性规则”
   。
2. 解析未知区域的历史：
   现在，将这台训练好的“时光机”应用于一个你完全不了解历史的新区域（
   B区
   ）。你仅提供B区最终的朋友关系图给时光机。
   这时，奇迹出现了：
   时光机利用在A区学到的“隐性规则”，开始分析B区的每一对朋友关系。
   尽管它在单次对比（A和B谁先成为朋友？）上的准确性可能仅略高于随机选择（例如55%的正确率），但在全面比较
   所有关系
   后，通过一种“多数决”的排序方式，它几乎可以
   非常精确地
   还原整个B区的朋友关系建立顺序！
3. 这台“时光机”能带来哪些惊喜？
   发现模式：
   还原历史后，你发现B区确实是由“社交高手”后来居上成为大家的核心（验证了
   偏好链接
   ），并且人们通常先在小团体内部成为朋友，然后才向外扩展（揭示了
   社群结构
   的发展）。这些是以往单一理论无法解释的现象。
   预测未来：
   了解了过去的关系顺序，你甚至可以更准确地预测
   未来谁最有可能成为朋友
   （这就是
   链接预测
   ）。
   解读生命：
   如果将“区域”替换为“蛋白质”，将“朋友关系”替换为“蛋白质相互作用”，我们就可以解读
   生命的发展历程
   ，例如细胞哪些功能先出现，哪些后出现。

论文基本信息

标题
：Reconstructing the evolution history of networked complex systems

发表年份
：2024年

作者
：Junya Wang, Yi-Jiao Zhang, Cong Xu, Jiaze Li, Jiachen Sun, Jiarong Xie, Ling Feng, Tianshou Zhou, Yanqing Hu

作者单位
：中山大学、南方科技大学、腾讯、北京师范大学、新加坡高性能计算研究所等

期刊
：
Nature Communications

研究目的

本研究旨在从复杂网络的
最终形态
中重建其
发展历史
，即恢复网络中边的生成顺序。通过理解网络的形成过程，揭示其结构特点（如社群结构、局部集群、偏好链接等）的发展机制，并促进网络结构预测等应用。

方法

简单来说，该方法的核心在于：
通过先进的图形表示学习技术将边编码为向量 -> 利用专为比较任务设计的CPNN集成模型进行精确的两两顺序判断 -> 最终通过Borda计数这一民主“投票”机制，将分散的两两比较结果汇总成一个可靠的全局发展序列。这种方法巧妙地规避了直接对长期发展过程建模的难题，而是将其分解为大量可解决的二分类问题，从而实现了从静态网络结构逆推动态历史的重大突破。

第一阶段：边表示学习 - 将边转换为特征向量
目标：将网络中的每条边表示为一个机器可读的、包含拓扑信息的向量。
基于节点嵌入的方法：
使用多种图形嵌入算法（如 Node2Vec, DeepWalk, LINE, SDNE, Struct2Vec），将网络中的每个
节点
映射为一个低维向量。
对于连接节点

u

和

v

的边，其向量表示通过计算两个节点向量的
Hadamard乘积
（即对应元素相乘）获得。这种方法能够捕捉边所连接的两个节点的局部和全局拓扑信息。
基于传统边特征的方法：
同时，也计算一组11个经典的、手工设计的边特征（例如共同邻居数、Jaccard系数、Adamic-Adar指数等）。
最终，每条边都有6个来自不同节点嵌入方法的向量和1个传统特征向量，为后续的集成学习提供了丰富且互补的特征视角。

第二阶段：集成模型预测 - 判断两条边的先后
目标：构建一个模型，输入两条边的特征，输出“边i晚于边j”的概率。
模型架构：比较范式神经网络：
核心模型是
CPNN
。这是一种专门用于
比较两个样本
的神经网络。
工作原理：
将两条边

i

和

j

的向量表示（例如，都使用Node2Vec方法获得的向量）同时输入到CPNN中。网络学习它们之间的差异特征，并输出一个概率值

o_i^l

，表示“边i晚于边j”的可信度。

集成策略

为何要集成？不同的嵌入技术揭示了网络结构的不同方面，通过集成可以综合各种方法的优势，增强模型的稳定性和精确度。

如何实现集成？作者采用了6种节点嵌入方法，从而构建了6个CPNN模型。此外，还从11个传统特征中挑选了一个在训练集上表现最佳的作为第7个模型（一个基于阈值的简单比较器）。

最终输出：将这7个模型的输出进行加权平均，得出最终的概率。

o_{ij}^{final}

权重通过在训练集上进行网格搜索确定。

CPNN

CPNN 是本文的核心神经网络模型，其全称是 Comparative Paradigm Neural Network。

CPNN 属于“孪生神经网络”的一种变体。其主要设计目的是：不关注单个样本的具体属性，而是专注于判断两个样本之间的相对关系。

在此文的背景下，这种“相对关系”指的是：“两条边，哪一条较晚加入网络？”

工作原理解析：

双塔结构： 两个输入（边i和边j的向量）分别通过两个结构相同且共享权重的神经网络（即“孪生”或“双塔”）。这意味着两条边被平等对待，网络不会因输入顺序不同而产生偏见。

特征提取： 每个塔都是一个多层感知器，其功能是将输入的边向量映射到一个更高维度、更抽象的特征空间，从中提取用于比较的深层次特征。

比较层： 这是至关重要的一步。将两个塔输出的特征向量

f_i

和

f_j

进行拼接，并加入它们的绝对差

|f_i - f_j|

。这个差值向量极大促进了网络关注两者之间的差异特征，这是判断其相对顺序的关键。

决策层： 拼接后的向量再经过几层全连接网络，最终通过一个Sigmoid激活函数输出一个介于0到1之间的概率值。这个值代表了模型认为“边i晚于边j”的可信度。

阶段三：全局排序 - 从两两比较到全局序列

目标：将模型输出的所有边的“两两比较”结果，整合成一个全局的、有序的边生成序列。

构建比较矩阵： 使用训练好的集成模型，对网络中所有可能的边对进行预测，生成一个比较矩阵。这个矩阵实际上记录了在所有“投票”中，每条边被认为比另一条边“更新”的次数。

Borda计数排序：

Borda计数： 对于每条边

i

，其Borda得分为：

u_i = ∑_{j≠i} u_{ij}

，其中

u_{ij} = 1

如果模型预测

i

晚于

j

，否则为0。

简单理解： 这类似于一场选举，每条边都在与其他所有边竞争“谁更晚出现”。每赢得一次，就得一分。最终的总得分（Borda计数）代表了该边在序列中的“新近程度”。

生成序列： 最后，将所有边按其Borda计数从小到大进行排序，计数最小的边是最早出现的，计数最大的边是最晚出现的。这样就得到了重建的整个网络的边生成序列，即演化历史。

模型训练与验证全流程

数据准备

输入数据：

网络最终拓扑结构： 一个静态的网络图

G = (V, E)

，其中

V

是节点集合，

E

是边集合。静态拓扑是生成所有特征信号的“源数据”。

算法如Node2Vec、DeepWalk会在该静态网络上进行随机游走，学习每个节点的低维向量表示。这些向量捕获了节点在网络中的结构角色（如中心节点、边缘节点、桥梁节点等）。

部分边的历史信息： 对于网络中的一小部分边，我们知道它们确切的生成时间或相对顺序（通常来自多个时间快照）。

数据预处理：

边对生成： 从已知历史的边中，生成训练所需的边对

(edge_i, edge_j)

。

标签生成： 对于每个边对，根据真实历史，打上标签：

标签 = 1：如果

edge_i

比

edge_j

晚出现

标签 = 0：如果

edge_i

比

edge_j

早出现

边对生成的具体流程：

步骤1： 获取带时间戳的边数据 假设我们有一个网络，在5个时间点被观测到（5个快照）：

T0: 边集 E0 = {e1, e2, e3}

T1: 边集 E1 = {e4, e5, e6}

T2: 边集 E2 = {e7, e8, e9}

T3: 边集 E3 = {e10, e11}

T4: 边集 E4 = {e12, e13, e14} # 最终状态

关键规则： 每条边的“生成时间”被定义为它首次出现的快照时间戳。

步骤2： 确定可比较的边对 从所有可能的边对中，只选择那些生成时间不同的边对：

可比较的：

(e1, e4)

,

(e1, e7)

,

(e2, e10)

... （因为生成时间不同）

不可比较的：

(e1, e2)

,

(e4, e5)

,

(e10, e11)

... （因为生成时间相同）

步骤3： 生成训练样本 对于每个可比较的边对

(edge_i, edge_j)

，我们创建一个训练样本：

输入：

(edge_i的向量, edge_j的向量)

标签：基于它们的真实生成时间

训练/测试集划分： 随机选择一定比例（如1%, 5%, 10%等）的边对作为训练集，其余作为测试集。

注意：这里划分的是边对，而不是边本身，确保训练和测试集包含所有边的组合信息。

真实网络数据的边生成机制： 在现实世界中，我们

不了解也不掌控边的具体生成策略。这正是研究的核心价值所在——从数据中学习实际的演化机制，而不是假定某种机制。真实网络边的“生成策略”是未知且多样的：

• PPI网络：可能融合了基因共表达、功能相似性和进化保守性等复杂因素
• 合作网络：可能融合了研究领域匹配、地理位置接近和社会关系等因素
• 贸易网络：可能融合了经济互补性、政治关系和地理距离等因素

这正是机器学习旨在解决的问题：我们不事先假设网络是随机增长、偏好连接还是其他机制，而是让模型从数据中自主发现实际的演化规律。

让我用一个实际的PPI网络案例来说明：假设我们有一个真菌PPI网络的五个观测快照：

• 2000年：检测到150个相互作用
• 2005年：新增80个相互作用
• 2010年：新增120个相互作用
• 2015年：新增90个相互作用
• 2020年：新增60个相互作用（最终状态）

训练数据生成步骤：

• 确定边的时间戳：
  2000年检测到的150条边：时间戳 = 1
  2005年新增的80条边：时间戳 = 2
  2010年新增的120条边：时间戳 = 3
  2015年新增的90条边：时间戳 = 4
  2020年新增的60条边：时间戳 = 5
• 生成可比较边对：
  

  (边_2000, 边_2005)

  → 标签 = 0（因为2000年的边更早）
  

  (边_2000, 边_2010)

  → 标签 = 0
  

  (边_2005, 边_2010)

  → 标签 = 0
  

  (边_2010, 边_2015)

  → 标签 = 0
  

  (边_2015, 边_2020)

  → 标签 = 0
  以及所有反向组合获得标签 = 1
• 排除不可比较的：
  同一年份检测到的边对不用于训练（因为不清楚确切顺序）

模型网络的边生成策略

虽然模型网络不用于训练，但论文在验证迁移学习时使用了它们，这些模型具有明确的边生成策略：

1. Barabási-Albert (BA) 模型
   节点添加：每次添加一个节点
   边生成策略：偏好连接 - 新节点连接到现有节点

   i

   的概率与节点

   i

   的度成正比
   数学表达：

   Π(ki) = ki / Σj kj

2. Fitness 模型
   节点添加：每次添加一个节点
   边生成策略：新节点连接到节点

   i

   的概率与

   η_i × ki

   成正比，其中

   η_i

   是节点的适应度
3. Popularity-Similarity Optimization (PSO) 模型
   在双曲空间中生成，同时考虑流行度（节点年龄）和相似性（角距离）

???? 输入与输出

单个CPNN模型的输入：

• 输入1：边

  i

  的向量表示

  e_i^l

  （来自第

  l

  种嵌入方法）
• 输入2：边

  j

  的向量表示

  e_j^l

  （来自同一种嵌入方法）

单个CPNN模型的输出：

一个标量概率值

o_i^l ∈ [0, 1]

，表示“边i晚于边j”的置信度

集成模型的最终输出：

加权平均后的最终概率：

o_ij^final = Σ w_l * o_i^l

这个概率用于后续的Borda排序

???? 训练过程

训练目标：最小化二元交叉熵损失函数，使模型准确预测边对的相对顺序。

训练步骤：

• 分别训练6个CPNN：每个CPNN使用同一种嵌入方法生成的所有边向量进行训练
• 选择最佳单特征：在11个传统边特征中，选择在训练集上预测准确率最高的一个
• 确定集成权重：通过网格搜索，找到使集成模型在验证集上性能最优的权重组合

  {w_1, w_2, ..., w_7}

关键训练参数：

• 训练比例：仅需 1%-5% 的边对即可达到满意性能（图2a）
• 训练停止：当准确率在验证集上饱和时停止

???? 验证过程与结果

1. 边对预测准确率（中间指标）
   验证指标：配对准确率

   x

   x = (#正确预测的边对) / (总测试边对数)

   
   结果（图2a）：
   仅使用 0.5% 的边对训练，准确率已达 ~65%
   使用 5% 的边对训练，准确率饱和于 75%-80%
   随机猜测的基线准确率为50%
2. 整体序列重建误差（最终指标）
   验证指标：归一化均方根误差

   E

   （公式1）
   理论关系（公式2）：
   E_theory = √[x(1-x)] / (2x-1) * 1/√E
   其中

   E

   是边的总数
   关键发现：
   误差

   E

   与

   1/√E

   成正比 → 边数越多，重建越准确
   即使配对准确率

   x

   仅略高于50%，只要边数足够大，整体误差仍然很小
   例如：当

   E=10,000

   ，

   x=0.6

   时，理论误差

   E ≈ 0.005

   （非常小）
3. 误差分布分析（图2c-e）
   方法：分析

   D_i/E = (真实位置 - 预测位置) / 总边数

   
   结果：
   误差分布呈 对称的钟形，中心在0附近
   分布宽度随

   x

   增加而减小，随

   E

   增加而减小
   真实数据与模拟结果高度一致，验证了理论关系的正确性
4. 迁移学习验证（表1）
   设置：
   训练网络：BA模型（N=500）
   测试网络：BA模型（N=1000）、PSO模型、Fitness模型
   结果对比：
   直接验证（不进行特征对齐）：准确率

   x^d ≈ 0.69

   
   迁移学习（进行线性变换对齐）：准确率

   x^t ≈ 0.85

   
   提升幅度：约16个百分点，证明特征空间对齐的有效性
5. 下游任务验证
   链接预测性能（图6）：

利用重建的边序列，链接预测的准确率提升了21.1%-67.6%

在PPI（细菌）网络上表现尤为突出

网络机制重现（图4,5）：

• 重建的序列能够精确再现：
  - 偏好连接现象（与实际网络强度相符）
  - 社区结构的发展
  - 度相关性（同配/异配性）
  - 局部聚类系数的变化
• 纯PA规则生成的序列在这些特性上与实际网络存在显著差异

核心验证结论：

• 可行性：只需少量的历史信息（5%边对）就能高精度重建完整的演化历史
• 可扩展性：该方法对大型网络尤其有效（误差随边数增加而减少）
• 泛化能力：通过迁移学习，可以将模型应用于没有历史信息的类似网络
• 实用性：重建的历史在链接预测和机制分析中具有重要应用价值
• 稳健性：对时间分辨率较低的实际网络数据仍然有效

此验证框架不仅证明了方法的有效性，更重要的是建立了从中级指标（配对准确率x）到最终性能（总体误差E）的理论联系，为方法的应用提供了理论指导。

验证的三个层次

论文实际上进行了三个不同层次的验证，每个层次的目的和适用性都不同：

层次1：在同一个实际网络上验证（主要验证）

这是最重要、最核心的验证，直接回答“用实际网络训练，学到的规律是否适用于实际网络”。

方法：
- 在一个有部分历史信息的实际网络（如PPI网络）上训练模型
- 在同一网络的未见过的边对上测试模型性能
- 评估指标：边对预测准确率

x

、整体序列误差

?

结果：
- 图2a, 2b, 2c, 2d, 2e 都展示了在实际网络上的性能
- 例如：在合作网络、PPI网络、世界贸易网等实际网络上，模型都能准确重建演化历史
- 实际世界观测数据：
- PPI网络：通过不同时期的生物学实验数据，了解某些蛋白质相互作用在哪个时间点被发现
- 合作网络：通过论文发表时间，了解作者间的合作关系在何时建立
- 贸易网络：通过年度贸易数据，了解国家间贸易关系何时开始

层次2：在模型网络上验证迁移学习

这是补充性验证，目的是在受控环境中测试方法的理论可行性。论文中的迁移学习不是通过微调进行的，而是一种特征空间对齐 + 直接应用的方法。

在实际网络中，我们无法知道“真实”的演化机制。但在模型网络中，我们知道ground truth：
- BA模型：我们知道边确实是按偏好连接规则生成的
- ER模型：我们知道边确实是随机生成的
- PSO模型：我们知道边确实是按流行度-相似性优化的

这样我们就可以定量评估重建序列与真实生成机制的吻合程度。

表1的迁移学习结果实际上证明了：只有当训练网络和测试网络具有相似的生成机制时，迁移学习才有效。

例如：
- 在BA模型上训练，在BA模型上测试 → 效果好
- 在BA模型上训练，在PSO模型上测试 → 效果相对较差

这反过来暗示：实际网络中，同类型的网络可能共享相似的演化机制。

层次3：在相似的实际网络间迁移验证

作者们自己承认，当前的迁移学习技术仅在人工合成的模型网络上验证成功，而将其应用于实际世界网络还需要进一步探索。

在模型网络上验证迁移学习的具体步骤：

1. 在源网络(Network A)上训练
   - 使用Network A的最终拓扑和部分边历史信息训练得到集成模型（6个CPNN + 最佳特征）
   - 同时得到Network A的节点嵌入矩阵

   H_A

2. 特征空间对齐（核心）
   - 这是迁移学习成功的关键，目的是让两个网络的向量表示在同一个空间里可比。
   - 具体操作：
   - 对两个网络的节点按度排序
   - 将Network A和Network B的节点分别按度值降序排列
   - 取前k个节点（k = min(|V_A|, |V_B|)）
   - 构建节点嵌入矩阵

   H_A

   ：Network A前k个节点的嵌入向量矩阵
   - 构建节点嵌入矩阵

   H_B

   ：Network B前k个节点的嵌入向量矩阵
   - 求解线性变换矩阵L
   - text L = (H_B^T · H_B)^{-1} · H_B^T · H_A
   - 这个最小二乘解使得

   H_B · L ≈ H_A

3. 变换目标网络表示
   - 将Network B所有节点的嵌入向量通过L变换：
   - text H_B' = H_B · L
   - 然后用变换后的节点向量计算Network B的边向量（Hadamard乘积）
4. 直接应用模型
   - 不进行任何微调
   - 直接将Network B变换后的边向量输入到在Network A上训练好的集成模型
   - 预测Network B中所有边对的相对顺序
   - 通过Borda排序得到完整的边生成序列

论文在模型网络上验证了这种迁移学习方法（表1）：

实验设置：
- 训练网络：BA模型（N=500）
- 测试网络：BA模型（N=1000）、PSO模型、Fitness模型

结果对比：
- 直接验证（不进行特征对齐）：准确率

x^d ≈ 0.69

- 迁移学习（进行线性变换对齐）：准确率

x^t ≈ 0.85

- 提升：约16个百分点

论文明确指出，这种迁移学习在实际网络中面临挑战：

当前局限性：
- 机制相似性判断困难：我们无法像模型网络那样确切知道实际网络的演化机制
- 节点对应关系模糊：按度排序建立节点对应关系可能不够精确
- 领域差异

不同实际网络间可能存在基本的结构差异。

主要结论

即便模型对边生成顺序的预测准确率仅略微超过随机猜测（>50%），也能有效重构网络的演化历程，特别是对于包含大量边的网络。重构的演化历史有助于揭示多种网络特性的共同演化机制，例如偏好连接、社群结构、局部聚集等特性，这些都是传统理论难以同步解析的。在蛋白质相互作用网络中，重构的演化过程展示了蛋白质功能模块的形成遵循一定的时序规则，由基础功能逐渐向高级功能发展。重构的边序列可以明显提高链接预测的精确度。

创新点

提出了一种基于机器学习的综合框架，可以从静态网络结构中恢复其动态演化历程。引入了迁移学习技术，使得模型能够应用于没有历史数据的网络。首次系统地重建并验证了多种实际网络（如PPI、生态系统、社交网络）的演化路径。揭示了偏好连接与社群结构的共同演化机制，超越了传统单机制模型的局限。

局限性

假设边一旦形成便不会消失，未考虑节点或边的动态消亡。对于缺少精细时间标记的实际网络，重构结果的可靠性难以直接验证。当前迁移学习主要适用于机制相似的人造或合成网络，在不同实际网络间的迁移应用还需进一步探索。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：复杂系统 文献阅读 Optimization Constructing Comparative