Qualitative analysis of differential privacy applied over graph structures

The increase in popularity of online services has generated interest in developing new algorithms to better protect user privacy. Some services defend individual user records by only releasing statistics like the number of users that match certain criteria. If an attacker has access to side information, releasing such summaries can lead to privacy breaches where the records of a certain user are revealed. Differential privacy is a new technique which protects individual user records by altering the released statistics. Many services organize their data as a graph with the edge weights representing statistics. If such services are interested in releasing the information, they must do so in a privacy-preserving manner. We analyze how differential privacy can be used to protect such graph structures. We assess the quality of the released data in relation to the Dijkstra shortest path algorithm. Finally, we propose research directions to improve the performance of the released data.