Εύρεση κοινοτήτων σε δίκτυα

Abstract

Nowadays, networks are used to represent data in almost any field such as biology, transportation, marketing and social groups. Networks comprise a convenient way to study data and the associated relationships among them, via the field of network analysis. In networks, certain groups of entities with particular importance arise, which form the so- called communities. Communities are of particular importance, since they are related to functional units of the network. Consequently, community detection, constitutes a significant research field. To this end, the present thesis confronts three community detection related problems. More precisely, the first part of the thesis deals with local community detection where the process for identifying groups of entities starts from important entities called hints. This additional information about the importance of some entities can be exploited for detection of better and more relevant communities and it is derived from an expert on the domain, or may arise from the network’s side information. Hence, Hint Enhancement Framework is proposed, which applies a two-step procedure to discover the community of the hints. The last part of the first chapter of the thesis deals with the problem of community detection in dynamic networks. In many cases, looking at the evolution of a particular community or of the community that an important node belongs constitutes an interesting network problem. However, it is difficult to keep track of the evolving communities because of the drifting problem, where a community might shift to a completely different one. To confront this drawback, a framework for detecting the community that contains a set of nodes of particular importance, termed anchors, as well as its evolution over time is suggested. This framework, called Dynamic Community Detection with Anchors (DCDwA), circumvents the identity problem by letting the anchors define partially or completely the core of the corresponding community. The second part of the thesis focuses on discovering causal relations between entities and communities, which adds value to the community detection problem in networks. More specifically, a multi- step framework which identifies the causes of an entity participation in a community is introduced. This framework helps in the identification of important edges in a network, which if removed (or added) change some node’s belongingness to a community. Finally, the last part of the thesis concerns the organization and taxonomy of local community detection related work. More precisely, the last part aims to fill a gap and help researchers get a clear overview of the local community detection problem. To this end, along with the taxonomy of the local community detection approaches proposed in the literature mainly in the last decade (2012-2022), the best documented tools and the most commonly used datasets are also gathered to help researchers identify the tools they can use to prove their methods.

Στις μέρες μας, τα δίκτυα χρησιμοποιούνται για την αναπαράσταση δεδομένων σχεδόν σε κάθε τομέα, όπως η βιολογία, οι μετακινήσεις, η κοινωνιολογία, οι αγοραπωλησίες κ.ά.. Αυτό συμβαίνει διότι τα δίκτυα αποτελούν έναν εύχρηστο τρόπο μελέτης των δεδομένων καθώς και των μεταξύ τους σχέσεων μέσω των μεθόδων που συνιστούν την ανάλυση δικτύων. Πιο συγκεκριμένα, τα δεδομένα αναπαρίστονται από οντότητες που ονομάζονται κόμβοι και τις μεταξύ τους συσχετίσεις που ονομάζονται ακμές.Ειδικότερα, στα δίκτυα συνήθως προκύπτουν ορισμένες ομάδες οντοτήτων (κόμβων) που έχουν ιδιαίτερη σημασία, και σχηματίζουν τις επονομαζόμενες κοινότητες. Οι κοινότητες έχουν ιδιαίτερη σημασία επειδή σχετίζονται με λειτουργικά κομμάτια του δικτύου. Συνεπώς, η εύρεση κοινοτήτων, αποτελεί σημαντικό ερευνητικό πεδίο του ευρύτερου αντικειμένου της ανάλυσης δικτύων. Για το σκοπό αυτό, η παρούσα διατριβή αντιμετωπίζει τρία καίρια προβλήματα που σχετίζονται με την εύρεση κοινοτήτων σε δίκτυα. Το πρώτο μέρος της διατριβής ασχολείται με τον εντοπισμό τοπικών κοινοτήτων όπου η διαδικασία εύρεσης τους ξεκινά από σημαντικές οντότητες με υποδείξεις (hints). Αυτές οι πρόσθετες πληροφορίες σχετικά με τη σημασία ορισμένων οντοτήτων μπορούν να αξιοποιηθούν για τον εντοπισμό καλύτερων και πιο σχετικών κοινοτήτων και μπορεί να δίνονται από έναν ειδικό επί του τομέα ή μπορεί να προκύπτουν από επιπλέον πληροφορίες του δικτύου. Ως εκ τούτου, προτείνεται το πλαίσιο Hint Enhancement Framework (HEF), το οποίο εφαρμόζει μια διαδικασία μερικών βημάτων για να ανακαλύψει την κοινότητα των οντοτήτων με υποδείξεις. Ειδικότερα, το συγκεκριμένο πλαίσιο πραγματοποιεί τροποποίηση υφιστάμενων γραφημάτων, προκειμένου οι κοινότητες που μας ενδιαφέρουν να γίνουν πιο εύκολα αναγνωρίσιμες αλλά και πιο ισχυρές. Πιο συγκεκριμένα, γίνεται είτε αλλαγή των βαρών των ακμών των γράφων, είτε αλλαγή των τιμών των μετρικών που λαμβάνονται υπόψη για την ένταξη ενός κόμβου σε μια κοινότητα ή όχι, έτσι ώστε να ενισχυθούν συγκεκριμένοι κόμβοι ενδιαφέροντος. Η αλλαγή των βαρών γίνεται με κάποια μέθοδο επανυπολογισμού βαρών, για παράδειγμα με βάση τα τρίγωνα στα οποία συμμετέχουν οι προσκείμενες ακμές των κόμβων ενδιαφέροντος. Για την αξιολόγηση του HEF ήταν απαραίτητη και η αναζήτηση κατάλληλων συνόλων δεδομένων προκειμένου να διεξαχθούν πειράματα. Ειδικότερα, χρησιμοποιήθηκαν τόσο συνθετικά όσο και πραγματικά σύνολα δεδομένων για την όσο το δυνατόν αντικειμενικότερη αξιολόγηση. Το τελευταίο κομμάτι του πρώτου μέρους της διπλωματικής εργασίας ασχολείται με το πρόβλημα της εύρεσης κοινοτήτων σε δυναμικά δίκτυα. Ειδικότερα, προτείνεται ένα πλαίσιο εύρεσης της κοινότητας στην οποία ανήκει ένα σύνολο κόμβων ιδιαίτερης σημασίας, που ονομάζονται άγκυρες (anchors), καθώς και η εξέλιξη του με την πάροδο του χρόνου. Ειδικότερα, οι κόμβοι "άγκυρες" αποτελούν επέκταση της ιδέας των “hints” προς εφαρμογή σε χρονικώς μεταβαλλόμενα δίκτυα καθώς θεωρείται πως οι κόμβοι-hints ουσιαστικά ορίζουν την κοινότητα και ως εκ τούτου μπορούν με ένα φυσικό τρόπο να εφαρμοσθούν στην περίπτωση που το δίκτυο αλλάζει. Από την εργασία αυτή προέκυψε ένα πλαίσιο το οποίο μπορεί να εντοπίζει τοπικές κοινότητες συγκεκριμένων κόμβων ενδιαφέροντος σε ροές γραφημάτων.Το δεύτερο μέρος της εργασίας επικεντρώνεται στην ανακάλυψη αιτιότητας μεταξύ οντοτήτων (κόμβων) και κοινοτήτων, γεγονός που προσθέτει αξία στο πρόβλημα εύρεσης κοινοτήτων στα δίκτυα. Πιο συγκεκριμένα, παρουσιάζεται ένα πλαίσιο που προσδιορίζει τις αιτίες της συμμετοχής (ή μη) ενός κόμβου σε μια κοινότητα. Δηλαδή, γιατί ένας κόμβος ανήκει σε μια συγκεκριμένη κοινότητα (ή όχι) και ποιες είναι οι σχέσεις (ακμές) που επηρεάζουν την συμμετοχή (ή μη) αυτού στην κοινότητα; Το συγκεκριμένο ζήτημα είναι η πρώτη φορά που εξετάζεται στο πλαίσιο της εύρεσης κοινοτήτων σε δίκτυα. Από την εργασία αυτή προέκυψε ένα πλαίσιο μερικών βημάτων το οποίο δύναται να εντοπίζει σχέσεις αιτιότητας κόμβου-κοινότητας. Και σε αυτήν την περίπτωση πραγματοποιήθηκε πειραματική αξιολόγηση του προτεινόμενου πλαίσιο με ενθαρρυντικά αποτελέσματα.Το τελευταίο κομμάτι της διατριβής, αποτελεί μια συνολική έρευνα στο κομμάτι της τοπικής εύρεσης κοινοτήτων σε δίκτυα. Πιο συγκεκριμένα, από την ενασχόληση με αλγορίθμους και μεθόδους τοπικής εύρεσης κοινοτήτων τα τελευταία τέσσερα χρόνια, προέκυψε η ανάγκη δημιουργίας μιας εκτενούς εργασίας όπου θα υπάρχουν συγκεντρωμένες οι κυριότερες εργασίες πάνω στο αντικείμενο της τοπικής εύρεσης κοινοτήτων σε δίκτυα, καθώς δεν υπάρχει αντίστοιχη εκτενής εργασία. Ειδικότερα, συγκεντρώθηκαν όλες οι σημαντικές εργασίες πάνω στην τοπική εύρεση κοινοτήτων σε όλων των ειδών τα δίκτυα (στατικά, δυναμικά, ροές γραφημάτων) με έμφαση στην τελευταία δεκαετία (2012-2022), και ταξινομήθηκαν προκειμένου να βοηθήσουν τον εκάστοτε ενδιαφερόμενο ερευνητή να εντοπίζει εύκολα τη μέθοδο που ταιριάζει καλύτερα στα ερευνητικά του ερωτήματα. Παράλληλα, συγκεντρώθηκαν και παρουσιάζονται τα σημαντικότερα εργαλεία που βοηθούν στην συγκεκριμένη κατεύθυνση αλλά και τα πιο συχνά χρησιμοποιούμενα πραγματικά δεδομένα για αξιολόγηση των μεθόδων. Τέλος, παρουσιάζονται για κάθε μέθοδο τα σημαντικότερα χαρακτηριστικά της αλλά και η διαθεσιμότητα του κώδικα υλοποίησης προκειμένου να γίνεται ακόμη πιο εύκολη η επιλογή προσέγγισης των ενδιαφερόμενων ερευνητών.