Graph mining In complex networks and prediction in the web graph
Authors: Βουδιγάρη Έλλη 
Published: September 2021

Η μελέτη των πραγματικών δικτύων έχει προσελκύσει σημαντική προσοχή κατά τις τελευταίες δεκαετίες από πολλούς τομείς όπως η Βιολογία, η Πληροφορική, τα Οικονομικά, η Μιχανική, τα Μαθηματικά, η Φυσική, η Κοινωνιολογία και η Στατιστική. Η ανάγκη για τη διερεύνησή τους φανέρωσε την υπεροχή του πεδίου της Εξόρυξης γνώσης από γράφους, το οποίο αποτελεί ένα δυναμικό εργαλείο για την αναπαράσταση δεδομένων (ως γράφους). Οι γράφοι έχουν αναδειχθεί ως πολύ σημαντικοί για τη μοντελοποίηση πολύπλοκων δομών και για την ανάλυση των τοπολογικών χαρακτηριστικών μεγάλων και πολύπλοκων δικτύων, και κυρίως κατά τα τελευταία χρόνια, λόγω της τεράστιας ανάπτυξης του Παγκόσμιου Ιστου και της μεγάλης δημοτικότητας των κοινωνικών δικτύων. Σε αυτό το είδος δικτύων, μοιράζονται και μεταφέρονται μεγάλου όγκου πληροφορίες και δεδομένα μεταξύ εκατομμυρίων ή ακόμα και δισεκατομμυρίων χρηστών. Ο απλούστερος τρόπος ανάλυσής τους είναι εφικτός μέσω της μετατροπής τους σε γράφους, όπου οι κόμβοι αναπαριστούν τους χρήστες και οι ακμές μεταξύ των κόμβων περγράφουν τις μεταξύ τους σχέσεις (φιλίες).Στην παρούσα Διατριβή, αρχικά επικεντρωθήκαμε στη διερεύνηση του φαινομένου της ομοφιλίας σε έναν υπογράφο του Facebook, ο οποίος συλλέχθηκε μέσω της μεθόδου BFS (Breadth First Search). Εφαρμόζοντας έναν αλγόριθμο ανίχνευσης κοινοτήτων και βασιζόμενοι μόνο στη γραφική δομή, αποπειραθήκαμε να εξετάσουμε τη συσχέτιση μεταξύ αυτών των κοινοτήτων του κοινωνικού δικτύου και των χαρακτηριστικών των χρηστών τους που αναπαρίστανται από τις προτιμήσεις τους (Likes). Το αποτέλεσμα της μελέτης αυτής οδήγησε στο συμπέρασμα ότι τα Likes των χρηστών αποτελούν κριτήριο διαχωρισμού μεταξύ των κοινοτήτων και επιβεβιώνουν τη διαίσθηση που μας οδήγησε σε αυτή τη διερεύνηση.Στη συνέχεια, συλλέξαμε έναν μεγαλύτερο υπογράφο του Facebook, αποτελούμενο από 10 εκατομμύρια χρήστες και 80 εκατομμύρια σχέσεις μεταξύ των χρηστών. Προκειμένου να ανακαλύψουμε τις σημαντικές τοπολογικές ιδιότητες αυτού του τεράστιου γράφου, καθώς και άλλων πραγματικών δικτύων, κατευθυνθήκαμε στη μελέτη μεθόδων δειγματοληψίας γράφων. Αυτή η απόπειρά μας οδήγησε στην επινόηση της μεθόδου Rank Degree, ενός νέου αλγορίθμου δειγματοληψίας γράφων (δικτύων) που βασίζεται στην επιλογή ακμών. Η πειραματική αξιολόγηαη, κατόπιν εφαρμογής μεγάλου πλήθους αποτελεσματικών αλγορίθμων δειγματοληψίας πάνω σε διαφόρων ειδών πραγματικά δίκτυα απέδειξαν την υπεροχή της Rank Degree έναντι αυτών. Η επέκταση αυτής της μελέτης, στην οποία παρουσιάζονται τα διεξοδικά πειράματα που διενεργήθηκαν σε διαφορετικά και μεγάλου μεγέθους δίκτυα, ανέδειξαν πολλά από τα πλεονεκτήματα της Rank Degree, καθώς και την υπεροχή της συγκριτικά με πολύπλοκους και εξαιρετικά αποτελεσματικούς αλγορίθμους δειγματοληψίας γράφων.Επιπλέον, καταπιαστήκαμε με το πρόβλημα της ανίχνευσης των σημαντικών κόμβων ενός πολύπλοκου δικτύου, κάτω από μια διαφορετική σκοπιά σε σχέση με προηγούμενες μελέτες. Η προσέγγισή μας βασίστηκε στη δειγματοληψία γράφων και συγκεκριμένα, στις σημαντικές ιδιότητες της Rank Degree. Η μελέτη μας ανέδειξε την αποτελεσματικότητα της Rank Degree και στο πρόβλημα αυτό. Η συνέχεια αυτής της μελέτης εξαπλώθηκε σε επιδημιολογικά μοντέλα, όπως τα SIR και SIS, τα οποία έχουν τη σημαντική ιδιότητα της ανακάλυψης όλων των κόμβων ενός γράφου και της ανίχνευσης των πιο σημαντικών. Χρησιμοποιώντας τα ως ground truth πληροφορία, συγκρίναμε τα παραγόμενα αποτελέσματα σημαντικών κόμβων από τα SIR και SIS, με αυτά που παράχθηκαν από τα δείγματα της Rank Degree και άλλων περίπλοκων και αποτελεσματικών μεθόδων. Τα αποτελέσματα απέδειξαν ότι ο αλγόριθμός μας υπερέχει και πάλι έναντι των υπολοίπων μεθόδων, ενώ παράλληλα είναι συγκρίσιμος με τόσο σημαντικά επιδημιολογικά μοντέλα.Στο τελευταίο τμήμα της Διατριβής, το πρόβλημα της ανίχνευσης των σημαντικών κόμβων μεταφέρεται στο γράφο του Παγκόσμιου Ιστού υπό διαφορετική σκοπιά. Συλλέξαμε τα αποτελέσματα (ιστοσελίδες) από διάφορα ερωτήματα (queries) σε δημοφιλείς μηχανές αναζήτησης (Google, Yahoo) και συγκεκριμένα, εκείνες τις ιστοσελίδες που βρίσκονται στις πρώτες θέσεις και τη σειρά κατάταξής τους σε διαδοχικά στιγμιότυπα. Ασφαλώς, οι πιο σημαντικές ιστοσελίδες (κόμβοι) του γράφου του Παγκόσμιου Ιστού βρίσκονται στις πρώτες θέσεις των ερωτημάτων που τέθηκαν. Χρησιμοποιώντας αυτή την τοπική πληροφορία, προτείναμε κάποιες μεθόδους Μηχανικής Μάθησης, προκειμένου να προβλέψουμε αν οι κόμβοι ενός μη στατικού γράφου, όπως ο Παγκόσμιος Ιστός, θα παραμείνουν στις υψηλότερες θέσεις στο κοντινό μέλλον. Η ποιότητα της πρόβλεψης καθορίσθηκε από την ομοιότητα μεταξύ της προβλεπόμενης και της πραγματικής σειράς κατάταξης των ιστοσελίδων. Διενεργήσαμε διεξοδικά πειράματα σε πραγματικά δεδομένα μεγάλου μεγέθους, χρησιμοποιήσαμε μεγάλο πλήθος μέτρων ομοιότητας για τη σύγκριση των σημαντικών κόμβων, ενώ προτείναμε κι ένα νέο και μάλιστα, πιο αυστηρό μέτρο. Οι προβλέψεις μας υπήρξαν ενθαρρυντικές, ενώ τα αποτελέσματα προσφέρουν πολλά ενδιαφέροντα θέματα προς μελλοντική διερεύνηση των μη στατικών γράφων, οι οποίοι εξελίσσονται με το πέρασμα του χρόνου.