Warning Propagation: stability and subcriticality
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910458306363392 |
|---|---|
| author | Cooley, Oliver Lee, Joon Ravelomanana, Jean B. |
| author_facet | Cooley, Oliver Lee, Joon Ravelomanana, Jean B. |
| contents | Warning Propagation is a combinatorial message passing algorithm that unifies and generalises a wide variety of recursive combinatorial procedures. Special cases include the Unit Clause Propagation and Pure Literal algorithms for satisfiability as well as the peeling process for identifying the $k$-core of a random graph. Here we analyse Warning Propagation in full generality on a very general class of multi-type random graphs. We prove that under mild assumptions on the random graph model and the stability of the the message limit, Warning Propagation converges rapidly. In effect, the analysis of the fixed point of the message passing process on a random graph reduces to analysing the process on a multi-type Galton-Watson tree. This result corroborates and generalises a heuristic first put forward by Pittel, Spencer and Wormald in their seminal $k$-core paper (JCTB 1996). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_15577 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Warning Propagation: stability and subcriticality Cooley, Oliver Lee, Joon Ravelomanana, Jean B. Combinatorics 05C80 Warning Propagation is a combinatorial message passing algorithm that unifies and generalises a wide variety of recursive combinatorial procedures. Special cases include the Unit Clause Propagation and Pure Literal algorithms for satisfiability as well as the peeling process for identifying the $k$-core of a random graph. Here we analyse Warning Propagation in full generality on a very general class of multi-type random graphs. We prove that under mild assumptions on the random graph model and the stability of the the message limit, Warning Propagation converges rapidly. In effect, the analysis of the fixed point of the message passing process on a random graph reduces to analysing the process on a multi-type Galton-Watson tree. This result corroborates and generalises a heuristic first put forward by Pittel, Spencer and Wormald in their seminal $k$-core paper (JCTB 1996). |
| title | Warning Propagation: stability and subcriticality |
| topic | Combinatorics 05C80 |
| url | https://arxiv.org/abs/2111.15577 |