The Periodic Behavior of a Threshold Model on Directed Graphs

Gao, Zuguang

Permalink

https://hdl.handle.net/2142/78988 Copy

Description

Title

The Periodic Behavior of a Threshold Model on Directed Graphs

Author(s)

Gao, Zuguang

Contributor(s)

Basar, Tamer

Issue Date

2015-05

Keyword(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.

Type of Resource

other

Language

en

Permalink

http://hdl.handle.net/2142/78988

Owning Collections