单纯复形重构：如何从数据中发现复杂网络潜在高阶关系？

导语

从社交网络中的信息传播、神经元网络的放电行为，到生态系统中多个物种的相互作用，可以发现高阶相互作用是无处不在且重要的。但现有的研究工作均假设高阶结构是已知的。在社会、生物、信息等一些复杂系统中，我们往往仅能观测到状态数据，很难获得结构信息，因此基于观测数据重构网络结构是研究复杂系统的重要途径。然而，之前的重构工作主要集中在具有成对或两体交互关系的网络上。该如何从观测数据中重构出具有高阶关系的网络？这篇文章在重构具有单纯复形结构的网络上做出了初步努力。

为了探索高阶交互结构，聚焦网络科学前沿，集智俱乐部发起了「高阶网络读书会」，研读分享相关研究。读书会自6月28日起，持续10-12周，并特邀Ginestra Bianconi等一线学者做报告。欢迎从事复杂网络研究与应用的朋友加入。详情见文末。

研究领域：高阶网络，网络重构，单纯复形

王欢 | 作者

邓一雪 | 编辑

论文题目：

Full reconstruction of simplicial complexes from binary contagion and Ising data

论文链接：https://www.nature.com/articles/s41467-022-30706-9

1. 研究单纯复形重构的必要性

网络在现实世界中无处不在，但其具体拓扑结构以及控制网络属性和物理可观测性的内在动力系统通常是未知的。目前，一种可行的方法是从观测数据中找到网络拓扑和节点动力学方程，但这一领域之前的工作主要集中于仅有成对交互关系的传统网络上。然而，许多复杂系统不能只用成对的连接来表示。

例如，在社交网络中，多个朋友对某新商品的集体推荐通常比单个朋友的推荐更有说服力，从而使得个人产生更强烈的意愿去购买新产品；在谣言传播过程中，如果一条虚假消息同时被许多人分享或宣传，那么它很可能被个人相信；或者在描述科学家合作关系时，通过成对的连接只能描述哪两个作者有合作，却无法表示当一篇科学论文中出现多名作者时的情况。因此，二元网络无法捕捉到群体的影响，需要借助一种超越成对关系的高阶网络来描述群体动力学影响个体行为的复杂方式。

单纯复形是一种特殊的高阶网络，它是由一系列单纯形组成的集合，并且如果存在一个由m+1个节点组成的m-单纯形，那么这些节点的任意节点子集也构成单纯形。比如在科学家合作网中，如果三个作者组成了一个2-单纯形，表明这三个作者有合作关系，那么任意两个作者也具有合作关系，则两两作者之间也会组成1-单纯形。

可以看到，相比于传统网络，高阶网络可以更充分、更精确地描述真实系统。基于此，如何从观测数据中推断出这种特殊的高阶网络结构-单纯复形，就显现出了尤为重要的意义与价值，这将是一个既具有挑战性又具有重要意义的科学问题。

图1 单纯形示意图

2. 重构单纯复形的总体框架

在安徽大学张海峰团队最新发表于Nature Communications的工作中，为了解决单纯复形的重构问题，作者从一种最简单的单纯复形网络出发（2-单纯复形），借助由社会传染动力学和单纯形Ising动力学两种模型生成的二元时间序列数据，基于统计推断框架设计了一种纯数据驱动的方法用于重构2-单纯复形网络。其中在数据生成过程中，为了体现出多体结构的存在，两种动力学模型的共同点是：在考虑两体间相互作用的同时，关注了三体间的协同强化影响。

接下来，以完全重构成对交互和2-单纯形为目标，即确定出每个节点所属的1-单纯形和2-单纯形。重构过程可分成以下三个步骤：（1）基于观测数据建立似然函数；（2）根据EM（Expectation-Maximization）方法的思想最大化似然函数，获得两体及三体交互的连接概率；（3）执行一种改进的两步走重构策略，以显著提高重构效率。

具体来看重构方法的三个步骤，第一步中通过统计推断的方法将此问题转化为了似然函数最大化问题，即借助条件概率公式，可写出个体 i 的状态翻转是由其余任意单个个体激发的概率以及任意两个个体的协同强化而激发的概率，然后根据每一时间步中翻转次数的期望即可得到个体 i 在所有时间段被感染次数的似然函数。

第二步根据EM方法的思想，进而估计出每个节点与重构节点构成两体的概率及任意两个节点与重构节点构成三体的概率。理论上来讲，通过对概率值截断后即可以得到重构结果。然而，不难发现仅利用前两步进行重构的效率非常低，其复杂度主要来源于对于2-单纯形的预测，因为在预测每个节点所属的2-单纯形时，都需要计算出个概率值。

因此，第三步利用单纯复形自身的性质，提出了一种改进的两步走重构策略，即首先预测出每个节点的“近似”邻居，并提取出预测邻居的时间序列；然后仅基于提取出的时间序列，即可进一步高效预测出每个节点所属的两体及三体交互。

图2 基于社会传染动力学数据重构2-单纯复形的总体框架示意图。(a)-(e) 基于统计推断方法的直接重构过程。(a)(b)(f-i) 根据改进的两步走重构策略的重构过程。

为了验证该重构方法的效果，我们基于社会传染动力学数据和单纯形Ising动力学数据，对3种合成的2-单纯复形 (ERSC, SFSC, SWSC) 和4个由真实数据集所构造的2-单纯复形 (Hypertext2009, Thiers12, InVS15, LyonSchool) 进行重构。同时考虑了两体和三体的密度、网络大小、传播率大小、事件数等各因素对重构结果的影响。

研究结果表明该方法可以高效重构出网络中的两体及三体关系，并验证了该重构方法的鲁棒性。此外，通过与直接重构的一步走方法相比，两步走重构策略在提高重构精度的同时，显著减少了计算时间。

图3 对4个真实2-单纯复形的可视化(a-d)与基于社会传染动力学数据的重构性能(e-h)。

3. 展望高阶网络重构

网络重构问题是网络科学研究中的一个热门问题。对于高阶网络的重构，许多开放性问题仍然存在。

比如，本工作的重构框架是根据来自社会传染动力学和单纯形Ising动力学的二元时间序列数据制定的，如何从更一般的动力学产生的数据中重构高阶网络结构值得研究；该统计推断方法是针对传统网络之外的“最简单”网络结构——2-单纯复形开发的，对于如何重构更一般的高阶网络模型（如3-单纯复形、超图等）是一个值得研究的课题；此外，如何利用更短的时间序列数据来提高重构精度也是一个值得考虑的问题。我们希望，此工作将推动高阶网络重构这一新兴子领域的进一步研究。

参考文献

[1] Battiston, F. et al. Networks beyond pairwise interactions: structure and dynamics. Phys. Rep. 874, 1–92 (2020).

[2] Battiston, F. et al. The physics of higher-order interactions in complex systems. Nat. Phys. 17, 1093–1098 (2021).

[3] Iacopini, I., Petri, G., Barrat, A. & Latora, V. Simplicial models of social contagion. Nat. Commun. 10, 1–9 (2019).

[4] Carletti, T., Battiston, F., Cencetti, G. & Fanelli, D. Random walks on hypergraphs. Phys. Rev. E 101, 022308 (2020).

[5] Young, J.-G., Petri, G. & Peixoto, T. P. Hypergraph reconstruction from network data. Commun. Phys. 4, 135 (2021).

[6] Cipra, B. A. An introduction to the Ising model. Am. Ma. Mon. 94, 937–959 (1987).

[7] Dempster, A. P., Laird, N. M. & Rubin, D. B. Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. Ser. B Method. 39, 1–22 (1977).

[8] Ma, C., Chen, H.-S., Lai, Y.-C. & Zhang, H.-F. Statistical inference approach to structural reconstruction of complex networks from binary time series. Phys. Rev. E 97, 022301 (2018).

[9] Wang, W.-X., Yang, R., Lai, Y.-C., Kovanis, V. & Harrison, M. A. F. Time-series based prediction of complex oscillator networks via compressive sensing. EPL (Europhys. Lett.) 94,

48006 (2011).

[10] Ma, L., Han, X., Shen, Z., Wang, W.-X. & Di, Z. Efficient reconstruction of heterogeneous networks from time series via compressed sensing. PloS One 10, e0142837 (2015).

高阶网络读书会启动

随着对现实世界的探索不断深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元交互关系，也广泛存在多个体同时（或以特定顺序）进行交互，即高阶交互现象。为此，研究人员分别发展出了基于超图、单纯复形、依赖关系等的网络高阶表示模型，为复杂网络分析和研究提供了新的思路。为了促进此领域的交流与合作，我们发起了【高阶网络读书会】。

集智俱乐部读书会是面向广大科研工作者的系列论文研读活动，其目的是共同深入学习探讨某个科学议题，激发科研灵感，促进科研合作。【高阶网络读书会】由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，第一期分享从 6月 28日（周二）20:00 开始，后续每周分享时间为每周四 19:00-21:00 进行，预计持续 10-12 周。这其间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本次读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。

详情请见：

推荐阅读

点击“阅读原文”，报名读书会