Simplicial closure and higher-order link prediction
Simplicial closure and higher-order link prediction
复制标题
DOI：
10.1073/pnas.1800683115
复制
发表时间：
2018-11-27
影响因子：
11.1
通讯作者：
Kleinberg, Jon
中科院分区：
文献类型：
--
作者：
Benson, Austin R.;Abebe, Rediet;Kleinberg, Jon
网络提供了一个强大的形式主义，通过使用成对的相互作用的模型来建模复杂的系统。但这些系统中的大部分结构都涉及同时发生在两个以上节点之间的相互作用，例如，一个群体内的通信而不是人与人之间的通信，一个团队之间的合作而不是一对共同作者之间的合作，或者一组分子之间的生物相互作用而不是两个分子之间的生物相互作用。这种高阶相互作用是普遍存在的，但他们的实证研究受到了有限的关注，很少有人知道这种结构可能的组织原则。在这里，我们研究了19个数据集的时间演化，明确说明高阶相互作用。我们发现，在我们的数据集中有丰富的各种结构，但来自相同系统类型的数据集具有一致的模式的高阶结构。此外，我们发现，领带强度和边缘密度是竞争的高阶组织的积极指标，这些趋势是一致的相互作用，涉及不同数量的节点。为了系统地进一步研究这种高阶结构的理论，我们提出高阶链接预测作为一个基准问题，以评估预测高阶结构的模型和算法。我们发现了一个根本的区别，从传统的成对链接预测，更大的作用，而不是长期的本地信息在预测新的相互作用的出现。
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.