Finding Bipartite Components in Hypergraphs
Finding Bipartite Components in Hypergraphs
复制标题
DOI：
10.48550/arxiv.2205.02771
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Peter Macgregor
中科院分区：
文献类型：
--
作者：
Peter Macgregor
超图是建模对象三元或高阶关系的重要对象，在分析实际中出现的许多复杂数据集方面有着广泛的应用。在这项工作中，我们研究了超图中一个新的热扩散过程，并利用这个过程设计了一个在超图中近似寻找二部分支的多项式时间算法。我们从理论上证明了所提算法的性能，并通过在合成数据集和真实数据集上的大量实验分析，将其与以前的最新算法进行了比较。我们发现，我们的新算法在大范围的超图上一致且显著地优于以前的最先进的算法。
Hypergraphs are important objects to model ternary or higher-order relations of objects, and have a number of applications in analysing many complex datasets occurring in practice. In this work we study a new heat diffusion process in hypergraphs, and employ this process to design a polynomial-time algorithm that approximately finds bipartite components in a hypergraph. We theoretically prove the performance of our proposed algorithm, and compare it against the previous state-of-the-art through extensive experimental analysis on both synthetic and real-world datasets. We find that our new algorithm consistently and significantly outperforms the previous state-of-the-art across a wide range of hypergraphs.