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

University Of South Florida, Tampa FL

Investigators

Abstract

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.