Efficient Graph Search Algorithms for Public-Private Social Networks (Xin Huang et al.)

Online social networks (Facebook, Twitter, Google+, etc.) have been important platforms for the spread of information, ideas, and influence among a huge number of socially connected users. Driven by applications such as social media marketing and user behavior prediction, social network analysis – the process of investigating social structures using network and graph theories– has become a focal point of research. However, privacy issues present a major concern in the algorithmic analysis of social networks. As reported in a recent study1, 52.6% of 1.4 million New York City Facebook users hid their friends' list. Such privacy protection leads to a novel graph model, called public-private graphs. This new model contains a public graph, in which each node is also associated with a private graph. The public graph is visible to everyone, but each private graph is visible only to the corresponding user.

In this project, we plan to design an index-based computational paradigm to efficiently update an index-based solution on a public graph using the edges in a private graph, with a minimal amount of recomputation on the public graph. This project focuses on investigating three useful and fundamental problems on social networks analysis: community search, geo-social community search, and keyword search. Community search is aimed at finding the densely-connected subgraphs containing given query nodes. Geo-social community search leverages users’ spatial locations to find other users that are both socially connected and physically close. Keyword search finds users in the vicinity of a given user with similar keywords.


For further information on this research topic, please contact Dr. Xin Huang.