TY - GEN
T1 - Periodic behavior of a diffusion model over directed graphs
AU - Gao, Zuguang
AU - Chen, Xudong
AU - Liu, Ji
AU - Başar, Tamer
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/12/27
Y1 - 2016/12/27
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85010791689&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85010791689&partnerID=8YFLogxK
U2 - 10.1109/CDC.2016.7798243
DO - 10.1109/CDC.2016.7798243
M3 - Conference contribution
AN - SCOPUS:85010791689
T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
SP - 37
EP - 42
BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th IEEE Conference on Decision and Control, CDC 2016
Y2 - 12 December 2016 through 14 December 2016
ER -