论文标题
在超图中查找两分组件
Finding Bipartite Components in Hypergraphs
论文作者
论文摘要
超图是对象的三元或高阶关系的重要对象，并且在分析实践中发生的许多复杂数据集时具有许多应用程序。在这项工作中，我们研究了超图中的新热扩散过程，并采用此过程来设计多项式时间算法，该算法大约在超图中找到了两部分成分。从理论上讲，我们证明了我们提出的算法的性能，并通过对合成和现实世界数据集进行广泛的实验分析将其与先前的最新算法进行了比较。我们发现，我们的新算法始终如一，并且在广泛的超图中均超过了先前最新的算法。
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.
