Advanced

Robustness of large-scale stochastic matrices to localized perturbations

Como, Giacomo LU and Fagnani, Fabio (2015) 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 In 2014 IEEE 53rd 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
in
2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014)
volume
2015-February
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
c079b93d-d1b1-49f0-a4ff-419d279daaba
date added to LUP
2016-08-25 19:06:48
date last changed
2016-10-07 15:55:22
@misc{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},
  isbn         = {9781467360890},
  keyword      = {consensus,large-scale networks,network centrality,resilience,Robustness,stationary probability distributions,stochastic matrices},
  language     = {eng},
  month        = {02},
  pages        = {3648--3653},
  publisher    = {ARRAY(0xb576ab0)},
  series       = {2014 IEEE 53rd Annual Conference on Decision and Control (CDC 2014) },
  title        = {Robustness of large-scale stochastic matrices to localized perturbations},
  url          = {http://dx.doi.org/10.1109/CDC.2014.7039957},
  volume       = {2015-February},
  year         = {2015},
}