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

由于关系的敏感性或保密性，社交网络的许多应用都需要关系匿名性。通过用随机ID替换节点的标识信息来匿名图并不能保证私密性，因为应用子图攻击会严重危害节点的标识。该项目正在探索矩阵扰动和谱分析在隐私保护社会网络分析中的新应用，并正在开发基于边缘的社会网络随机化的新的有效技术和工具。具体地说，该项目正在调查基于边的随机化如何很好地保护链接隐私，以及它对图形的效用有多大影响。由于网络的频谱和特征向量都与实际空间图的许多特征密切相关，因此通过关注网络的谱和特征向量的变化来量化效用损失。此外，该项目正在开发保留频谱/效用的随机化方法，该方法可以更好地保留图形特征，而不会牺牲太多隐私保护。这项研究正在推动对社交网络隐私和频谱分析相关基本问题的理论理解，以及用于发布社交网络数据的实用的基于边缘的随机化技术的设计和实现。这项研究还包括，通过课程和论文项目，研究生和本科生提高他们在隐私保护社会网络分析方面的知识和技能。

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.