超图中的高阶模体分析

导语

从社会关系到大脑神经网络，许多现实世界的系统都可以成功地用节点及其连边组成的图来描述。但在许多系统中，比如人类面对面的互动，生态系统中的物种互动，或不同大脑区域之间的神经耦合，单元之间的相互作用并不局限于成对的，而是可以发生在更多节点之间，这时可以用超图来描述。最近发表于 Communications Physics 的一项研究系统地分析了高阶网络中的局部结构，并提出一个有效的算法用高阶模体分析真实网络。

研究领域：高阶模体，高阶网络

高飞 | 作者

邓一雪 | 编辑

论文题目：

Higher-order motif analysis in hypergraphs

论文链接：

https://www.nature.com/articles/s42005-022-00858-7

真实复杂系统中高阶交互的重要性不言而喻，而超图（Hypergraph）作为建模高阶相互作用的数学工具，被广泛应用。不同复杂网络结构的功能性区别，常常表现在其局部偏好连接模式的不同，这可以用网络的模体（Motif）来量化。网络模体分析已经被广泛的应用于各领域的网络结构，包括细菌、大脑和金融。但已有的模体分析技术，都仅限于基于成对交互的网络。为了系统性地分析高阶网络中的局部结构，本文作者开发了一套通用的可扩展的方法来研究高阶模体，并在真实的网络数据分析上显示出其方法的有效性。

1. 方法和数据

高阶模体的分析方法与传统的模体分析相似，也需要三步：

1. 统计每种高阶模体在网络中出现的频次；

2. 将上述结果与零模型（null model）中的统计结果进行比较；

3. 根据比较结果，判断每种高阶模体的出现频次的显著性。

但是传统的模体分析方法没有办法处理高阶交互，为此作者开发可用于高阶模体统计和评估的方法。为了验证方法的有效性，作者收集了四组不同领域的超图数据，包括社会网络、技术网络、生物网络和合作网络。

值得一提的是，高阶模体的数目随着模体阶数指数上升，包含3个节点的高阶模体有6种，而包含4个节点的高阶模体便增加到了171种。

图1. 包含3个节点的所有高阶模体

甚至因为要考虑到图同构的问题，准确计算每阶模体的个数都是困难的。作者给出了模体个数随阶数增长的上下界，表明高阶模体数目确实是指数增长的。因此，作者后续分析时，只考虑了3阶和4阶的高阶模体。

图2. 高阶模体数目随其阶数指数增长

2. 用高阶模体分析真实网络

对于每一个真实网络，作者会为其计算其中的每一个高阶模体相比于随机网络的丰度 Δ（abundance），当该模体的丰度高于随机网络时，称为过度表达（over-expressed），反之为欠表达（under-expressed）。所有高阶模体丰度组成的归一化向量作为该高阶网络的显著性描述 SP （Signiﬁcance proﬁles）。

真实网络中的3阶模体

包含3个节点的高阶模体只有6种，作者分别计算了这6种高阶模体在不同网络中的丰度，并以此作为 SP 来刻画对应的网络。

图3. 6种高阶模体在不同网络中的丰度

作者将相同领域网络的模体丰度平均后发现（图3a），不同领域的局部结构显著的不同：

（1）技术和社会领域过度表达的模体是 VI，表明这些领域中高阶交互团队中的个体也倾向于各自单独交互。并且在这两个还出现了欠表达的反模体（anti-motif）III，表明在群体中的互动不太可能没有两两互动。

（2）在合作和生物领域，过度表达的模体是IV和V，这表明在这些领域中可能存在一种分层结构，阻止所有节点成对地平等互动，例如一个研究领导者与学生和博士后的关系。

通过利用不同网络的 SP 的相关性，作者将来自于不同的领域的网络进行了层次聚类分析（图3b），发现模体的 SP 能够很好的将网络按照所属领域进行区分。

真实网络中的4阶模体

虽然4阶模体的分析会带来运算量的显著增加，但分析4阶的高阶模体比3阶模体提供了关于网络局部结构的更细微的信息。

图4. 4阶模体对网络进行更细致的刻画

图4a中，作者将171个模体按照能最大化不同曲线的视觉差异的方式排布在横轴x上。处于横轴左侧的模体在生物和合作网络中过度表达，而在社会和技术网络中欠表达；处于横轴右侧的模体只在社会和技术网络中过表达。这表明，x轴的两端的模体携带了关于网络之间结构差异的信息。

将不同类别网络中最过度表达的模体可视化后发现（图4c），社会/技术网络偏好嵌入了更多低阶结构的高阶交互，而生物/合作网络更偏好纯粹的高阶交互。这种模式可能是由于这样一个事实，即在群体中进行互动的人也可能以单对进行互动。社会/技术领域中的群体互动似乎是由大量较低层次的互动支撑的。而合作网络中，人们倾向于在大组中写论文，并长期保持同一个研究小组，很少增加或减少合作者，因此，只涉及二元关系的模式会很少。

正如预期的，这种4阶的模体对于网络能够更加细致的刻画。如上图b所示，用4阶模体 SP 计算的网络相关性，能更加清晰的聚类出不同领域的网络，并且有更加细致的层析结构。

3. 结论

本文作者开发了一套分析高阶模体的系统性方法，虽然在一些大网络上还有可扩展性等问题，但是作者的实验分析表明，这一套方法能有效的分析真实高阶网络的的局部结构特征。作者还进一步分析了高阶模体中的嵌套结构和增强效应，感兴趣的读者可以阅读原文。

高阶网络读书会启动

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

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