Community detection in networks
Creators: name: Μπάλτσου, Γεωργία Π.
Publisher: name: Aristotle University of Thessaloniki
Year: 2022
Subjects: Κοινότητες
Δίκτυα
Αιτιότητα
Αλγόριθμος
Communities
Networks
Causality
Algorithms

description: Τα δίκτυα αποτελούν έναν εύχρηστο τρόπο μελέτης δεδομένων καθώς και των μεταξύ τους σχέσεων μέσω των μεθόδων της ανάλυσης δικτύων. Συγκεκριμένα, τα δεδομένα αναπαρίστονται από οντότητες που ονομάζονται κόμβοι και τις μεταξύ τους συσχετίσεις που ονομάζονται ακμές. Στα δίκτυα συνήθως προκύπτουν ορισμένες ομάδες οντοτήτων που έχουν ιδιαίτερη σημασία, και σχηματίζουν τις επονομαζόμενες κοινότητες. Οι κοινότητες έχουν ιδιαίτερη σημασία καθώς σχετίζονται με λειτουργικά κομμάτια του δικτύου. Συνεπώς, η εύρεση κοινοτήτων, αποτελεί σημαντικό ερευνητικό πεδίο του ευρύτερου αντικειμένου της ανάλυσης δικτύων. Η παρούσα διατριβή αντιμετωπίζει τρία καίρια προβλήματα που σχετίζονται με την εύρεση κοινοτήτων σε δίκτυα. Το πρώτο μέρος της διατριβής ασχολείται με τον εντοπισμό τοπικών κοινοτήτων όπου η διαδικασία εύρεσης τους ξεκινά από σημαντικές οντότητες με υποδείξεις(hints). Αυτές οι πρόσθετες πληροφορίες σχετικά με τη σημασία ορισμένων οντοτήτων μπορούν να αξιοποιηθούν για τον εντοπισμό καλύτερων κοινοτήτων και μπορεί να δίνονται από έναν ειδικό επί του τομέα ή μπορεί να προκύπτουν από επιπλέον πληροφορίες του δικτύου. Έτσι, προτείνεται το πλαίσιο Hint Enhancement Framework(HEF), για να ανακαλύψει την κοινότητα των οντοτήτων με υποδείξεις. Μέσω αλλαγής βαρών των ακμών των γράφων, ή αλλαγής των τιμών των μετρικών που λαμβάνονται υπόψη για την ένταξη ενός κόμβου σε μια κοινότητα ή όχι, ενισχύονται συγκεκριμένοι κόμβοι ενδιαφέροντος. Εν συνεχεία, χρησιμοποιήθηκαν συνθετικά και πραγματικά δεδομένα για την αξιολόγηση του. Επιπροσθέτως, μελετήθηκε το πρόβλημα της εύρεσης κοινοτήτων σε δυναμικά δίκτυα. Ειδικότερα, προτείνεται ένα πλαίσιο εύρεσης της κοινότητας στην οποία ανήκει ένα σύνολο κόμβων ιδιαίτερης σημασίας, που ονομάζονται άγκυρες(anchors), καθώς και η εξέλιξη του με την πάροδο του χρόνου. Οι"άγκυρες" αποτελούν επέκταση της ιδέας των “hints” σε χρονικώς μεταβαλλόμενα δίκτυα καθώς θεωρείται πως οι κόμβοι-hints ουσιαστικά ορίζουν την κοινότητα και ως εκ τούτου μπορούν με ένα φυσικό τρόπο να εφαρμοσθούν στην περίπτωση που το δίκτυο αλλάζει. Από την εργασία αυτή προέκυψε ένα πλαίσιο το οποίο εντοπίζει τοπικές κοινότητες συγκεκριμένων κόμβων ενδιαφέροντος σε ροές γραφημάτων. Το δεύτερο μέρος της διατριβής επικεντρώνεται στην ανακάλυψη αιτιότητας μεταξύ οντοτήτων και κοινοτήτων, γεγονός που προσθέτει αξία στο πρόβλημα εύρεσης κοινοτήτων στα δίκτυα. Συγκεκριμένα, παρουσιάζεται ένα πλαίσιο που προσδιορίζει τις αιτίες της συμμετοχής (ή μη) ενός κόμβου σε μια κοινότητα. Δηλαδή, γιατί ένας κόμβος ανήκει σε μια συγκεκριμένη κοινότητα (ή όχι) και ποιες είναι οι σχέσεις (ακμές) που επηρεάζουν την συμμετοχή (ή μη) αυτού στην κοινότητα; Το συγκεκριμένο ζήτημα είναι η πρώτη φορά που εξετάζεται στο πλαίσιο της εύρεσης κοινοτήτων σε δίκτυα. Τελικώς, προέκυψε ένα πλαίσιο το οποίο εντοπίζει σχέσεις αιτιότητας κόμβου-κοινότητας. Και σε αυτήν την περίπτωση πραγματοποιήθηκε πειραματική αξιολόγηση με ενθαρρυντικά αποτελέσματα. Το τελευταίο κομμάτι της διατριβής, αποτελεί μια συνολική έρευνα στο κομμάτι της τοπικής εύρεσης κοινοτήτων σε δίκτυα καθώς από την ενασχόληση με το ζήτημα τα τελευταία τέσσερα χρόνια, παρατηρήθηκε πως δεν υπάρχει αντίστοιχη. Έτσι, συγκεντρώθηκαν όλες οι σημαντικές εργασίες πάνω στην τοπική εύρεση κοινοτήτων σε όλων των ειδών τα δίκτυα (στατικά, δυναμικά, ροές γραφημάτων) με έμφαση στην τελευταία δεκαετία (2012-2022), και ταξινομήθηκαν προκειμένου να βοηθήσουν τον εκάστοτε ενδιαφερόμενο ερευνητή να εντοπίζει εύκολα τη μέθοδο που ταιριάζει καλύτερα στα ερευνητικά του ερωτήματα. Παράλληλα, συγκεντρώθηκαν και παρουσιάζονται τα σημαντικότερα εργαλεία που βοηθούν στην συγκεκριμένη κατεύθυνση αλλά και τα πιο συχνά χρησιμοποιούμενα δεδομένα για αξιολόγηση των μεθόδων. Τέλος, παρουσιάζονται για κάθε μέθοδο τα σημαντικότερα χαρακτηριστικά της και η διαθεσιμότητα του κώδικα υλοποίησης προκειμένου να γίνεται ακόμη πιο εύκολη η επιλογή προσέγγισης των ενδιαφερόμενων ερευνητών.
description: 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, alobg 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.