2022/09/15 by Anirban Chatterjee, Chatterjee, Anirban, Sagnik Nandy +3
Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Mathematics #Opinion Dynamics and Social Influence #Probability (math.PR) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2209.07554
openalex publication_date 2022/09/15 · openalex created_date 2022/09/20 · openalex updated_date 2026/07/28
Multilayer networks are used to represent the interdependence between the relational data of individuals interacting with each other via different types of relationships. To study the information-theoretic phase transitions in detecting the presence of planted partition among the nodes of a multi-layer network with additional nodewise covariate information and diverging average degree, Ma and Nandy (2023) introduced Multi-Layer Contextual Stochastic Block Model. In this paper, we consider the problem of detecting planted partitions in the Multi-Layer Contextual Stochastic Block Model, when the average node degrees for each network is greater than 1. We establish the sharp phase transition threshold for detecting the planted bi-partition. Above the phase-transition threshold testing the presence of a bi-partition is possible, whereas below the threshold no procedure to identify the planted bi-partition can perform better than random guessing. We further establish that the derived detection threshold coincides with the threshold for weak recovery of the partition and provide a quasi-polynomial time algorithm to estimate it.