A First-Order Gradient Approach for the Connectivity Optimization of Markov Chains
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909761442676736 |
|---|---|
| author | Franssen, Christian P. C. Zocca, Alessandro Heidergott, Bernd F. |
| author_facet | Franssen, Christian P. C. Zocca, Alessandro Heidergott, Bernd F. |
| contents | Graphs are commonly used to model various complex systems, including social networks, power grids, transportation networks, and biological systems. In many applications, the connectivity of these networks can be expressed through the Mean First Passage Times (MFPTs) of a Markov chain modeling a random walker on the graph. In this paper, we generalize the network metrics based on Markov chains' MFPTs and extend them to networks affected by uncertainty, in which edges may fail and hence not be present according to a pre-determined stochastic model. To find optimally connected Markov chains, we present a parameterization-free method for optimizing the MFPTs of the Markov chain. More specifically, we present an efficient Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm in the context of Markov chain optimization. The proposed algorithm is suitable for both fixed and random networks. Using various numerical experiments, we demonstrate scalability compared to established benchmarks. Importantly, our algorithm finds an optimal solution without requiring prior knowledge of edge failure probabilities, allowing for an online optimization approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A First-Order Gradient Approach for the Connectivity Optimization of Markov Chains Franssen, Christian P. C. Zocca, Alessandro Heidergott, Bernd F. Optimization and Control Systems and Control Graphs are commonly used to model various complex systems, including social networks, power grids, transportation networks, and biological systems. In many applications, the connectivity of these networks can be expressed through the Mean First Passage Times (MFPTs) of a Markov chain modeling a random walker on the graph. In this paper, we generalize the network metrics based on Markov chains' MFPTs and extend them to networks affected by uncertainty, in which edges may fail and hence not be present according to a pre-determined stochastic model. To find optimally connected Markov chains, we present a parameterization-free method for optimizing the MFPTs of the Markov chain. More specifically, we present an efficient Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm in the context of Markov chain optimization. The proposed algorithm is suitable for both fixed and random networks. Using various numerical experiments, we demonstrate scalability compared to established benchmarks. Importantly, our algorithm finds an optimal solution without requiring prior knowledge of edge failure probabilities, allowing for an online optimization approach. |
| title | A First-Order Gradient Approach for the Connectivity Optimization of Markov Chains |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2403.11744 |