Research Blog for Department of Computer Science @ Rensselaer Polytechnic Institute
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.