Generalizations of Threshold Graph Dynamical Systems

Abstract

Dynamics of social processes in populations, such as the spread of emotions, influence, language, mass movements, and warfare (often referred to individually and collectively as contagions), are increasingly studied because of their social, political, and economic impacts. Discrete dynamical systems (discrete in time and discrete in agent states) are often used to quantify contagion propagation in populations that are cast as graphs, where vertices represent agents and edges represent agent interactions. We refer to such formulations as graph dynamical systems. For social applications, threshold models are used extensively for agent state transition rules (i.e., for vertex functions). In its simplest form, each agent can be in one of two states (state 0 (1) means that an agent does not (does) possess a contagion), and an agent contracts a contagion if at least a threshold number of its distance-1 neighbors already possess it. The transition to state 0 is not permitted. In this study, we extend threshold models in three ways. First, we allow transitions to states 0 and 1, and we study the long-term dynamics of these bithreshold systems, wherein there are two distinct thresholds for each vertex; one governing each of the transitions to states 0 and 1. Second, we extend the model from a binary vertex state set to an arbitrary number r of states, and allow transitions between every pair of states. Third, we analyze a recent hierarchical model from the literature where inputs to vertex functions take into account subgraphs induced on the distance-1 neighbors of a vertex. We state, prove, and analyze conditions characterizing long-term dynamics of all of these models.