Clustering via Hypergraph Modularity

Abstract

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. Two simple heuristic algorithms are described and applied to a few small 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.

References in corpus (13)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Resolution limit in community detection
• Limits of modularity maximization in community detection
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Community structure and scale-free collections of Erdös-Rényi graphs
• A Scalable Generative Graph Model with Community Structure
• Hypergraph model of social tagging networks
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures

Cited by in corpus (22)

• Networks beyond pairwise interactions: structure and dynamics
• Continuous Influence-based Community Partition for Social Networks
• Mapping flows on hypergraphs
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
• The simpliciality of higher-order networks
• Hypergraph assortativity: a dynamical systems perspective
• An Unsupervised Framework for Comparing Graph Embeddings
• Filtering higher-order datasets
• Opinion disparity in hypergraphs with community structure
• Atomic subgraphs and the statistical mechanics of networks
• On the modularity of 3-regular random graphs and random graphs with given degree sequences
• Community detection in hypergraphs through hyperedge percolation
• Multilayer hypergraph clustering using the aggregate similarity matrix
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• Flow-based Community Detection in Hypergraphs
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• The relevance of higher-order ties
• HIF: The hypergraph interchange format for higher-order networks
• Modularity of Erdős-Rényi random graphs
• Detecting Patterns of Interaction in Temporal Hypergraphs via Edge Clustering
• Quantifying the uneven efficiency benefits of ridesharing market integration
• Preferential attachment hypergraph with vertex deactivation