关键词：复杂网络，超图分析，高阶数据，社团检测



论文标题：Community detection in large hypergraphs
论文来源：Science Advances
斑图链接：https://pattern.swarma.org/paper/56d3dfae-9dfb-11ed-b097-0242ac17000d
原文链接：https://www.science.org/doi/10.1126/sciadv.adg9159

在过去的几十年里，从生物系统到社会系统的大多数关系数据，都被网络成功地表现出来，网络利用节点描述系统的基本单元，用连边表示它基本单元间的相互作用。然而，这种建模方法无法正确编码组交互的存在，无法同时描述三个或更多系统单元之间的关联，而随后发展出的超图可以描述任意数量的单元之间发生交互的网络，使之成为许多现实世界的社会和生物系统进行建模的自然工具。

近期，有人提出了统计推断框架，以原则性的方式捕获超图的中尺度组织，但存在诸多问题，如只能利用在小规模的超图中、计算复杂度高、需要强假设等。

作者基于此缺陷，提出一个新的原则性框架 Hy-MMSBM 来模拟高阶系统的组织。在硬社团分配和混合社团分配的情况下，该方法可以以超过最先进方法的精度检测超图中的社团。

图1 对真实社团分配的恢复（左图为硬社团分配，右图为混合社团分配）。D表示数据的最大超边尺寸，纵坐标表示真实社团分配与计算所得社团分配间的相似度，可见当信息稀缺，即最大超变尺寸较小时，作者的方法可与当前可用的最有效的方法相媲美。而当考虑更大的超边时，该方法在两类社团的分配推断结果上都优于竞争算法。


此外，该算法灵活性可以捕获到之前无法研究的一些结构，例如不协调的社团互动。

图2 协调与不协调社团中相互作用的检测。左图显示对数似然值的正（负）差异，表明协调（不协调）模型获得了更好的拟合，黄色区域由于没有足够结构与信息，检测性受影响。右图表示不协调模型的对数似然，模型可以更好地拟合具有明显不协调结构（深红色）的数据。


最后，该模型克服了以前方法的计算阈值，非常高效，适合研究包含数百万个节点的超图以及替代工具无法访问的数千个系统单元之间的交互。

图3 真实数据建模：超边缘预测和运行时间。左图显示在最大超边尺寸D = 25 时的计算阈值，该方法获得最高分，且能够对整个超图进行建模，最高可达D = 1074。右图显示该方法运行各种真实数据集所需时间。


该工作为超大型超图的建模提供了一种准确、灵活和可扩展的工具，提高了处理和研究现实世界高阶系统组织的能力。


编译｜董佳欣

高阶网络社区



详情请见：

探索复杂系统高阶交互的奥秘 | 高阶网络读书会启动



推荐阅读

‍1. Nat.Commun.速递：超图中超边和重叠社团的推断
2. S. Fortunat & M. Newman：复杂网络社团检测20年
3. 网络社团检测20年，哪些方法正在冉冉升起？
4. 张江：第三代人工智能技术基础——从可微分编程到因果推理 | 集智学园全新课程
5. 《张江·复杂科学前沿27讲》完整上线！
6. 加入集智学园VIP，获得20周年“涌现”学术年会入场券！
7. 加入集智，一起复杂！


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