Master of Science (MSc)
Faculty of Science
On-line social networks such as Facebook or Myspace are of increasing interest to computer scientists, mathematicians, and social scientists alike. In such real-world networks, nodes represent people and edges represent friendships between them. Mathematical models have been proposed for a variety of complex real-world networks such as the web graph, but relatively few models exist for on-line social networks.
We present two new models for on-line social networks: a deterministic model we call Iterated Local Transitivity (ILT), and a random ILT model. We study various properties in the deterministic ILT model such as average degree, average distance, and diameter. We show that the domination number and cop number stay the same no matter how many nodes or edges are added over time. We investigate the automorphism groups and eigenvalues of graphs generated by the ILT model. We show that the random ILT model follows a power-law degree distribution and we provide a theorem about the power law exponent of this model. We present simulations for the degree distribution of the random ILT model.
Hadi, Noor, "Models for On-line Social Networks" (2009). Theses and Dissertations (Comprehensive). 912.