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

CT-ER：社交网络随机化中的隐私和频谱分析

• 批准号: 0831204
• 负责人: Xintao Wu
• 金额: $ 18.61万
• 依托单位: University of North Carolina at Charlotte
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-10-01 至 2011-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0831204&HistoricalAwards=false
• 关键词: CT; ER; Privacy; Spectral; Analysis

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.

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