Faculty       Staff       Contact       Institute Directory
Research Groups      
Undergraduate       Graduate       Institute Admissions: Undergraduate | Graduate      
Events       Institute Events      
Lab Manual       Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Modeling Dynamics of Communication and Social Networks

By Konstantin Mertsalov
Advisor: Mark Goldberg
December 4, 2009

We present a novel approach to modeling the dynamics of large social and communication networks. Our model is based on the locality principle; it postulates that every node of the network is associated with a small local area, comprised of the nodes "close" to the center-node. The nodes of the locality are those that are most likely to receive communications from the center-node. Different implementations of the locality idea were considered and tested on the real-life network of blogs managed by the blog-provider LiveJournal. It turned out that the locality areas generated by short random walks with probabilistic restarts produce the best approximation of the LiveJournal network.

Our method for measuring the network dynamics and validation of the model includes a set of parameters traditionally used for this purpose, such as average diameter of the graph and the clustering coefficient, and the vertex in-degree and out-degree distribution. While out-degree distribution, used as the input, represents the individual properties of the network nodes, the vertex in-degree distribution represents the global property of the network, and it is used by as for testing and the validation of the model.

We view the communication network, which can be measured, as a sampling of the invisible social relationship network. Traceable communication data was to used for reasoning about a social network and modeling the dynamics. We developed a machinery for collecting the communication data from public section of LiveJournal. The data we collected covers more then two years of activity and contains information related to 1,8 million bloggers, 79 million posts and 223 million comments. Using permutation methods for statistical analysis of observed network, we measure and characterize the network dynamics. It turns out that individuals in the Blogosphere maintain surprisingly stable relationships i.e. if a pair communicated in the past, they are likely to continue communicating as long as both stay active. On the other hand, most bloggers were persistently active for a long time. We also observed that bloggers choose to communicate with individuals who were very close to them (via shortest distance) in the historical communication network. These observations allowed us to fit the model for accurate simulation of LiveJournal dynamics.

* Return to main PhD Theses page



---