Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Robustness of Large-Scale Stochastic Matrices to Localized Perturbations

In English

Författare

Summary, in English

Many notions of network centrality can be formulated in terms of invariant probability vectors of suitably defined stochastic matrices encoding the network structure. Analogously, invariant probability vectors of stochastic matrices allow one to characterize the asymptotic behavior of many linear network dynamics, e.g., arising in opinion dynamics in social networks as well as in distributed averaging algorithms for estimation or control. Hence, a central problem in network science and engineering is that of assessing the robustness of such invariant probability vectors to perturbations possibly localized on some relatively small part of the network. In this work, upper bounds are derived on the total variation distance between the invariant probability vectors of two stochastic matrices differing on a subset W of rows. Such bounds depend on three parameters: the mixing time and the entrance time on the set W for the Markov chain associated to one of the matrices; and the exit probability from the set W for the Markov chain associated to the other matrix. These results, obtained through coupling techniques, prove particularly useful in scenarios where W is a small subset of the state space, even if the difference between the two matrices is not small in any norm. Several applications to large-scale network problems are discussed, including robustness of Google's PageRank algorithm, distributed averaging, consensus algorithms, and the voter model.

Publiceringsår

2015-04-01

Språk

Engelska

Sidor

53-64

Publikation/Tidskrift/Serie

IEEE Transactions on Network Science and Engineering

Volym

2

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

IEEE - Institute of Electrical and Electronics Engineers Inc.

Ämne

  • Control Engineering

Nyckelord

  • consensus
  • distributed averaging
  • invariant probability vectors
  • large-scale networks
  • Network centrality
  • PageRank
  • resilience
  • robustness
  • stochastic matrices
  • voter model

Status

Published

Forskningsgrupp

  • LCCC

ISBN/ISSN/Övrigt

  • ISSN: 2327-4697