| Project Title: | Dynamic Models for On-line Social Networks |
| Participants: | Dr. Anthony Bonato, Noor Hadi, Dr. Pawel Pralat, Dr. Changping Wang |
| Project Description: | On-line social networks such as Facebook, MySpace, and Flickr have become increasingly popular in
recent years. In such networks, nodes represent people on-line, and edges correspond to a friendship
relation between them. In these complex real-world networks with sometimes millions of nodes and edges,
new nodes and edges dynamically appear over time. Parallel with their popularity among the general
public is an increasing interest in the mathematical and general scientifc community on the properties
on-line social networks, in both gathering data and statistics about the networks, and in finding models
simulating their evolution. Data about social interactions on-line networks is more readily accessible and
measurable than in on-line social networks, which suggests a need for rigorous models capturing their
evolutionary properties. The small world property of social networks, introduced by Watts and Strogatz, is a central notion in the study of complex networks, and has roots in the work of Milgram on short paths of friends connecting strangers. The small world property posits low average distance (or diameter) and high clustering, and has been observed in a wide variety of complex networks. An increasing number of studies have focused on the small world and other complex network prop- erties in on-line social networks. The goal of the project is to provide models for on-line social networks. We study a deterministic model for on-line social networks 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 real-world on-line social and other 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 links. A spectral gap for both the adjacency and normalized Laplacian matrices is proved for graphs arising from the ILT model, thereby simulating such bad expansion properties. The ILT model does not generate graphs with a power law degree distribution. An interesting problem is to design and analyze a stochastic version of the ILT model satisfying the properties displayed in the deterministic ILT model as well as generating power law graphs. Such a stochastic ILT model should with high probability generate power law graphs with topological properties similar to graphs from the deterministic ILT model. |
Modelling and Mining of Networked Information Spaces
