Robustness of large-scale stochastic matrices to localized perturbations
Författare
Summary, in English
Many linear dynamics over networks can be related by duality to the evolution of a Markov chain with state space coinciding with the node set of the network. Examples include opinion dynamics over social networks as well as distributed averaging algorithms for estimation or control. When the transition probability matrix P associated to the Markov chain is irreducible, a key quantity is its invariant probability distribution π = P′π. In this work, we study how π is affected by, possibly non-reversible or non-irreducible, perturbations of P. In particular, we are interested in perturbations which are localized on a small fraction of nodes but are not necessarily small in any induced norm. While classical perturbation results based on matrix analysis can not be applied in this context, we present various bounds on the effect on π of changes of P obtained using coupling and other probabilistic techniques. Such results allow one to find sufficient conditions for the l1-distance between π and its perturbed version to vanish in the large-scale limit, depending on the mixing time and one additional local property of the original chain P.
Avdelning/ar
Publiceringsår
2015-02-11
Språk
Engelska
Sidor
3648-3653
Publikation/Tidskrift/Serie
2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014)
Volym
2015-February
Dokumenttyp
Konferensbidrag
Förlag
IEEE - Institute of Electrical and Electronics Engineers Inc.
Ämne
- Control Engineering
Nyckelord
- consensus
- large-scale networks
- network centrality
- resilience
- Robustness
- stationary probability distributions
- stochastic matrices
Conference name
2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Conference date
2014-12-15 - 2014-12-17
Conference place
Los Angeles, United States
Status
Published
Forskningsgrupp
- LCCC
ISBN/ISSN/Övrigt
- ISBN: 9781467360890