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

Randomized algorithms (68W20) Models of societies, social and urban evolution (91D10) 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

(22)

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

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)