Connectivity of random hypergraphs with a given hyperedge size distribution
A hypergraph \(h=(V_{h},E_{h})\) is a set \(V_{h}=\{1,2,\ldots, n\}\) and a collection \(E_{h}\) of non-empty subsets of \(V_{h}\) called hyperedges. (When all hyperedges have order 2 this is a (simple) graph.) A hypergraph is connected if for every partition of \(V_{h}\) into \(V_{1}\) and \(V_{2}\) there is a hyperedge \(e\) with \(e\cap V_{1}\neq \emptyset\) and \(e\cap V_{2} \neq \emptyset\). This paper is about random hypergraphs, where a random (in a sense to be made precise) set of the hyperedges is present, and the question of when it is connected. While much previous work has focused instead on the case of when a giant component emerges when all hyperedges are of the same order, the present paper, motivated by applications in community detection, deals with the full connectivity threshold and is more interested in the case where there are a range of hyperedge sizes.\N\NThe model in detail is as follows. The empirical hyperedge size distribution of a hypergraph is the probability mass function on \(\{1,2,\ldots, n\}\) \(f(x)=\vert E_{h}\vert^{-1}\sum_{e\in E_{h}}\delta_{e}(x)\) where \(\delta_{e}(x)=1\) if \(x=e\) and is otherwise 0. We now let \(\mathcal{H}_{nmf}\) denote the set of all hypergraphs with vertex set \(\{1,2,\ldots, n\}\), \(m=m_{n}\) edges and empirical hyperedge size distribution \(f=f_{n}\). This set is non-empty precisely when for every \(1\leq i\leq n\) we have \(mf(i)\) is an integer and \(\leq \binom{n}{i}\). In this case, say that \(H_{nmf}\) is a hypergraph sampled uniformly at random from \(\mathcal{H}_{nmf}\).\N\NThe first main result (Theorem 2.1) is a threshold condition for \(H_{nmf}\) to be connected. The criterion depends on the moments \((f)_{r}=\sum_{r=2}^{n}x^{r}f(x)\) (noting that hyperedges of size 1 do not affect connectivity). Specifically, if \(\sum_{i=1}^{n}\binom{n}{i}^{-1}f(i)^{2} \ll m^{-2}\) and \((f)_{0}\lesssim (f)_{2}\) then if \(\log(n)-(m/n)(f)_{1}\rightarrow \infty\) as \(n\rightarrow\infty\) we have \(\mathbb{P}(H_{nmf}\text{ is connected})\rightarrow 0\): however if instead \(\log(n)-(m/n)(f)_{1}\rightarrow -\infty\) as \(n\rightarrow\infty\) we instead get \(\mathbb{P}(H_{nmf}\text{ is connected})\rightarrow 1\). This can be thought of as saying that subject to fairly mild regularity conditions the average hyperedge size suffices to characterise connectivity, with other characteristics such as heavy tails or higher moments not being relevant. Not dissimilar results have been found in studies of the giant component in random graphs.\N\NTheorem 2.1. already implies a result for the case where all hyperedges are of a fixed size \(d\) -- call the random hypergraph \(H_{nmd}\) here -- provided that size is bounded and \(m\ll \binom{n}{d}^{1/2}\), however the authors also prove a result (Theorem 2.2) for the case where \(2\leq d\leq n\) is allowed to be unbounded. That result is that \(\mathbb{P}(H_{nmd}\text{ is connected})\rightarrow 0\) if \(\log(n)+m \log(1-d/n)\rightarrow \infty\) but \(\mathbb{P}(H_{nmd}\text{ is connected})\rightarrow 1\) if \(\log(n)+m \log(1-d/n)\rightarrow -\infty\).\N\NOther (related) results in the paper include on the connectivity of so-called passive intersection graphs (and here an example (3.3) is given to show that some mild regularity condition is needed). The results depend on results on so-called shotgun random hypergraphs. Much of the work in the proofs focuses on controlling the number of isolated vertices, an obvious obstruction to connectivity.
- On the strength of connectedness of a random hypergraph
- The asymptotic number of connected \(d\)-uniform hypergraphs
- Component structure in the evolution of random hypergraphs
- Evolution of high-order connected components in random hypergraphs
- The size of the giant high-order component in random hypergraphs
- Approximating sparse graphs: The random overlapping communities model
- Assortativity and bidegree distributions on Bernoulli random graph superpositions
- Clique and cycle frequencies in a sparse random graph model with overlapping communities
- Clustering and percolation on superpositions of Bernoulli random graphs
- Community Recovery in Hypergraphs
- Component structure in the evolution of random hypergraphs
- Configuration models of random hypergraphs
- Counting connected graphs and hypergraphs via the probabilistic method
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- Normal and stable approximation to subgraph counts in superpositions of Bernoulli random graphs
- On the Minimax Misclassification Ratio of Hypergraph Community Detection
- On the strength of connectedness of a random hypergraph
- Parameter Estimators of Sparse Random Intersection Graphs with Thinned Communities
- Probability and Computing
- The asymptotic number of connected \(d\)-uniform hypergraphs
- The order of the giant component of random hypergraphs
- The phase transition in a random hypergraph
- The probability that a random multigraph is simple
- The tail does not determine the size of the giant
- Two Models of Random Intersection Graphs and their Applications
This page was built for publication: Connectivity of random hypergraphs with a given hyperedge size distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6611000)
