Ergodic Randomized Algorithms and Dynamics Over Networks

DOI10.1109/TCNS.2014.2367571MaRDI QIDQ5358445zbMATH OpenFDO

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)

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)

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.

Cited in

(19)

• Average resistance of toroidal graphs
• Large deviations analysis for distributed algorithms in an ergodic Markovian environment
• Transitional Behavior of $q$-Composite Random Key Graphs With Applications to Networked Control
• 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
• Mathematical models of self-appraisal in social networks
• Asymptotic behaviours of a class of threshold models for collective action 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
• Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation: a tutorial overview
• Opinion dynamics in social networks with stubborn agents: an issue-based perspective
• Multi-stage discrete time and randomized dynamic average consensus

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)