Pareto–Optimal Design of Markov Chains on Networks Based on Association Schemes
IEEE Access · 2026 · 14 · 72346-72376
DOI: 10.1109/access.2026.3680803 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Access, 2026. Verfasst von Saber Jafarizadeh. Die Arbeit nennt 74 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The design of fast-mixing Markov chains is a fundamental problem with broad relevance to randomized algorithms, distributed computation, and sampling over networks. In this paper, we study the fastest mixing Markov Chain (FMC) problem for networks whose structure is described by association schemes. By exploiting the algebraic symmetries inherent in these schemes, we show that optimal transition probabilities assign identical weights to edges within the same adjacency relation, leading to a substantial reduction in the number of design variables. Building on this structure, we develop two complementary approaches for computing optimal transition weights: a spectral characterization that yields analytical constraints and a linear Programming (LP) formulation that enables efficient numerical optimization. We further analyze clique-lifted association schemes and show that lifting preserves the optimal convergence rate while admitting explicit weight constructions. Numerical examples and experiments illustrate the resulting structural patterns in optimal designs. The proposed framework provides a general and scalable blueprint for optimal random-walk design in applications such as distributed averaging, network sampling, and diffusion processes on large symmetric graphs.
Zitieren
APA
Jafarizadeh, S. (2026). Pareto–Optimal Design of Markov Chains on Networks Based on Association Schemes. IEEE Access, 14, 72346-72376. https://doi.org/10.1109/access.2026.3680803
Vancouver
Jafarizadeh S. Pareto–Optimal Design of Markov Chains on Networks Based on Association Schemes. IEEE Access. 2026;14:72346-72376. doi:10.1109/access.2026.3680803
BibTeX
@article{Jafarizadeh2026,
author = {Jafarizadeh, Saber},
title = {Pareto–Optimal Design of Markov Chains on Networks Based on Association Schemes},
journal = {IEEE Access},
year = {2026},
volume = {14},
pages = {72346--72376},
doi = {10.1109/access.2026.3680803}
}
EUVIMED