2025/11/15 by Bhaswar B. Bhattacharya, Bhattacharya, Bhaswar B., Sanchayan Bhowal +6
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2511.12326
openalex publication_date 2025/11/15 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28
In a multiplex network a common set of nodes is connected through different types of interactions, each represented as a separate graph (layer) within the network. In this paper, we study the asymptotic properties of submultiplexes, the counterparts of subgraphs (motifs) in single-layer networks, in the correlated Erdős-Rényi multiplex model. This is a random multiplex model with two layers, where the graphs in each layer marginally follow the classical (single-layer) Erdős-Rényi model, while the edges across layers are correlated. We derive the precise threshold condition for the emergence of a fixed submultiplex \boldsymbolH in a random multiplex sampled from the correlated Erdős-Rényi model. Specifically, we show that the satisfiability region, the regime where the random multiplex contains infinitely many copies of \boldsymbolH, forms a polyhedral subset of ℝ3. Furthermore, within this region the count of \boldsymbolH is asymptotically normal, with an explicit convergence rate in the Wasserstein distance. We also establish various Poisson approximation results for the count of \boldsymbolH on the boundary of the threshold, which depends on a notion of balance of submultiplexes. Collectively, these results provide an asymptotic theory for small submultiplexes in the correlated multiplex model, analogous to the classical theory of small subgraphs in random graphs.