Random n-SuperHyperGraphs: A Probabilistic Model and Generation Algorithm for Hierarchical Networks

Abstract

Hypergraphs generalize classical graphs by allowing hyperedges to join any nonempty subset of vertices [1]. Superhypergraphs extend this idea by iterating the powerset operation, producing nested layers that capture hierarchical and self-referential relationships among vertex collections [2]. While random graph and hypergraph models form edges independently with probability p, they do not account for higher-order, multi-scale, or nested dependencies often observed in real-world networks. We introduce the random superhypergraph SuHG(n) (V0, p), defined on the n-fold powerset of a base set V0. We give a concise mathematical formulation, derive key properties (including expectation, variance, concentration, and substructure thresholds), and present efficient algorithms for generation. This framework provides a unified, probabilistic model for complex systems with layered, uncertain connectivity.