# 翻译 从部分观测的三元动力学中重构 2-单纯形

《Physica A: Statistical Mechanics and its Applications》：Reconstructing 2-Simplexes from Partially Observed Ternary Dynamics

　　

摘要
从动力学数据重构高阶相互作用拓扑仍然是复杂系统科学中的一个基本挑战。大多数现有方法需要完整的二元或三元动力学数据，这限制了它们在不完备观测场景下的应用。为了克服这一核心限制，我们提出了一种从部分观测的三元动力学数据重构 2-单纯形的新型算法。理论上，我们的方法建立了一个通用的 M 元动力学重构框架，通过张量分解恢复不完整的多状态数据。结合贝叶斯推断和最大似然估计，制定了一种用于 2-单纯形重构的统一优化算法。在本研究中，我们在三元动力学数据上验证了所提方法，这是一个具有挑战性的非二元多状态场景。进行了大量实验以评估所提算法在三个合成和四个真实世界高阶网络上的表现，以基于完整数据的三元重构算法作为基准。结果表明，我们的方法有效放宽了传统方法固有的严格完整数据约束，并取得了增强的重构性能。在合成网络上，它仅在 3,000 步内就实现了完整的 2-单纯形重构，始终优于基准方法。在真实世界网络上，它在短时序和长时序中均表现出色，在 10,000 步时精度较基准提高 17.22%。此外，该算法对潜在因子维度表现出优异的鲁棒性和可靠性。

引言
持续的数字革命不断引入具有挑战性的复杂性，其中大多数可以有效地建模和分析为复杂系统 [1], [2], [3]。然而，在实际场景中，由于测量成本、获取困难、标注错误和隐私考虑等限制，系统的完整拓扑结构通常不可用甚至完全未知 [4], [5], [6], [7]。这一限制从根本上阻碍了对系统功能的调查。因此，准确重构复杂系统对于深入理解和有效利用至关重要，这推动了揭示和探索其拓扑结构的需求。

复杂网络历来是研究复杂系统的主要工具 [8], [9]。历史上，研究主要集中在重构复杂网络中两个节点之间的边关系（或 1-单纯形）[8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18]。当前基于已知数据的网络重构主流方法包括压缩感知 [10], [11]、噪声驱动方法 [12], [13]、机器学习 [14], [15]、自适应控制 [16], [17] 以及最大似然估计 [18], [19], [20]。这些方法主要从动力学数据分析节点的动态行为，以推断和重构节点间的二元相互作用。此外，动力学数据通常是重构网络拓扑的唯一已知条件。因此，动力学数据的完整性是确保网络重构准确性的充分条件。

然而，我们注意到在现实场景中，由于技术问题、人为因素或外部干扰，动力学数据可能不完整 [21], [22]。针对这种不完整信息下的网络重构，已进行了大量研究。Zhang 等人 [23] 提出了一种在部分可用数据下的网络重构新框架，能够从子网数据推断子网络，并通过节点变量组平均值描述组间相互作用。该方法即使存在未知的内部和外部信号，也能仅使用节点变量数据进行网络重构。Kaiser 等人 [24] 利用从部分观测数据中学到的分层社区结构，重构了多层网络中未观测部分的真实拓扑。对于带有噪声的不完整观测数据，Hu 等人 [25] 引入了分组二元混合（GBM）框架，通过广义期望最大化算法求解最大似然估计，并使用信息准则确定社区数量，从而实现网络重构和社区检测的同时进行。

现有研究主要集中于从不完整动力学数据重构节点间的二元相互作用。然而，随着研究的深入，显然许多真实世界的复杂系统不仅表现出成对相互作用，还表现出通过群体和团队实现的多变量相互作用 [26], [27]。因此，揭示和识别高阶拓扑结构已成为一个至关重要的研究方向，对于推进我们对复杂系统动力学和功能性的理解、分析和预测至关重要。目前关于高阶结构重构的研究仍处于起步阶段 [28]。现有努力主要集中在重构超图 [28], [29] 和单纯形复形 [30], [31], [32]。Jean-Gabriel Young 等人 [29] 通过引入贝叶斯方法，使用普通二元网络数据重构了潜在的高阶相互作用。Wang 等人 [30] 开发了一个整合统计推断与期望最大化的一般框架，能够从离散状态动力学生成的二元时间序列中重构 2-单纯形复形。Yu 等人 [32] 制定了三元动态传播方程，并引入了一种由三元动力学数据驱动的 2-单纯形重构算法，该算法结合了贝叶斯推断与最大似然估计。这些研究成功地从动力学数据中推断和重构了节点之间的多变量相互作用。然而，在不完整动力学数据下重构高阶拓扑结构正成为一个重要的新挑战。

此外，大多数现有研究主要依赖二元时间序列数据进行网络重构，其假设节点仅表现出两种离散状态。然而，这种二元状态数据面临双重局限性：它们无法充分捕捉真实世界复杂系统的行为复杂性和多样性，并且这些方法通常需要较长的时间序列才能达到满意的重构精度，导致数据成本高。相比之下，诸如三元数据等多状态动力学数据不仅为高阶结构重构提供了更丰富的信息，还能更准确地表示各种真实的复杂系统 [32], [33]。因此，如何从不完整的三元动力学数据中重构高阶结构仍然是一个值得深入研究的问题。

为了解决这些挑战，本文研究了基于部分观测三元动力学数据的 2-单纯形结构重构。理论上，我们在 M 元动力学框架下推导了我们的方法。首先，我们通过张量分解（矩阵分解的高维扩展）重构缺失的 M 元动力学观测。随后，利用重构后的动力学数据，我们将贝叶斯推断与 EM 算法相结合以进行 2-单纯形推断，从而提出了一种从不完整动力学数据重构 2-单纯形的新型算法。最后，我们在合成网络和真实世界高阶网络上进行了全面的 2-单纯形重构和敏感性分析实验，以基于完整三元动力学数据的重构算法作为基准。本文的主要贡献如下：
•在张量空间理论下，不完整 M 元动力学数据以张量形式表示。然后采用张量分解（矩阵分解的高维扩展）来重构缺失的 M 元动力学数据。
•开发了基于重构 M 元动力学数据的 2-单纯形推断框架，结合贝叶斯推断与期望最大化（EM）算法。
•通过整合基于张量分解的数据重构与 2-单纯形推断，提出了一种从不完整动力学数据重构 2-单纯形的新型算法。
•对比实验表明，我们的算法在合成网络上具有优越性，初期精度迅速提升，并且在真实网络上无论序列长度如何均始终有效。

本文其余部分组织如下。第 2 节演示通过张量分解重构 M 元动力学数据。第 3 节展示通过结合重构的 M 元动力学数据与贝叶斯推断及期望最大化（EM）方法进行 2-单纯形推断。第 4 节介绍基于重构动力学数据的 2-单纯形重构算法。第 5 节通过数值实验在合成和真实世界网络上评估所提重构算法。最后，第 6 节得出结论。

章节片段
基于张量分解的 M 元动力学数据重构 (TD-based-MR)
由于网络结构完全未知，且动力学数据是重构网络拓扑的唯一可用信息，因此这些数据的完整性是确保重构准确性的关键条件。然而，我们注意到，由于技术问题、人为影响或外部干扰等因素，部分动力学数据可能会缺失。这为从不完整动力学数据重构网络结构带来了巨大挑战。

从重构的 M 元动力学数据推断 2-单纯形
重构 M 元动力学数据后的状态张量定义为 $\hat{S} = (\hat{S}_{i,t,m}) \in \mathbb{R}^{N \times T \times M}$，其中 $\hat{S}_{i,t,m} (m=1,2,\cdots,M)$ 表示节点 $i$ 在时间 $t$ 处于第 $m$ 个状态的概率。为了便于确定节点状态，我们将概率向量 $\hat{S}_{i,t} = (\hat{S}_{i,t,1}, \hat{S}_{i,t,2}, \cdots, \hat{S}_{i,t,M})$ 通过公式 (19) 映射为独热状态向量 $S^*_{i,t} = (S^*_{i,t,1}, S^*_{i,t,2}, \cdots, S^*_{i,t,M})$。
$$ S^*_{i,t,m} = \begin{cases} 1, & m = \arg\max_{1 \leq k \leq M} \hat{S}_{i,t,k} \\ 0, & \text{其他} \end{cases}, \quad t=1,2,\cdots,T $$
如公式 (19) 所示，当 $m = \arg\max_{1 \leq k \leq M} \hat{S}_{i,t,k}$ 时，节点 $i$ 可以...

从重构的 M 元动力学数据进行 2-单纯形重构算法
在第 3 节中，从重构数据中提取的感染状态使得能够推导节点 $i, j$ 和 $k$ 形成 2-单纯形的概率 $P^*_{j,m,k,m \to i}$。取决于节点 $j$ 和 $k$ 的值，其中 $j \neq k \neq i, j, k = 1,2,\cdots,N$，得到序列 $\{P^*_{j,m,k,m \to i}\}^{\frac{N(N-1)}{2}}$。通过对序列 $\{P^*_{j,m,k,m \to i}\}^{\frac{N(N-1)}{2}}$ 设置阈值，我们可以消除节点 $i$ 可能属于的“假”2-单纯形，从而识别出“真”2-单纯形。
对于节点 $i$，设置截断阈值为 $\theta^*_{im} = \arg\max ...$

实验分析
用于评估 2-单纯形重构准确性的指标是 F1 值 [36]。
$$ F1 = \frac{2 \cdot Recall \cdot Precision}{Recall + Precision} $$
其中 $Recall = \frac{TP}{TP+FN}$ 和 $Precision = \frac{TP}{TP+FP}$ 分别表示召回率和精确率。具体而言，$TP, FP$ 和 $FN$ 分别表示真正、假正和假负 2-单纯形结构的数量。

结论
近年来，在复杂网络理论下，从动力学数据重构复杂系统的高阶相互作用受到了广泛关注并展示了 promising 的结果。然而，大多数现有研究依赖于完整动力学数据的假设——这一条件在现实应用中很少满足，因为观测往往由于各种因素而不完整。这为从...中准确重构个体间的相互作用带来了巨大挑战。

CRediT 作者贡献声明
Xinyi Yu：初稿撰写、软件、方法论、形式分析。Lilan Tu：审稿与编辑、监督、概念化。Fujuan Gao：验证、资源、数据整理。Zhigang Wang：验证、监督、软件。

利益声明
作者声明他们没有已知的竞争财务利益或个人关系可能会影响本文所报告的工作。

致谢
作者感谢匿名审稿人提出的有趣意见。本工作得到中国国家自然科学基金（批准号 72031009）的支持。

Xinyi Yu|Lilan Tu|Fujuan Gao|Zhigang Wang