Iterated Models for Social Networks

<p>We define two novel iterative models of social networks. The models are deterministic processes that generate graphs over discrete time-steps, and the properties of these graphs will be explored. The first model generalizes two known models: the Iterated Local Tran- sitivity Model and the Iterated Local Anti-Transitivity Model. The Iterated Local Model includes as input an infinite binary sequence that determines the way the graphs are constructed over time. These models each utilize the underlying graph structure in previous time-steps. Subsequently, we define a model that is independent of the structure of the graph at the previous time-step. The Iterated Global Model creates new adjacencies based on subsets of vertices of a prescribed cardinality. </p><br><p>We prove complex network properties of the Iterated Local Model, such as the small- world property and bad spectral expansion. We also present graph-theoretic properties of the model, such as bounds on the chromatic number, domination number, and Hamiltonicity properties. Analogously, for the Iterated Global Model, we prove both complex network and graph-theoretic properties.</p><div><br></div>