Department of Computer Science, Cornell University, Ithaca, NY 14853.
Institute for Data, Systems, and Society, Massachusetts Institute of Technology, Cambridge, MA 02139.
Proc Natl Acad Sci U S A. 2018 Nov 27;115(48):E11221-E11230. doi: 10.1073/pnas.1800683115. Epub 2018 Nov 9.
Networks provide a powerful formalism for modeling complex systems by using a model of pairwise interactions. But much of the structure within these systems involves interactions that take place among more than two nodes at once-for example, communication within a group rather than person to person, collaboration among a team rather than a pair of coauthors, or biological interaction between a set of molecules rather than just two. Such higher-order interactions are ubiquitous, but their empirical study has received limited attention, and little is known about possible organizational principles of such structures. Here we study the temporal evolution of 19 datasets with explicit accounting for higher-order interactions. We show that there is a rich variety of structure in our datasets but datasets from the same system types have consistent patterns of higher-order structure. Furthermore, we find that tie strength and edge density are competing positive indicators of higher-order organization, and these trends are consistent across interactions involving differing numbers of nodes. To systematically further the study of theories for such higher-order structures, we propose higher-order link prediction as a benchmark problem to assess models and algorithms that predict higher-order structure. We find a fundamental difference from traditional pairwise link prediction, with a greater role for local rather than long-range information in predicting the appearance of new interactions.
网络通过使用一种两两相互作用的模型为复杂系统的建模提供了一种强大的形式化方法。但是，这些系统中的许多结构都涉及到不止两个节点同时发生的相互作用，例如，一个群体内部的交流而不是人与人之间的交流，一个团队内部的协作而不是两个合著者之间的协作，或者一组分子之间的生物相互作用而不是仅仅两个分子之间的相互作用。这种高阶相互作用无处不在，但对其进行实证研究的关注有限，对这些结构可能存在的组织原则也知之甚少。在这里，我们研究了 19 个数据集的时间演变，明确考虑了高阶相互作用。我们表明，我们的数据集具有丰富多样的结构，但来自相同系统类型的数据集具有一致的高阶结构模式。此外，我们发现联系强度和边密度是高阶组织的竞争正指标，这些趋势在涉及不同数量节点的相互作用中是一致的。为了系统地推进对这种高阶结构的理论研究，我们提出了高阶链接预测作为评估模型和算法的基准问题，以预测高阶结构。我们发现，与传统的两两链接预测相比，新交互的出现预测中，局部信息而非远程信息的作用更大。
