Community detection in signed, directected graphs

Ανδρουλιδάκης, Εμμανουήλ; Androulidakis, Manolis

dc.contributor.advisor	Χαλκίδη, Μαρία
dc.contributor.advisor	Halkidi, Maria
dc.contributor.author	Ανδρουλιδάκης, Εμμανουήλ
dc.contributor.author	Androulidakis, Manolis
dc.date.accessioned	2021-03-24T15:21:31Z
dc.date.available	2021-03-24T15:21:31Z
dc.date.issued	2021-02
dc.identifier.uri	https://dione.lib.unipi.gr/xmlui/handle/unipi/13345
dc.identifier.uri	http://dx.doi.org/10.26267/unipi_dione/768
dc.description.abstract	Η συσταδοποίηση σε γράφους είναι μια θεμελιώδης τεχνική που κατηγοριοποιεί παρόμοιους κόμβους ενός γράφου σε ομάδες (συστάδες). Είναι πολύ σημαντική για δίκτυα μεγάλης κλίμακας και χρησιμοποιείται ευρέως σε επιστημονικά πεδία όπου είναι απαραίτητη η ταυτοποίηση μοτίβων ή δομών, όπως η ανάλυση κοινωνικών δικτύων, η στατιστική Ανάλυση Δεδομένων, η Εξόρυξη Δεδομένων, η Μηχανική Μάθηση, η Βιολογία και άλλα. Στη παρούσα διπλωματική επικεντρωνόμαστε σε κατευθυνόμενους γράφους και εξετάζουμε ένα αλγόριθμο ανίχνευσης κοινοτήτων, ο οποίος ομαδοποιεί κόμβους με παρεμφερή χαρακτηριστικά. Ο πιο σημαντικός παράγοντας για αποδοτική συσταδοποίηση είναι ο υπολογισμός του μέτρου ομοιότητας μεταξύ κόμβων. Η πιο σημαντική πρόκληση είναι ο καθορισμός της σχέσης ομοιότητας μεταξύ κόμβων, με βάση τα μοτίβα συνδεσιμότητας που ακολουθούν οι κόμβοι, δηλαδή ο συνδυασμός των εννοιών co-reference και co-citation. Αρχικά, χωρίζουμε τον γράφο στο θετικό και αρνητικό υπο-γράφο του και δουλεύουμε παράλληλα και στους δύο υπο-γράφους. Για κάθε υπο-γράφο αναλύουμε τις αναφορές και τις συνδέσεις μεταξύ των κόμβων προκειμένου να υπολογίσουμε τους πίνακες co-citation και co-reference, αντίστοιχα. Ο πρώτος περιέχει τον αριθμό κόμβων στους οποίους αναφέρονται δύο κόμβοι, και ο δεύτερος δίνει τον αριθμό κόμβων που δείχνουν δύο κόμβοι. Χρησιμοποιούμε κανονικοποιημένα μαθηματικά μοντέλα για να εξομαλύνουμε τα δεδομένα, συν-υπολογίζοντας τον βαθμό κάθε κόμβου. Προκειμένου να απομακρυνθούν τα ακραία στοιχεία, επιχειρήσαμε να λάβουμε υπόψη την ισορροπία θετικών και αρνητικών εισερχόμενων και εξερχόμενων ακμών μεταξύ των κόμβων, ούτως ώστε ο αριθμός κοινών ακμών μεταξύ δύο κόμβων να μετράει λιγότερο όταν αυτοί οι κόμβοι μοιράζονται σημαντικά λιγότερες θετικές από αρνητικές ακμές και αντίστροφα. Συνεχίζοντας, κάνουμε μια πλήρη υλοποίηση του αλγορίθμου σε python προκειμένου να ελέγξουμε πειραματικά την ορθότητα και την ακρίβεια του αλγορίθμου. Τέλος, παρουσιάζουμε τα πειραματικά αποτελέσματα του αλγορίθμου ο οποίος υλοποιείται σε signed, directed γράφους χιλιάδων κόμβων, ανάλογα με την πυκνότητα του γράφου.	el
dc.format.extent	52	el
dc.language.iso	en	el
dc.publisher	Πανεπιστήμιο Πειραιώς	el
dc.rights	Αναφορά Δημιουργού 3.0 Ελλάδα	*
dc.rights	Αναφορά Δημιουργού 3.0 Ελλάδα	*
dc.rights.uri	http://creativecommons.org/licenses/by/3.0/gr/	*
dc.title	Community detection in signed, directected graphs	el
dc.type	Master Thesis	el
dc.contributor.department	Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Ψηφιακών Συστημάτων	el
dc.description.abstractEN	Graph clustering is a fundamental technique that partitions similar nodes into clusters. It is of great importance in large-scale networks and is widely adopted in a variety of scientific areas where it is crucial to identify patterns or structures quickly, such as Social Network Analysis, Statistical Data Analysis, Data Mining, Machine Learning, Biology and others. In this thesis, we focus on signed directed graphs and examine a community detection algorithm that groups together nodes with similar characteristics. The single most significant factor for efficient graph clustering is the computation of the similarity score among nodes. Our main challenge is to establish a similarity relationship among nodes based on the connectivity patterns they follow, i.e., combine the concepts positive and negative co-citation and co-reference. First, we partition the original graph into its positive and negative subgraphs and work in parallel on both subgraphs. For each subgraph, we apply citation analysis and binding theory to calculate the co-citation and co-reference matrices, respectively. The former contains the number of nodes that two nodes both point to, while the latter gives the number of nodes that commonly point to two nodes. We use normalized mathematical models to smoothen data, factoring in the degree of each node. Further, to remove outliers, we tested taking into consideration the balance among positive and negative incoming and outgoing links among nodes. That is, the number of common links between two nodes counts less when these nodes share significantly less positive than negative out-links, and vice versa. In this work, we also provide a complete implementation of the proposed algorithm in Python, as well as the datasets that we used to experimentally evaluate its correctness and accuracy. With this, we prove that the proposed algorithm returns the expected results for randomly generated signed directed graphs and scales up to thousands of nodes, depending on the density of the original graph.	el
dc.contributor.master	Ψηφιακά Συστήματα και Υπηρεσίες	el
dc.subject.keyword	Statistical data analysis	el
dc.subject.keyword	Social network analysis	el
dc.subject.keyword	Graph clustering	el
dc.subject.keyword	Similarity score	el
dc.subject.keyword	Co-citation	el
dc.subject.keyword	Co-reference	el
dc.subject.keyword	Balance	el
dc.subject.keyword	NetworkX	el
dc.subject.keyword	Community detection	el
dc.date.defense	2021-02-15

Αρχεία σε αυτό το τεκμήριο

Name:: Androulidakis_1802.pdf
Μέγεθος:: 1.054Mb
Τύπος:: PDF
Description:: Μεταπτυχιακή διατριβή

Προβολή/Άνοιγμα

Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές

Τμήμα Ψηφιακών Συστημάτων
Department of Digital Systems

Εμφάνιση απλής εγγραφής

Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού 3.0 Ελλάδα