De-anonymization of Dynamic Online Social Networks via Persistent Structures

Service providers of Online Social Networks (OSNs) periodically publish anonymized OSN data, which creates an opportunity for adversaries to de-anonymize the data and identify target users. Most commonly, these adversaries use deanonymization mechanisms that focus on static graphs. Some mechanisms separate dynamic OSN data into slices of static graphs, in order to apply a traditional de-anonymization attack. However, these mechanisms do not account for the evolution of OSNs, which limits their attack performance. In this paper, we provide a novel angle, persistent homology, to capture the evolution of OSNs. Persistent homology barcodes show the birth time and death time of holes, i.e., polygons, in OSN graphs. After extracting the evolution of holes, we apply a two-phase de-anonymization attack. First, holes are mapped together according to the similarity of birth/death time. Second, already mapped holes are converted into super nodes and we view them as seed nodes. We then grow the mapping based on these seed nodes. Our de-anonymization mechanism is extremely compatible to the adversaries who suffer latency in relationship collection, which is very similar to real-world cases.