Stochastic block hypergraph model
- 23 September 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 110 (3) , 034312
Abstract
The stochastic block model is widely used to generate graphs with a community structure, but no simple alternative currently exists for hypergraphs, in which more than two nodes can be connected together through a hyperedge. We discuss here such a hypergraph generalization, based on the clustering connection probability between nodes of communities and , and that uses an explicit and modulable hyperedge formation process. We focus on the standard case where when ( is the Kronecker symbol). We propose a simple model that satisfies three criteria: it should be as simple as possible, when the model should be equivalent to the standard hypergraph random model, and it should use an explicit and modulable hyperedge formation process so that the model is intuitive and can easily express different real-world formation processes. We first show that for such a model the degree distribution and hyperedge size distribution can be approximated by binomial distributions with effective parameters that depend on the number of communities and . Also, the composition of hyperedges goes for from ‘pure’ hyperedges (comprising nodes belonging to the same community) to ‘mixed’ hyperedges that comprise nodes from different communities for . We test various formation processes and our results suggest that when they depend on the composition of the hyperedge, they tend to favor the dominant community and lead to hyperedges with a smaller diversity. In contrast, for formation processes that are independent from the hyperedge structure, we obtain hyperedges comprising a larger diversity of communities. The advantages of the model proposed here are its simplicity and flexibility that make it a good candidate for testing community-related problems, such as their detection, impact on various dynamics, and visualization.
Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Exact and sampling methods for mining higher-order motifs in large hypergraphsComputing, 2023
- Growing hypergraphs with preferential linkingJournal of the Korean Physical Society, 2023
- Higher-Order Networks2021
- Networks beyond pairwise interactions: Structure and dynamicsPhysics Reports, 2020
- Simplicial models of social contagionNature Communications, 2019
- Higher-order interactions stabilize dynamics in competitive network modelsNature, 2017
- Two’s company, three (or more) is a simplexJournal of Computational Neuroscience, 2016
- Hypergraph Theory2013
- Community detection in graphsPhysics Reports, 2010
- The Size of the Giant Component of a Random Graph with a Given Degree SequenceCombinatorics, Probability and Computing, 1998