Privacy-Preserving Data Analysis on Graphs and Social Networks.

Abstract

Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 21.7 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43521.1 Introduction The proliferation of social networks, online communities, peer-to-peer file sharing,and telecommunication systems has created large, complex graphs. These graphs are of significant interest to researchers in various application domains such as marketing, psychology, and epidemiology. Research in these areas has revealed interesting properties of the data and presented efficient ways of maintaining, mining, and querying them. Distributed and ubiquitous computing over these networks, which are essentially graph structures, is also an emerging topic with increasing interest in the data mining community. However, with the exception of some recent work, the privacy concerns associated with data analysis over graphs and networks have been largely ignored. In this chapter, we provide a detailed survey of the very recent work on privacy-preserving data analysis over graphs and networks in an effort to allow the reader to observe common themes and future directions.