Efficient Graph Search Algorithms for Public-Private Social Networks

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. From each user’s viewpoint, the social network is exactly the union of the public graph and the user’s own private graph. Despite the long existence of such networks, the public-private graph model has started garnering attention from the research community just in the past two years. Owing to the scale of the network and its associated idiosyncrasies, many graph analysis queries cannot be efficiently answered using traditional tools and techniques. To overcome these barriers, in this project, we plan to comprehensively investigate public-private social network analysis in terms of problem modeling, theory analysis, algorithm design and prototype development.

To illustrate the scenario, consider a social recommendation request for all users. For each recommendation, the social network provider can only use the data that the corresponding user can access; otherwise, it could violate privacy laws. Therefore, one approach is to run the algorithms once for each user on a different massive graph, which incurs a prohibitively high computation cost. Another more straightforward approach is to ignore all users’ private data, which leads to ineffective results. To tackle these challenges, 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. Our research agenda for this project is planned as follows: 1) modeling of public-private social networks; 2) design of efficient query processing algorithms for community search and keyword search problems; 3) performance evaluation of the proposed algorithms using real-life data; 4) development of a prototype system to verify the feasibility of our solutions.

With our extensive research experience in graph processing and privacy-aware computing, we hope the outcome of this project will lead to an increase in the adoption of the public-private graph model in social network analysis systems, further provide better analytics and recommendation services, and as a result benefit both individuals and society as a whole