Analysis and development of structural de-anonymization algorithms

OData support
Dr. Gulyás Gábor György
Department of Automation and Applied Informatics

Nowadays, the users of social networks share more and more information about themselves. This information is accessible by numerous parties; however, the operator of the network can share it for research purposes or sell it to business partners. The identifiers, like names, addresses or e-mail addresses are removed in the process in order to protect the users privacy.

Unfortunately, such naive anonymization techniques can be reversed. There are algorithms which can connect anonymous users with their real identity using a background network, based on the structure obtained from a different public network.

First of all, discuss the most efficient and current algorithms, then I choose the state-of-the-art algorithm in my thesis. Thereafter, I disclose the framework developed for the measurements and the methodology of the measurements.

I propose two new algorithms as improvements of the state-of-the-art algorithm. These are the Grasshopper and the Bumblebee attacks, which I compare to the state-of-the-art algorithm with the help of the disclosed methodology. The benefits and the disadvantages of the algorithms are also presented.

As my measurements show, Grasshopper significantly improves the error rate and is able to operate with less initial information, while also scaling well in runtime. Furthermore, Bumblebee is able to run with only a single given seed, and the trade-off between its error rate and yield can be adjusted in a wide range.


Please sign in to download the files of this thesis.