| dc.contributor.advisor | Χαλκίδη, Μαρία | |
| dc.contributor.author | Γαγλία, Ιωάννα | |
| dc.date.accessioned | 2022-06-28T08:07:15Z | |
| dc.date.available | 2022-06-28T08:07:15Z | |
| dc.date.issued | 2022-06 | |
| dc.identifier.uri | https://dione.lib.unipi.gr/xmlui/handle/unipi/14419 | |
| dc.identifier.uri | http://dx.doi.org/10.26267/unipi_dione/1842 | |
| dc.description.abstract | Στην επιστήμη των μαθηματικών οι γράφοι είναι ένας τρόπος αναπαράστασης ενός δικτύου, μιας
συλλογής στοιχείων που είναι συνδεδεμένα μεταξύ τους. Οι γράφοι δομούνται από κόμβους οι
οποίοι αντιπροσωπεύουν τα δεδομένα και ακμές οι οποίες χαρακτηρίζουν τις σχέσεις μεταξύ
των κόμβων. Οι γράφοι οργανώνονται σε συστάδες, δηλαδή ομάδες κόμβων με περισσότερα
κοινά χαρακτηριστικά εντός της ίδιας συστάδας και λιγότερο κοινά χαρακτηριστικά μεταξύ
διαφορετικών συστάδων.
Σε αυτή την διπλωματική εργασία στο περιβάλλον της python θα μελετηθούν τα
αποτελέσματα αλγορίθμων σε σύνολα δεδομένων γράφων τα οποία θα αξιολογηθούν από
δείκτες αξιολόγησης οι οποίοι έχουν προταθεί από σχετικές μελέτες. Πιο αναλυτικά θα
χρησιμοποιηθούν τρία σύνολα δεδομένων γράφων και θα τμηματοποιηθούν με την χρήση δύο
διαδεδομένων αλγορίθμων συσταδοποίησης, Spectral και Louvain. Κάθε αλγόριθμος θα δώσει
αποτελέσματα για διαφορετικό αριθμό συστάδων, κάθε αποτέλεσμα θα αξιολογηθεί με την
χρήση δύο γνωστών δεικτών, οι οποίοι είναι ο modularity και ο conductance. Ο δείκτης
modularity αξιολογεί την πυκνότητα των εσωτερικών συνδέσεων της συστάδας σε σχέση με τις
εξωτερικές συνδέσεις με άλλες συστάδες. Ο δείκτης Conductance μιας τομής (conductance of a
cut) συγκρίνει το μέγεθος μιας τομής, δηλαδή τον αριθμό των κομμένων άκρων και το βάρος
(weight) των ακμών σε οποιονδήποτε από τους δύο υπογράφους που δημιουργούνται από την
τομή. Επίσης θα χρησιμοποιηθούν τρείς δείκτες αξιολόγησης οι οποίοι έχουν αναπτυχθεί και
προταθεί σε μελέτες σχετικής μελέτης. Ο δείκτης Q-graph χρησιμοποιεί το degeneracy και το
density τα οποία αφορούν στην πυκνότητα των κόμβων και των ακμών, για να αξιολογήσει την
συνδεσιμότητα μεταξύ των γράφων εντός και εκτός της συστάδας. Ο δείκτης CDS που
χρησιμοποιείται επίσης για αξιολόγηση λαμβάνει υπόψη του την πυκνότητα του γράφου και το
cohesion το οποίο αξιολογεί το πόσο κοντά είναι οι κόμβοι σε ένα δίκτυο και κατά πόσο μπορούν
να διαχωριστούν από άλλους. Ένας ακόμα δείκτης που υπολογίζεται είναι ο GS* ο οποίος
βασίζεται στον silhouette index και αξιολογεί την ποιότητα της συσταδοποίησης με βάση την
απόσταση των κόμβων.
Οπτικοποιώντας τις συσταδοποιήσεις ενός πολύ γνωστού μικρού συνόλου δεδομένων
και θα γίνει προσπάθεια ερμηνείας των αποτελεσμάτων των δεικτών αξιολόγησης και θα
παρατηρηθεί πως η δομή των συστάδων επηρεάζει τα αποτελέσματα του. Οι δείκτες
αξιολόγησης είναι πολύ σημαντική για την επικύρωση των αποτελεσμάτων, παρόλα αυτά δεν
εντοπίζεται ένας ο οποίος μπορεί να είναι αξιόπιστος υπό όλες τις συνθήκες. | el |
| dc.format.extent | 62 | el |
| dc.language.iso | el | el |
| dc.publisher | Πανεπιστήμιο Πειραιώς | el |
| dc.title | Μελέτη και ανάπτυξη προσεγγίσεων αξιολόγησης αποτελεσμάτων clustering σε γράφους | el |
| dc.type | Master Thesis | el |
| dc.contributor.department | Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Ψηφιακών Συστημάτων | el |
| dc.description.abstractEN | Graphs is the way to represent networks in mathematics, networks that their structural elements
are interconnected. Graph are consisted from nodes that represents the data and edges that
represents the relationships between nodes. The structure of a graph gives information about the
nodes, the nodes that belongs to the same cluster have more similar characteristics than with
nodes that belongs to other clusters.
In this thesis will be studied the results of clustering algorithms in graph data sets by
evaluating them with evaluating indices that have proposed in relevant papers. More specifically
three graph data sets will be clustered by using two popular clustering algorithms, Spectral and
Louvain. Each cluster algorithm will give results for several number of clusters, in each result will
be evaluated the quality of clusters with the use of two popular indices, modularity and
conductance. The modularity index compares the intra-linkage of a cluster that need to be denser
from the inter-linkage of the cluster with the neighbor clusters. The index conductance compares
the number of edges cut and their weights that induced from a cut in graph that split the graph
to subgraphs. Also there will be used three evaluation indices that have developed and proposed
from papers with common field of interest. The index Q-graph that is also calculated uses the
degeneracy and graph density that referred to density of nodes and edges, to evaluate the
connectivity of nodes in and between clusters. The index CDS that is also used for evaluation of
clustering results, contains calculation regarding the structural cohesion and the graph density,
cohesion evaluates the distance between the nodes and the possibility of separation. One more
index that is calculated is GS* that is based to silhouette index, this index is evaluating the
similarity of nodes comparing the distance between nodes belonging in the same cluster and their
distance with nodes of neighboring clusters. Python environment includes tools and libraries that
will be useful for the experimental study.
To interpret the results, a small but well-known graph data set will be used to visualize
the clusters and to observe how the cluster structure affects the results of the cluster validation
indices. Cluster validation indices have significant role to ensure the reliability of the results, the
current experiment study comes to the conclusion that there is no the best index but a
combination that need to be used according to graph structure. | el |
| dc.contributor.master | Πληροφοριακά Συστήματα και Υπηρεσίες | el |
| dc.subject.keyword | Graph clustering | el |
| dc.subject.keyword | Ground truth | el |
| dc.subject.keyword | Cluster validity indices | el |
| dc.date.defense | 2022-06-23 | |
