SGH Warsaw School of Economics, Warsaw, Poland.
The Tutte Institute for Mathematics and Computing, Ottawa, ON, Canada.
PLoS One. 2019 Nov 6;14(11):e0224307. doi: 10.1371/journal.pone.0224307. eCollection 2019.
Despite the fact that many important problems (including clustering) can be described using hypergraphs, theoretical foundations as well as practical algorithms using hypergraphs are not well developed yet. In this paper, we propose a hypergraph modularity function that generalizes its well established and widely used graph counterpart measure of how clustered a network is. In order to define it properly, we generalize the Chung-Lu model for graphs to hypergraphs. We then provide the theoretical foundations to search for an optimal solution with respect to our hypergraph modularity function. A simple heuristic algorithm is described and applied to a few illustrative examples. We show that using a strict version of our proposed modularity function often leads to a solution where a smaller number of hyperedges get cut as compared to optimizing modularity of 2-section graph of a hypergraph.
尽管许多重要的问题（包括聚类）都可以用超图来描述，但超图的理论基础以及使用超图的实际算法还没有得到很好的发展。在本文中，我们提出了一个超图模块性函数，它推广了已有的、广泛使用的图模块性度量，用于衡量网络的聚类程度。为了正确地定义它，我们将图的 Chung-Lu 模型推广到超图中。然后，我们提供了关于我们的超图模块性函数的最优解的理论基础。描述了一种简单的启发式算法，并将其应用于几个说明性的例子。我们表明，使用我们提出的模块性函数的严格版本通常会导致一个解决方案，其中与优化超图的 2 节图的模块性相比，较少的超边被切断。
