III: Small: Discovering and Characterizing Implicit Links in Graph Data

Arizona State University, Scottsdale AZ

Investigators

Abstract

Graph data represent a variety of phenomena, ranging from traffic data, biological networks to social networks. Social networks enable people to participate in a variety of online activities. A typical social networking site allows users to explicitly specify "positive" links to other users with "labels" such as family, friendships, Twitter follower, etc. Little attention is paid to "implicit links" which are unspecified links among social users that may indicate competition, distrust, dislike, or antagonism. This project studies fundamental data analytics issues of understanding and identifying implicit links in graph data. The project explores new computational techniques to discover actionable and insightful patterns in large-scale graph data (e.g., social networks) and enables a large-scale study of social media user behaviors in computational social science. The research insights gained through this project are expected to lead to better design of supervised and unsupervised learning algorithms on networks with both positive and implicit links. The study of implicit social network links will be applicable to the design of new recommender systems, leading to improved services and user experience. The proposed research will involve graduate and undergraduate students in pursuing their theses or projects. Research topics and findings will be integrated in undergraduate and graduate education. The proposed research addresses issues of link analysis in large-scale, incomplete, and noisy networks, such as underlying social media. As implicit links between users are typically invisible on social networking sites, discovering them entails novel challenges. The research team proposes to evaluate the value of implicit links for relationship discovery and better social network understanding. The project includes development of algorithms for graph data analytics, machine learning for positive and unlabeled link discovery in heterogeneous cross-media data, and computationally efficient implicit link predictions. The team proposes to apply the research insights to improving recommendation systems design, classification of implicit user relationships, and social user clustering. The research team plans to share results of this project, including benchmark data with the research community to promote the research on implicit link discovery in social networks via the project site (http://www.public.asu.edu/~huanliu/projects/ImplicitLinks/).