CT-ER: Privacy and Spectral Analysis in Social Network Randomization

University Of North Carolina At Charlotte, Charlotte NC

Investigators

Abstract

Many applications of social networks require relationship anonymity due to the sensitive or confidential nature of relationship. Anonymizing graphs by replacing the identifying information of the nodes with random ids does not guarantee privacy since the identification of the nodes can be seriously jeopardized by applying subgraph attacks. This project is exploring new approaches with novel applications of matrix perturbation and spectrum analysis in privacy preserving social network analysis, and is developing new effective techniques and tools for edge-based social network randomization. Specifically, the project is investigating how well edge-based randomization protects link privacy and how much it affects the graph's utility. Utility loss is quantified by focusing on the change of the spectrum and eigenvectors of networks since both the spectrum and eigenvectors have close relation with many real space graph characteristics. Further, the project is developing spectrum/utility preserving randomization methods which can better preserve graph characteristics without sacrificing much privacy protection. The research is advancing the theoretical understanding of fundamental issues related to both privacy and spectral analysis of social networks and the design and implementation of practical edge-based randomization techniques for publishing social network data. The research also involves, through courses and thesis projects, graduate and undergraduate students to enhance their knowledge and skills in privacy preserving social network analysis.