Ergodic Randomized Algorithms and Dynamics Over Networks

DOI10.1109/TCNS.2014.2367571zbMATH Open1370.93308arXiv1309.1349MaRDI QIDQ5358445FDOQ5358445

Authors: Chiara Ravazzi, Paolo Frasca, Hideaki Ishii, Roberto Tempo 

Publication date: 21 September 2017

Published in: IEEE Transactions on Control of Network Systems (Search for Journal in Brave)

Abstract: Algorithms and dynamics over networks often involve randomization, and randomization may result in oscillating dynamics which fail to converge in a deterministic sense. In this paper, we observe this undesired feature in three applications, in which the dynamics is the randomized asynchronous counterpart of a well-behaved synchronous one. These three applications are network localization, PageRank computation, and opinion dynamics. Motivated by their formal similarity, we show the following general fact, under the assumptions of independence across time and linearities of the updates: if the expected dynamics is stable and converges to the same limit of the original synchronous dynamics, then the oscillations are ergodic and the desired limit can be locally recovered via time-averaging.

Full work available at URL: https://arxiv.org/abs/1309.1349

Mathematics Subject Classification ID

Models of societies, social and urban evolution (91D10) Randomized algorithms (68W20) Stochastic stability in control theory (93E15)

Cited In (19)

• Average resistance of toroidal graphs
• Transitional Behavior of $q$-Composite Random Key Graphs With Applications to Networked Control
• Large deviations analysis for distributed algorithms in an ergodic Markovian environment
• Opinion influence and evolution in social networks: a Markovian agents model
• Structural balance and interpersonal appraisals dynamics: beyond all-to-all and two-faction networks
• Opinion dynamics and social power evolution over reducible influence networks
• Stochastic recursions on directed random graphs
• Bifurcation analysis of Friedkin-Johnsen and Hegselmann-Krause models with a nonlinear interaction potential
• Community structure recovery and interaction probability estimation for gossip opinion dynamics
• Gossip based asynchronous and randomized distributed task assignment with guaranteed performance on heterogeneous networks
• Asymptotic behaviours of a class of threshold models for collective action in social networks
• Mathematical models of self-appraisal in social networks
• On modeling collective risk perception via opinion dynamics
• Opinion dynamics with the increasing peer pressure and prejudice on the signed graph
• Pseudorandomness for network algorithms
• Concentration in gossip opinion dynamics over random graphs
• Opinion dynamics in social networks with stubborn agents: an issue-based perspective
• Multi-stage discrete time and randomized dynamic average consensus
• Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation: a tutorial overview

This page was built for publication: Ergodic Randomized Algorithms and Dynamics Over Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358445)