K-Isomorphismus

In den letzten Jahren wurden ernsthafte Bedenken hinsichtlich des Datenschutzes in sozialen Netzwerken geäußert; jedoch ist die Forschung auf diesem Gebiet noch in der Anfangsphase. Das Problem ist herausfordernd aufgrund der Vielfalt und Komplexität von Graphdaten, über die ein Angreifer viele Arten von Hintergrundwissen nutzen kann, um einen Angriff durchzuführen. Eine beliebte Art von Angriffen, die durch Pionierarbeit 2 untersucht wurde, ist die Verwendung von eingebetteten Teilgraphen. Wir folgen diesem Ansatz und identifizieren zwei realistische Ziele von Angriffen, nämlich NodeInfo und LinkInfo. Unsere Untersuchungen zeigen, dass k-Isomorphismus, oder Anonymisierung durch die Bildung von k paarweise isomorphen Teilgraphen, sowohl ausreichend als auch notwendig für den Schutz ist. Das Problem ist nachweislich NP-schwer. Wir entwickeln eine Reihe von Techniken, um die Anonymisierungseffizienz zu steigern und gleichzeitig die Datenverwendbarkeit zu erhalten. Ein kombinierter Vertex-ID-Mechanismus wird ebenfalls eingeführt, um die Privatsphäre über mehrere Datenveröffentlichungen hinweg zu wahren. Die zufriedenstellende Leistung bei einer Reihe von realen Datensätzen, einschließlich HEP-Th, EUemail und LiveJournal, zeigt, dass die hohe Symmetrie sozialer Netzwerke sehr hilfreich ist, um die Schwierigkeit des Problems zu mindern.