Iterated Global Models for Complex Networks

02/20/2020
by   Anthony Bonato, et al.
0

We introduce the Iterated Global model as a deterministic graph process that simulates several properties of complex networks. In this model, for every set S of nodes of a prescribed cardinality, we add a new node that is adjacent to every node in S. We focus on the case where the size of S is approximately half the number of nodes at each time-step, and we refer to this as the half-model. The half-model provably generate graphs that densify over time, have bad spectral expansion, and low diameter. We derive the clique, chromatic, and domination numbers of graphs generated by the model.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset