Periodic behavior of a diffusion model over directed graphs

Zuguang Gao, Xudong Chen, Ji Liu, Tamer Başar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider in this paper a discrete-time deterministic m-ary diffusion model over a strongly connected directed graph. The update rule is easy to state: let the vertices of the graph represent the agents and the edges represent the information flow; at every time step, each vertex updates its value to the maximum value held by its incoming neighbors at the last time step. The resulting system, defined over the graph, is a finite state machine, and hence, enters a periodic motion in finite time from any initial condition. We compute in this paper all possible periods of periodic motions of the system. In particular, by relating the periodic motions to directed cycles in the graph, we show that periods are common divisors of the lengths of the cycles, and vice versa.

Original languageEnglish (US)
Title of host publication2016 IEEE 55th Conference on Decision and Control, CDC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages37-42
Number of pages6
ISBN (Electronic)9781509018376
DOIs
StatePublished - Dec 27 2016
Event55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States
Duration: Dec 12 2016Dec 14 2016

Publication series

Name2016 IEEE 55th Conference on Decision and Control, CDC 2016

Other

Other55th IEEE Conference on Decision and Control, CDC 2016
CountryUnited States
CityLas Vegas
Period12/12/1612/14/16

ASJC Scopus subject areas

  • Artificial Intelligence
  • Decision Sciences (miscellaneous)
  • Control and Optimization

Fingerprint Dive into the research topics of 'Periodic behavior of a diffusion model over directed graphs'. Together they form a unique fingerprint.

Cite this