论文标题
局部主题聚类通过（超）图形分区
Local Motif Clustering via (Hyper)Graph Partitioning
论文作者
论文摘要
图表上使用广泛使用的操作是局部聚类，即，在种子节点周围提取良好的社区，而无需处理整个图。最近提出了局部基序聚类：它根据基序的分布寻找局部群集。由于这种本地聚类的观点相对较新，因此提出的大多数方法是先前用于基于边缘的本地聚类的统计和数值方法的扩展，而可用的组合方法仍然很少而且相对简单。在这项工作中，我们构建了一个超图和图形模型，该模型都代表种子节点周围的基序分布。我们使用专为（超级）图分区设计的复杂组合算法解决这些模型。在与三角基序的广泛实验中，我们观察到，与最先进的工具MAPPR计算的社区相比，基序电导值平均计算的社区平均是三分之一，而平均平均速度快6.3倍。
A widely-used operation on graphs is local clustering, i.e., extracting a well-characterized community around a seed node without the need to process the whole graph. Recently local motif clustering has been proposed: it looks for a local cluster based on the distribution of motifs. Since this local clustering perspective is relatively new, most approaches proposed for it are extensions of statistical and numerical methods previously used for edge-based local clustering, while the available combinatorial approaches are still few and relatively simple. In this work, we build a hypergraph and a graph model which both represent the motif-distribution around the seed node. We solve these models using sophisticated combinatorial algorithms designed for (hyper)graph partitioning. In extensive experiments with the triangle motif, we observe that our algorithm computes communities with a motif conductance value being one third on average in comparison against the communities computed by the state-of-the-art tool MAPPR while being 6.3 times faster on average.
