A0570
Title: Detecting planted partition in sparse multi-layer networks
Authors: Sagnik Nandy - University of Chicago (United States) [presenting]
Anirban Chatterjee - University of Pennsylvania (United States)
Ritwik Sadhu - Cornell University (United States)
Abstract: Multi-layer networks 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 node covariate information and diverging average degree, a recent study introduced a multi-layer contextual stochastic block model. The problem of detecting planted partitions is considered in the multi-layer contextual stochastic block model when the average node degrees for each network are greater than 1. The sharp phase transition threshold is established for detecting such 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. The derived detection threshold is further established to coincide with the threshold for weak recovery of the partition, and a quasi-polynomial time algorithm is provided to estimate it.
