  We present a deterministic model for on-line social networks (OSNs) based on
transitivity and local knowledge in social interactions. In the Iterated Local
Transitivity (ILT) model, at each time-step and for every existing node $x$, a
new node appears which joins to the closed neighbour set of $x.$ The ILT model
provably satisfies a number of both local and global properties that were
observed in OSNs and other real-world complex networks, such as a densification
power law, decreasing average distance, and higher clustering than in random
graphs with the same average degree. Experimental studies of social networks
demonstrate poor expansion properties as a consequence of the existence of
communities with low number of inter-community edges. Bounds on the spectral
gap for both the adjacency and normalized Laplacian matrices are proved for
graphs arising from the ILT model, indicating such bad expansion properties.
The cop and domination number are shown to remain the same as the graph from
the initial time-step $G_0$, and the automorphism group of $G_0$ is a subgroup
of the automorphism group of graphs generated at all later time-steps. A
randomized version of the ILT model is presented, which exhibits a tuneable
densification power law exponent, and maintains several properties of the
deterministic model.
