Robustness of LargeScale Stochastic Matrices to Localized Perturbations
(2015) In IEEE Transactions on Network Science and Engineering 2(2). p.5364 Abstract
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... (More)
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 largescale network problems are discussed, including robustness of Google's PageRank algorithm, distributed averaging, consensus algorithms, and the voter model.
(Less)
 author
 Como, Giacomo ^{LU} and Fagnani, Fabio
 organization
 publishing date
 20150401
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 consensus, distributed averaging, invariant probability vectors, largescale networks, Network centrality, PageRank, resilience, robustness, stochastic matrices, voter model
 in
 IEEE Transactions on Network Science and Engineering
 volume
 2
 issue
 2
 pages
 12 pages
 publisher
 IEEEInstitute of Electrical and Electronics Engineers Inc.
 external identifiers

 Scopus:84934343932
 ISSN
 23274697
 DOI
 10.1109/TNSE.2015.2438818
 language
 English
 LU publication?
 yes
 id
 a611ae8bc7af4fa98c32519292f52422
 date added to LUP
 20160825 19:05:51
 date last changed
 20170101 08:32:37
@article{a611ae8bc7af4fa98c32519292f52422, abstract = {<p>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 largescale network problems are discussed, including robustness of Google's PageRank algorithm, distributed averaging, consensus algorithms, and the voter model.</p>}, articleno = {7115154}, author = {Como, Giacomo and Fagnani, Fabio}, issn = {23274697}, keyword = {consensus,distributed averaging,invariant probability vectors,largescale networks,Network centrality,PageRank,resilience,robustness,stochastic matrices,voter model}, language = {eng}, month = {04}, number = {2}, pages = {5364}, publisher = {IEEEInstitute of Electrical and Electronics Engineers Inc.}, series = {IEEE Transactions on Network Science and Engineering}, title = {Robustness of LargeScale Stochastic Matrices to Localized Perturbations}, url = {http://dx.doi.org/10.1109/TNSE.2015.2438818}, volume = {2}, year = {2015}, }