Robustness of largescale stochastic matrices to localized perturbations
(2015) 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 In 2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014) 2015February. p.36483653 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 nonreversible or nonirreducible, 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 nonreversible or nonirreducible, 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_{1}distance between π and its perturbed version to vanish in the largescale 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
 20150211
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 consensus, largescale networks, network centrality, resilience, Robustness, stationary probability distributions, stochastic matrices
 in
 2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014)
 volume
 2015February
 pages
 6 pages
 publisher
 Institute of Electrical and Electronics Engineers Inc.
 conference name
 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
 external identifiers

 scopus:84931843550
 ISBN
 9781467360890
 DOI
 10.1109/CDC.2014.7039957
 language
 English
 LU publication?
 yes
 id
 c079b93dd1b149f0a4ff419d279daaba
 date added to LUP
 20160825 19:06:48
 date last changed
 20170418 15:01:34
@inproceedings{c079b93dd1b149f0a4ff419d279daaba, 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 nonreversible or nonirreducible, 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 largescale 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}, keyword = {consensus,largescale networks,network centrality,resilience,Robustness,stationary probability distributions,stochastic matrices}, language = {eng}, month = {02}, pages = {36483653}, publisher = {Institute of Electrical and Electronics Engineers Inc.}, title = {Robustness of largescale stochastic matrices to localized perturbations}, url = {http://dx.doi.org/10.1109/CDC.2014.7039957}, volume = {2015February}, year = {2015}, }