Modularity for hypergraph clustering: Methodologies and applications
将模块度定义扩展到超图，提出混合整数线性规划模型来最大化超图模块度，并与投影方法对比，证明能提高分区质量，最后应用于调查数据分析，揭示隐藏的数据结构。
We consider the problem of detecting communities of the vertices of data structures defined as hypergraphs. There are many methods that were devised to find communities on simple graphs, one of the most important being modularity maximization. Therefore we extend the definition of modularity to deal with hypergraphs, too. The new definition considers whether a hyperedge as internal or not to a community, and in the affirmative case, the hyperedge is assigned with a weight defining the level of cohesiveness of their vertices. Next, we formulate a mixed-integer linear programming model to hypergraph modularity maximization, whose optimal solutions consist in the best vertex partitions of the hypergraph. Previous attempts of partitioning hypergraphs did suggest the projection of hyperedges onto simple graphs, replacing every hyperedge with a complete subgraph. So, we compare our proposal with the previous methodologies, including other hypergraph modularity definitions, and we find that we improve the quality of the partition. Finally, we apply the methodology to the analysis of survey data, and we show how hypergraph modularity clustering highlights some peculiar data structures that otherwise would remain hidden to researchers.