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.