Εκτίμηση Παραμέτρων Γραφημάτων από Θορυβώδη Δείγματα και Ερωτήματα

Abstract

Η μέτρηση του πλήθους εμφανίσεων μικρών υπογραφημάτων σε μεγαλύτερα γραφήματα είναι μια κρίσιμη εργασία για πολλές εφαρμογές. Πιο συγκεκριμένα, τα τρίγωνα εμπλέκονται στον ορισμό μετρικών όπως ο συντελεστής ομαδοποίησης (clustering coefficient) και ο λόγος μεταβατικότητας (transitivity ratio), που είναι θεμελιώδεις στη μελέτη σύνθετων δικτύων. Μια δυσκολία στον υπολογισμό αυτών των παραμέτρων είναι ότι συχνά τα γραφήματα προς μελέτη δεν είναι πλήρως διαθέσιμα για διάφορους λόγους. Σε αυτή την διπλωματική εργασία, ορίζουμε ένα μοντέλο θορύβου παρακινούμενοι από την ιδιωτικότητα στα κοινωνικά δίκτυα, δηλαδή το γεγονός ότι οι χρήστες μπορούν να θέτουν τους φίλους τους ως κρυφούς. Ειδικότερα, έχουμε ένα αυθεντικό γράφημα όπου κάθε κορυφή εκτελεί ένα πείραμα Bernoulli με κάποια γνωστή πιθανότητα επιτυχίας και το θορυβώδες δείγμα ορίζεται αφαιρώντας τις ακμές για τις οποίες και τα δύο άκρα σημειώνουν επιτυχία στα πειράματα. Ο στόχος είναι η εκτίμηση του πλήθους ακμών και τριγώνων του αυθεντικού γραφήματος εντός μικρού πολλαπλασιαστικού σφάλματος, με μεγάλη πιθανότητα. Αρχικά, βρίσκουμε τέτοιες εκτιμήτριες και αποδεικνύουμε αντίστοιχα κάτω φράγματα για το απαιτούμενο πλήθος δειγμάτων, βασισμένα στην θεωρία πληροφορίας. Έπειτα, επιτρέπουμε στους αλγορίθμους μας να έχουν επιπλέον πρόσβαση στο αυθεντικό γράφημα μέσω μαντείου που αποκαλύπτει την πραγματική γειτονιά κορυφών και επεκτείνουμε τις προηγούμενες εκτιμήτριες για αυτή την περίπτωση. Ο αριθμός των δειγμάτων που χρειάζονται γίνεται σταθερός και το πλήθος των ερωτημάτων προς το μαντείο εξαρτάται μόνο από τις παραμέτρους ακρίβειας και όχι από το μέγεθος του γραφήματος.