direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Graph Degree Anonymization: Lower Bounds and Heuristics

Clemens Hoffmann (TU Berlin)

Datensätze sozialer Netzwerke sind als Quelle wissenschaftlicher Forschungen sowie Marktforschungen von großer Bedeutung. Um die Privatheit der Nutzer zu schützen oder Datenschutzrichtlinien zu erfüllen, ist die Anonymisierung solcher Datensätze notwendig und Gegenstand aktueller Forschungen. Die vorliegende Arbeit beschäftigt sich mit der k-Grad-Anonymisierung von Graphen sozialer Netzwerke, die in der Regel potenzverteilt sind. Gegeben ein einfacher Graph G und ein Parameter k, ist nach einem Supergraphen von G gefragt, in dem jeder Knotengrad mindestens k mal auftritt. Die in dieser Arbeit behandelten Algorithmen zur Lösung dieses Problems basieren auf einem dynamischen Zwei-Phasen-Algorithmus von Liu und Terzi. In Phase 1 wird die zum Graph gehörende Gradsequenz k-anonymisiert, so dass jeder Grad mindestens k mal in der anonymisierten Sequenz auftritt. In der zweiten Phase wird die  anonymisierte Sequenz als Supergraph von G realisiert. Da die in Phase 1 mit dem Algorithmus von Liu und Terzi errechneten k-anonymen Gradsequenzen für die Graphen aus dem verwendeten Test-Set nicht realisierbar sind, wird dieser Algorithmus in einem Algorithm Engineering Prozess erweitert, so dass die Wahrscheinlichkeit für die Realisierbarkeit der berechneten Lösungssequenzen in Phase 2 zunimmt. Darüber hinaus werden für Phase 2 verschiedene Heuristiken zur Realisierung der k-anonymen Gradsequenz als Supergraph des Eingabegraphen vorgestellt und anhand von Effektivität und Laufzeit verglichen. Mit Hilfe dieser Algorithmen konnten einige sehr große Instanzen mit > 100.000 Knoten und k = 200 innerhalb von einer Stunde optimal gelöst werden.

Date
Speaker
Location
Language
17.04.2014 16:15
Clemens Hoffmann
TEL 512
deutsch

Back to the research colloquium site.

Zusatzinformationen / Extras