Ph.D. Theses

Proximity, Interactions, and Communities in Social Networks: Properties and Applications

By Tommy Nguyen
Advisor: Boleslaw Szymanski
September 22, 2014

Social network analysis, in the form of network theory, where nodes are humans and edges are social relationships between humans, have a wide range of applications in information science, political science, social science, economics, etc. The availability of data from location-based online social media such as Gowalla and FourSquare has helped scientists model and analyze human relationships and their interactions. In this thesis, we use such data to analyze multiple dimensions of social relationships in terms of three specific aspects: geographical proximity of nodes, their face-to-face interactions, and the structure of their communities. Then we incorporate these three aspects of social relationships into the following applications.

First, we propose techniques for analyzing human relationships in terms of geographical proximity, face-to-face interactions, and communities. We show how geographical proximity shapes structure of the social network by limiting face-to-face interactions among distant users. We also incorporate geographical locations that users visited into a few community detection algorithms for the purpose of detecting communities where members are on average separated by a few friendship link, are close to each other geographically, and are likely to interact with each other face-to-face. These aspects of social network analysis resulted in the first two applications -- human mobility patterns and the spread of ideas.

Second, we use URLs that people share with their followers on social media to personalize the ranking of information by looking at who follows whom, geographical location of the users, and the structure of their detected communities. This allows us to analyze how social media tunnels the flow of information in the network. More importantly, personalized ranking based on these aspects allow users to see information through the eyes of other users whom they consider important (neighbors, friends, peers, etc.) and provides an opportunity for them to interact with information which was used by the people that they care -- the third application.

Finally, we replicate the small world experiment by emulating the process of searching for targets by routing a folder among their acquaintances. Geographical information and community structure allow us to selectively choose starters and targets based on the knowledge of where users are located and to which community they belong. In addition, we examine various routing strategies based on geographical proximity and community structure that perhaps were likely used by participants in the small-world experiment to reach a target. In doing so, we discover which combinations of routing strategies and selection techniques are likely to make the small-world experiment successful in terms of the small number of hops required to reach the target and the percentage of such successful chains -- the last application.

Return to main PhD Theses page