Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/10099
Title: Ταυτοποίηση κόμβων σε κοινωνικά δίκτυα
Other Titles: De-anonymizing nodes in social networks
Authors: Τσιτσόκα, Ευανθία
Keywords: Ταυτοποίηση κόμβων
Άρση ανωνυμίας σε δίκτυα
Ανώνυμα κοινωνικά δίκτυα
Αλγόριθμοι σε γραφήματα
Αλγόριθμοι τοπικής αναζήτησης
Keywords (translated): Network de-anonymization
Network re-identification
Network privacy
Anonymized social networks
Graph algorithms
Local search algorithms
Abstract: Στα πλαίσια της παρούσας διπλωματικής εργασίας, μελετάμε το πρόβλημα της ταυτοποίησης των χρηστών ενός ανώνυμου κοινωνικού δικτύου με τη βοήθεια ενός δεύτερου κοινωνικού δικτύου, στο οποίο αναπαρίστανται σωστά οι πραγματικές κοινωνικές σχέσεις μεταξύ των χρηστών και του οποίου οι χρήστες είναι γνωστοί (ground truth). Το πρόβλημα μοντελοποιείται με τη χρήση απλών, μη κατευθυ- νόμενων γραφημάτων, στα οποία οι κόμβοι αναπαριστούν τους χρήστες και οι ακμές τις σχέσεις μεταξύ των χρηστών. Εξετάσαμε πλήθος αλγορίθμων και τελικά προτείνουμε δύο γενικούς αλγορίθμους και τρείς αλγορίθμους τοπικής αναζήτησης. Οι αλγόριθμοι επιχειρούν, χρησιμοποιώντας αποκλειστικά δο- μικές πληροφορίες των δύο δικτύων, να κατασκευάσουν μια αμφιμονοσήμαντη αντιστοίχιση μεταξύ των συνόλων κόμβων των δύο γραφημάτων, ταυτοποιώντας με τον τρόπο αυτό τους χρήστες του ανώνυμου κοινωνικού δικτύου. Οι αλγόριθμοι που προτάθηκαν και υλοποιήθηκαν, αξιολογήθηκαν πειραματικά με τη χρήση τυχαίων γραφημάτων αλλά και στιγμιότυπων πραγματικών κοινωνικών δικτύων.
Abstract (translated): This diploma thesis studies the problem of de-anonymizing users in anonymized social networks, using a ground truth social network where the users are known. The problem is modeled using simple, undirected graphs with nodes representing the users of the network and edges representing the relation- ships between the users. A number of algorithms were studied and as a result, two general algorithms and three local search algorithms are proposed. The algorithms attempt to identify the users of the anonymized social network by producing a bijection from the nodes of the anonymized graph to the nodes of the ground truth graph, using exclusively structural information of the available graphs. The algorithms presented in this work were evaluated through a series of experiments, using random graphs as well as snapshots from real-world social networks.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Ταυτοποίηση κόμβων σε κοινωνικά δίκτυα.pdf332 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.