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 ‥C the process of investigating social structures using network and graph theories‥C 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.

Related Publications:


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