论文标题
基于Pagerank的HyperGraph聚类
Hypergraph Clustering Based on PageRank
论文作者
论文摘要
超图是一个有用的组合对象，用于模拟实体之间的三元或高阶关系。聚类超图是网络分析中的一项基本任务。在这项研究中，我们基于HyperGraphs的个性化Pagerank开发了两种聚类算法。第一个是本地的，因为它的目标是找到一个紧密连接的顶点集，其中包含指定的顶点（指定的顶点）。第二个是全球的，因为它的目标是找到紧密连接的顶点集。对于这两种算法，我们讨论了有关输出顶点集的电导的理论保证。另外，我们在实验上证明，在解决方案质量和运行时间方面，我们的聚类算法的表现优于现有方法。据我们所知，我们的是第一个实用算法的超图，并具有理论保证的输出集合。
A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this study, we develop two clustering algorithms based on personalized PageRank on hypergraphs. The first one is local in the sense that its goal is to find a tightly connected vertex set with a bounded volume including a specified vertex. The second one is global in the sense that its goal is to find a tightly connected vertex set. For both algorithms, we discuss theoretical guarantees on the conductance of the output vertex set. Also, we experimentally demonstrate that our clustering algorithms outperform existing methods in terms of both the solution quality and running time. To the best of our knowledge, ours are the first practical algorithms for hypergraphs with theoretical guarantees on the conductance of the output set.
