Generative hypergraph models and spectral embedding.
Generative hypergraph models and spectral embedding.
复制标题
DOI：
10.1038/s41598-023-27565-9
复制
发表时间：
2023-01-11
影响因子：
4.6
通讯作者：
中科院分区：
文献类型：
--
作者：
许多复杂的系统涉及两个以上的代理之间的相互作用。超图通过可以链接两个以上节点的超边来捕获这些高阶交互。我们考虑的问题，嵌入超图到低维欧氏空间，使大多数的相互作用是短程的。这种嵌入与许多后续任务相关，例如节点重新排序，集群和可视化。我们专注于两个谱嵌入算法定制超图恢复线性和周期性结构分别。在周期性的情况下，节点位于单位圆上。我们表明，这两个谱超图嵌入算法与一类新的生成超图模型。这些模型根据节点在嵌入空间中的位置生成超边，并鼓励短距离连接。它们允许我们通过最大似然来量化数据中周期性和线性结构的相对存在。它们还提高了节点嵌入的可解释性，并为超边缘预测提供了度量。我们展示了超图嵌入和后续任务，包括量化结构的相对强度，聚类和超边缘预测合成和现实世界的超图。我们发现，超图的方法可以优于聚类算法，只使用二元边缘。我们还比较了高中和小学接触超图上的三元边预测方法，当训练数据量有限时，我们的算法改进了基准方法。
Many complex systems involve interactions between more than two agents. Hypergraphs capture these higher-order interactions through hyperedges that may link more than two nodes. We consider the problem of embedding a hypergraph into low-dimensional Euclidean space so that most interactions are short-range. This embedding is relevant to many follow-on tasks, such as node reordering, clustering, and visualization. We focus on two spectral embedding algorithms customized to hypergraphs which recover linear and periodic structures respectively. In the periodic case, nodes are positioned on the unit circle. We show that the two spectral hypergraph embedding algorithms are associated with a new class of generative hypergraph models. These models generate hyperedges according to node positions in the embedded space and encourage short-range connections. They allow us to quantify the relative presence of periodic and linear structures in the data through maximum likelihood. They also improve the interpretability of node embedding and provide a metric for hyperedge prediction. We demonstrate the hypergraph embedding and follow-on tasks—including quantifying relative strength of structures, clustering and hyperedge prediction—on synthetic and real-world hypergraphs. We find that the hypergraph approach can outperform clustering algorithms that use only dyadic edges. We also compare several triadic edge prediction methods on high school and primary school contact hypergraphs where our algorithm improves upon benchmark methods when the amount of training data is limited.
登录
查看更多内容
DOI：
10.1073/pnas.1800683115
发表时间：
2018-11-27
影响因子：
11.1
作者：
Benson, Austin R.;Abebe, Rediet;Kleinberg, Jon
通讯作者：
Kleinberg, Jon
DOI：
10.1126/science.aad9029
发表时间：
2016-07-08
期刊：
Science (New York, N.Y.)
影响因子：
--
作者：
Benson AR;Gleich DF;Leskovec J
通讯作者：
Leskovec J
DOI：
10.1016/j.cam.2006.04.026
发表时间：
2007-07-01
影响因子：
2.4
作者：
Higham, Desmond J.;Kalna, Gabriela;Kibble, Milla
通讯作者：
Kibble, Milla
影响因子：
1.6
作者：
de Kergorlay, Henry-Louis;Higham, Desmond J.
通讯作者：
Higham, Desmond J.
影响因子：
3.7
作者：
Mastrandrea R;Fournet J;Barrat A
通讯作者：
Barrat A