Performance bound analysis of linear consensus algorithm on strongly connected graphs using effective resistance and reversiblization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911406404665344 |
|---|---|
| author | Yonaiyama, Takumi Sato, Kazuhiro |
| author_facet | Yonaiyama, Takumi Sato, Kazuhiro |
| contents | We study the performance of the linear consensus algorithm on strongly connected directed graphs using the linear quadratic (LQ) cost as a performance measure. In particular, we derive bounds on the LQ cost by leveraging effective resistance and reversiblization. Our results extend previous analyses-which were limited to reversible cases-to the nonreversible setting. To facilitate this generalization, we introduce novel concepts, termed the back-and-forth path and the pivot node, which serve as effective alternatives to traditional techniques that require reversibility. Moreover, we apply our approach to Cayley graphs and random geometric graphs to estimate the LQ cost without the reversibility assumption. The proposed approach provides a framework that can be adapted to other contexts where reversibility is typically assumed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_19720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Performance bound analysis of linear consensus algorithm on strongly connected graphs using effective resistance and reversiblization Yonaiyama, Takumi Sato, Kazuhiro Optimization and Control Multiagent Systems We study the performance of the linear consensus algorithm on strongly connected directed graphs using the linear quadratic (LQ) cost as a performance measure. In particular, we derive bounds on the LQ cost by leveraging effective resistance and reversiblization. Our results extend previous analyses-which were limited to reversible cases-to the nonreversible setting. To facilitate this generalization, we introduce novel concepts, termed the back-and-forth path and the pivot node, which serve as effective alternatives to traditional techniques that require reversibility. Moreover, we apply our approach to Cayley graphs and random geometric graphs to estimate the LQ cost without the reversibility assumption. The proposed approach provides a framework that can be adapted to other contexts where reversibility is typically assumed. |
| title | Performance bound analysis of linear consensus algorithm on strongly connected graphs using effective resistance and reversiblization |
| topic | Optimization and Control Multiagent Systems |
| url | https://arxiv.org/abs/2502.19720 |