Graph mining In complex networks and prediction in the web graph

Abstract

The study of real world networks has attracted considerable attention over the last decades from many disciplines including biology, computer science, economics, engineering, mathematics, physics, sociology and statistics. The need for their investigation gave prominence to the Graph Mining field which constitutes a very powerful tool of data representation (as graphs). Graphs have become very important in modeling complicated structures and analyzing the topological characteristics of large and complex networks and especially in recent years, with the vast growth of the World Wide Web and the popularity of social networks. In the latter type of networks, large amounts of information and data are shared and transferred among millions or even billions of users. The simplest way to analyze them is through their conversion to graphs, where the nodes represent the users and the edges between pairs of nodes describe the relations (friendships).In the first part of this thesis, we focus on the investigation of homophily in a subgraph of Facebook collected via the Breadth First Search. By applying a community detection algorithm and based just on the graph structure, we intend to examine the correlation between the social network communities and the users’ characteristics represented by Likes. More specifically, we take into account the users’ top preferences (Likes) in each community and the categories corresponding to the Likes. Next, we assign a score on the distinct Likes and categories, based on their popularity within the community. The experimental results show that in the case of users’ Likes, the correlation ranges from small to medium between communities and the whole population (Facebook crawled subgraph), while it is even smaller between communities. However, there is a high correlation in terms of Like categoriesbetween the different communities and between communities and the overall population. This fact proves that Likes constitute a criterion of distinction among the communities and verify the intuition that led us towards this research.In the second part, we crawled a large dataset from the Facebook graph consisting of 10 million users and 80 million users’ relations. In order to discover important topological properties of this huge graph and other large real networks, we were directed towards the study of graph sampling methods. The initial attempt resulted in the development of Rank Degree, a new graph exploration sampling algorithm which is based on edge selection. The experimental evaluation on several real datasets and the comparison with five efficient graph sampling techniques proves that our approach maintains several properties of the initial graph, leading to representative samples and outperforms among the five approaches. Extending this study, we performed a deeper search into all the advantages of Rank Degree. Specifically, we present the results of exhaustive experiments and compare the Rank Degree with more complex and efficient methods in the graph sampling scientific area, such as theMetropolis-Hastings algorithm, in many real-world datasets of different type and size and using a variety of measures.Furthermore, we deal with the problem of identifying the influential spreaders of a complex network under a different scope as it is used in previous works. Our approach is based on graph sampling and specifically, on the superior properties of Rank Degree. Initially, we conduct extensive experiments on five real-world networks and we use four centrality metrics for the influences of nodes. We provide strong evidence that our method is highly effective. The continuity of this study spreads to epidemic models such as SIR and SIS, which possess the significant property of exploring all the nodes of a graph and discover the most important ones. Using them as ground truth identifiers, we compare the resulted important nodes with those produced by the samples of Rank Degree and other intricate and efficient methods. The results prove that our algorithm is superior towards other methods and is even able to be compared with such crucial models, discriminating the influential spreaders of large network graphs.In the last part, the problem of important node discovery is transferred to the Web graph and is examined under a different scope. Applying crawling, we gather the results (webpages) coming out of various queries on popular search engines (Google, Yahoo) and specifically, the top webpages and their ranking in successive timestamps. Obviously, the webpages (nodes) considered to be the most important in the Web graph appear in the first positions of the proposed links for the given queries. Exploiting this local information, we propose different machine learning methodologies in order to predict whether the nodes of a non-static graph, as the Web is, will remain in the top positions in the near future. The prediction quality is quantified as the similarity between the predicted and the actual rankings. We carry out extensive experiments on real-world large scale datasets. In addition, we use a variety of existing similarity measures for comparing the top-k nodes, while we introduce a new one which is stricter. The predictions are encouraging in all experimental setups and similaritymeasures. Moreover, the results offer many interesting tasks for future investigation in graphs which are not static, but evolve through time.

Η μελέτη των πραγματικών δικτύων έχει προσελκύσει σημαντική προσοχή κατά τις τελευταίες δεκαετίες από πολλούς τομείς όπως η Βιολογία, η Πληροφορική, τα Οικονομικά, η Μιχανική, τα Μαθηματικά, η Φυσική, η Κοινωνιολογία και η Στατιστική. Η ανάγκη για τη διερεύνησή τους φανέρωσε την υπεροχή του πεδίου της Εξόρυξης γνώσης από γράφους, το οποίο αποτελεί ένα δυναμικό εργαλείο για την αναπαράσταση δεδομένων (ως γράφους). Οι γράφοι έχουν αναδειχθεί ως πολύ σημαντικοί για τη μοντελοποίηση πολύπλοκων δομών και για την ανάλυση των τοπολογικών χαρακτηριστικών μεγάλων και πολύπλοκων δικτύων, και κυρίως κατά τα τελευταία χρόνια, λόγω της τεράστιας ανάπτυξης του Παγκόσμιου Ιστου και της μεγάλης δημοτικότητας των κοινωνικών δικτύων. Σε αυτό το είδος δικτύων, μοιράζονται και μεταφέρονται μεγάλου όγκου πληροφορίες και δεδομένα μεταξύ εκατομμυρίων ή ακόμα και δισεκατομμυρίων χρηστών. Ο απλούστερος τρόπος ανάλυσής τους είναι εφικτός μέσω της μετατροπής τους σε γράφους, όπου οι κόμβοι αναπαριστούν τους χρήστες και οι ακμές μεταξύ των κόμβων περγράφουν τις μεταξύ τους σχέσεις (φιλίες).Στην παρούσα Διατριβή, αρχικά επικεντρωθήκαμε στη διερεύνηση του φαινομένου της ομοφιλίας σε έναν υπογράφο του 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) και συγκεκριμένα, εκείνες τις ιστοσελίδες που βρίσκονται στις πρώτες θέσεις και τη σειρά κατάταξής τους σε διαδοχικά στιγμιότυπα. Ασφαλώς, οι πιο σημαντικές ιστοσελίδες (κόμβοι) του γράφου του Παγκόσμιου Ιστού βρίσκονται στις πρώτες θέσεις των ερωτημάτων που τέθηκαν. Χρησιμοποιώντας αυτή την τοπική πληροφορία, προτείναμε κάποιες μεθόδους Μηχανικής Μάθησης, προκειμένου να προβλέψουμε αν οι κόμβοι ενός μη στατικού γράφου, όπως ο Παγκόσμιος Ιστός, θα παραμείνουν στις υψηλότερες θέσεις στο κοντινό μέλλον. Η ποιότητα της πρόβλεψης καθορίσθηκε από την ομοιότητα μεταξύ της προβλεπόμενης και της πραγματικής σειράς κατάταξης των ιστοσελίδων. Διενεργήσαμε διεξοδικά πειράματα σε πραγματικά δεδομένα μεγάλου μεγέθους, χρησιμοποιήσαμε μεγάλο πλήθος μέτρων ομοιότητας για τη σύγκριση των σημαντικών κόμβων, ενώ προτείναμε κι ένα νέο και μάλιστα, πιο αυστηρό μέτρο. Οι προβλέψεις μας υπήρξαν ενθαρρυντικές, ενώ τα αποτελέσματα προσφέρουν πολλά ενδιαφέροντα θέματα προς μελλοντική διερεύνηση των μη στατικών γράφων, οι οποίοι εξελίσσονται με το πέρασμα του χρόνου.