rpicompsci

Research Blog for Department of Computer Science @ Rensselaer Polytechnic Institute

Using social networks to understand how people move

Tommy Nguyen, PhD Student at RPI/CS

My name is Tommy Nguyen and I am a Ph.D. student in the Computer Science department at Rensselaer Polytechnic Institute. My research interests focus on large scale distributed systems for information networks and data analysis in social networks. I want to design socially intelligent systems by using large and socially connected data on the web. My current dissertation advisor is Dr. Boleslaw Szymanski, and I work closely with the researchers from the SCNARC group and external collaborators from the past. I also maintain a blog about latest technologies in Computer Science.

Understanding how people move, i.e. mobility, is crucial in designing systems that can work well even in the presence of big changes to their configuration due to the changes in the locations of the main components. For example, if a person’s mobile phone is working as part of an ad-hoc network (like mobile ad-hoc networks, or MANETs for short), then their movements can easily change the availability of the whole network. To better design such systems, we need to first understand how people move. I have recently been interested in using social networking data to validate existing mobility models for MANETs and delay tolerant networks (DTNs) i.e. networks where nodes do not have to transmit information immediately like people talking to each other when they come in contact. The Random Waypoint (RWP) and Erdos-Renyi (ER) models have been a popular choice among researchers for generating mobility traces of nodes and relationships between them. These models assume movements and relationships within nodes are completely random and independent. However, we observe that neither the relationships among people nor their movements are random. Instead, human movements frequently contain repeated patterns and friendship is bounded by distance. For example, we go from our home to work repeatedly from Monday to Friday, and the people who are within our proximity are more likely to be our friends than people from a different continent. As online social networking provides an opportunity to validate these thesis, I use social networking data to study models of human mobility and relationships for analysis and evaluations of applications in opportunistic networks, such as sensor networks and transportation models in civil engineering. In doing so, my advisor Prof. Szymanski and I hope to provide more human-like movements and social relationship models for studying problems in complex networks.

The first figure displays mobility traces of RWP and our proposed friendship-based mobility model. The gray lines represent the trajectories of the RWP. The green lines represent the trajectories of our model using real data from a location-based social network. These mobile traces represent trajectories of a particular node moving from one point to the next, which are being represented by the lines. The two models are different in a fundamental way. First, the stationary distribution of the positions from the trajectories in the RWP is centralized at the middle. That is, if we randomly pick two points on a coordinate system, the line that connects the two points is more likely to cross the center. The stationary distribution of movements from our friendship-based mobility model reflects the fact the humans have a tendency to be around certain locations (e.g., home, school, work, etc.) and travel to places with less probability that are outside of our proximity (e.g., vacation, conferences, travel, etc).

In the second figure, there are 701 blue points that represent two randomly selected users who are friends and 620 red points that represent two randomly selected users who are not friends. The shaded region is drawn by using the k-nearest neighbor algorithm for classifying whether two users are friends given their average distance apart and checkin similarity, which means how often do two users occur at the same time and place. From the graph, we argue that distance impacts friendship in a fundamental way. First, we notice from the y-axis as distance increases, it becomes less likely to see friendship from two randomly selected users. Interestingly, being nearby distance does not influence friendship, which is represented by the x-axis. To conclude, long distances prevents people from being friends, but being close together doesn’t not by itself create friendship.

About these ads

One comment on “Using social networks to understand how people move

  1. Pingback: Distance impacts friendship. « Nguyen's Blog/Page

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Information

This entry was posted on May 21, 2012 by in Mobility, Social Networking.
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: