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.