Files in this item

FilesDescriptionFormat

application/pdf

application/pdfECE499-Sp2015-gao.pdf (823kB)
(no description provided)PDF

Description

Title:The Periodic Behavior of a Threshold Model on Directed Graphs
Author(s):Gao, Zuguang
Contributor(s):Basar, Tamer
Subject(s):social network
periodic solution
automata
Abstract:This thesis investigates a discrete-time deterministic binary threshold model over a directed graph. At each time step, each agent updates the value it holds to the value held by the majority of its incoming neighbors at the last time step. It has been proved in the literature that if the underlying graph is undirected, then for any initial condition, the solution of the threshold model will enter into a periodic solution with the period being no larger than two. Examples can be generated to show that in the cases when the underlying graph is directed, even though the solution will still be periodic, the period of the solution exhibits richer possibilities. This thesis computes the periods of all possible periodic solutions of the model over a certain class of directed graphs, including a single directed cycle and a composition of two directed cycles. It is shown that in the case when the graph is a single directed cycle, all possible periods are divisors of the size of the cycle (i.e., the number of edges). It is also shown that in the case when the graph is a composition of two directed cycles, all possible periods are common divisors of the sizes of the two cycles. The analysis used in this thesis is generalizable to more complex graphs.
Issue Date:2015-05
Genre:Other
Type:Other
Language:English
URI:http://hdl.handle.net/2142/78988
Date Available in IDEALS:2015-08-03


This item appears in the following Collection(s)

Item Statistics