BIGDATA: IA: F: Structural Anonymization Techniques for Large, Labeled, and Dynamic Social Graphs

这项工作的目标是为大数据所有者提供工具，以安全地与研究界分享他们的社交网络数据。大数据的具体类型是大型在线社交图，由于两种不同的动态过程而随着时间的推移而演变：一种是图的自然演变，包括边缘和节点的移除和插入；另一种是改变网络顶点状态的动态过程。真实的、纵向的社会图形数据集是理解各种现象的基础，如流行病、行为的采用、人群管理和政治起义。然而，发布真实数据受到严重隐私风险的严重阻碍：即使人类身份被删除，研究也一再证明，去匿名化是可行的，成功率很高。该项目旨在研究和比较结构匿名化技术，这些技术依赖于生成具有原始真实图的给定特征的图。本研究的结果减轻了与图形共享相关的隐私和安全风险，并通过促进真实图形共享以实现更好、更快、更有影响力的研究，有助于更快地理解真实图形上的自然和社会现象。该项目还有助于理解社交图谱的动态过程；让研究生和本科生参与跨学科研究；在github上共享结果代码；通过针对社会学和计算机科学学生的合作教学来加强课程；并通过演讲、出版物和暑期学校向从中学到研究生的受众传播由此产生的知识。该项目旨在通过两种图形生成技术来实现图形匿名化：dk系列技术，在互联网网络生成的背景下引入，以及基于指数随机图形模型的方法（ERGM），这是社会学中建模社会网络的最新技术。对于每种方法，该项目首先调查了从代表性数据集中抽样的静态社交网络匿名化的有效性（有些是可用的，有些是作为这项工作的一部分收集的）。其次，基于社会关系演变的经验特征，将dK系列和ERGM技术应用于动态社会网络。第三，将经验描述的动态过程添加到前面步骤的静态和动态网络之上。最后，研究的重点是扩展计算技术，使其能够匿名化数以百万计节点的社交（因此，稀疏）图。

The objective of this work is to provide big data owners with tools to safely share their social networks data with the research community. The specific type of big data is large online social graphs that evolve over time due to two different dynamic processes: one is the natural evolution of the graph with edge and node removal and insertion; the other is a dynamic process that changes the state of the vertices of the network. Real, longitudinal social graphs datasets are fundamental to understanding a variety of phenomena, such as epidemics, adoption of behavior, crowd management and political uprisings. However, publishing real data is significantly hampered by serious privacy risks: even when humans' identities are removed, studies have proven repeatedly that de-anonymization is doable with high success rate. This project aims to investigate and compare structural anonymization techniques that rely on generating graphs with given characteristics of the original, real graph. The results of this study alleviate the privacy and security risks related to graph sharing and contribute to a faster understanding of natural and social phenomena on real graphs by facilitating real graph sharing for better, faster, more impactful research. The project also contributes to the understanding of dynamic processes on social graphs; involves graduate and undergraduate students in interdisciplinary research; shares resulting code on github; enhances curriculum via collaborative teaching targeted at Sociology and Computer Science students; and disseminates resulting knowledge to audiences ranging from middleschool to graduate students via presentation, publications, and summer schools.The project aims to approach graph anonymization via two techniques for graph generation: dK-series techniques, introduced in the context of internet network generation, and Exponential Random Graph Model-based approaches (ERGM), which are the state of the art in modeling social networks in Sociology. For each approach, the project first investigates its effectiveness on anonymizing static social networks sampled from representative datasets (some available, others collected as part of this effort). Second, it adapts the dK series and ERGM techniques to dynamic social networks based on empirical characterizations of the evolution of social relations. Third, the empirically-described dynamic processes are added on top of the static and dynamic networks from the previous steps. And finally, the research focuses on scaling up the computational techniques to be able to anonymize social (thus, sparse) graphs in the order of millions of nodes.