Robustness of large-scale stochastic matrices to localized perturbations
(2015) 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 2015-February. p.3648-3653- Abstract
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... (More)
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.
(Less)
- author
- Como, Giacomo LU and Fagnani, Fabio
- organization
- publishing date
- 2015-02-11
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- consensus, large-scale networks, network centrality, resilience, Robustness, stationary probability distributions, stochastic matrices
- host publication
- 2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014)
- volume
- 2015-February
- article number
- 7039957
- edition
- February
- pages
- 6 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
- conference location
- Los Angeles, United States
- conference dates
- 2014-12-15 - 2014-12-17
- external identifiers
-
- scopus:84988293936
- ISBN
- 9781467360890
- DOI
- 10.1109/CDC.2014.7039957
- language
- English
- LU publication?
- yes
- id
- c079b93d-d1b1-49f0-a4ff-419d279daaba
- date added to LUP
- 2016-08-25 19:06:48
- date last changed
- 2022-01-30 05:41:30
@inproceedings{c079b93d-d1b1-49f0-a4ff-419d279daaba,
abstract = {{<p>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 l<sub>1</sub>-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.</p>}},
author = {{Como, Giacomo and Fagnani, Fabio}},
booktitle = {{2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014)}},
isbn = {{9781467360890}},
keywords = {{consensus; large-scale networks; network centrality; resilience; Robustness; stationary probability distributions; stochastic matrices}},
language = {{eng}},
month = {{02}},
pages = {{3648--3653}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
title = {{Robustness of large-scale stochastic matrices to localized perturbations}},
url = {{http://dx.doi.org/10.1109/CDC.2014.7039957}},
doi = {{10.1109/CDC.2014.7039957}},
volume = {{2015-February}},
year = {{2015}},
}