Detecting Planted Partition in Sparse Multi-Layer Networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929355529125888 |
|---|---|
| author | Chatterjee, Anirban Nandy, Sagnik Sadhu, Ritwik |
| author_facet | Chatterjee, Anirban Nandy, Sagnik Sadhu, Ritwik |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_07554 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Detecting Planted Partition in Sparse Multi-Layer Networks Chatterjee, Anirban Nandy, Sagnik Sadhu, Ritwik Statistics Theory Probability 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. |
| title | Detecting Planted Partition in Sparse Multi-Layer Networks |
| topic | Statistics Theory Probability |
| url | https://arxiv.org/abs/2209.07554 |