Naukowcy z University of Texas pokazali, że jest możliwe dokonanie deanonimizacji „anonimowej” sieci społecznej.

Anonimizacja sieci społecznej polega na zamianie znaczących atrybutów wierzchołków (jak np. nazw użytkownika, adresów e-mail, itp.) na losowo wygenerowane identyfikatory. Ma to służyć uniemożliwieniu identyfikacji użytkowników na podstawie tak przygotowanego grafu. Bywa on udostępniany badaczom lub nawet publikowany w Internecie, jak w przypadku zbioru rekomendacji filmowych użytkowników serwisu Netflix.

Arvind Narayanan i Vitaly Shmatikov z University of Texas pokazali, że jest możliwe dokonanie deanonimizacji (czyli powtórnego zidentyfikowania wierzchołków). Wystarczy jeśli napastnik posiada dostęp do innego, niezanonimizowanego grafu, z którym graf atakowany ma wspólnych użytkowników. Narayanan i Shmatikov w ramach eksperymentu odtworzyli nazwy użytkowników Twittera na podstawie grafu Flickra, z błędami rzędu 12%.

Duże serwisy społecznościowe (jak Facebook albo Nasza Klasa w Polsce) robią bardzo niewiele aby chronić sieci społeczne swoich użytkowników. Stwarzają w ten sposób zagrożenie dla ich prywatności w innych sieciach społecznościowych.