Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/28760Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Κουφός, Νικόλαος | el |
| dc.date.accessioned | 2017-12-20T09:28:34Z | - |
| dc.date.available | 2017-12-20T09:28:34Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/28760 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.2411 | - |
| dc.rights | Default License | - |
| dc.subject | Graphic methods | en |
| dc.subject | Quality measures | en |
| dc.subject | Datasets & results | en |
| dc.title | Community detection in undirected graphs using a new quality measure | en |
| dc.title | Εντοπισμός κοινοτήτων σε μη κατευθυνόμενα γραφήματα με ένα νέο κριτήριο ποιότητας διαμέρισης | el |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Graphic methods | en |
| heal.dateAvailable | 2017-12-20T09:29:34Z | - |
| heal.language | en | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.publicationDate | 2017 | - |
| heal.bibliographicCitation | Βιβλιογραφία : σ. 54-56 | el |
| heal.abstract | The detection of communities is of great significance in sociology, biology, computer science and other disciplines where complex systems are often represented as graphs or networks. One of the most interesting properties of graphs representing real systems is community structure, i.e. the partitioning of graph nodes into clusters, with many edges joining nodes of the same cluster and comparatively few edges joining nodes of different clusters. This hard but important problem has attracted an increasing scientific interest over the past few years and several techniques have been proposed, especially for the case where the number of communities is not known in advance. The most popular family of community detection methods is based on the optimization of the so called ‘modularity’ criterion using various clustering approaches. The modularity of a community is defined as fraction of the edges that fall within a given group minus the expected fraction if edges were distributed at random. However, it has been shown that modularity has several drawbacks, such as for example the ‘resolution limit’, i.e., it is unable to detect small communities. We introduce a new quality measure to evaluate a partitioning of a graph into communities that is called ‘inclusion’. This quality measure evaluates how well each node is ‘included’ in its community by considering both its existing and its non-existing edges. We have implemented several techniques to optimize the inclusion criterion. A first technique follows the agglomerative principles, as it starts with every node in a separate community and iteratively merges communities so that inclusion is improved. A second technique is similarly initialized, but instead of community merging, it improves the inclusion of the partitioning by moving each time a single node to another community. Another method is based on evaluating the solutions provided by spectral clustering. In the experimental evaluation we conducted, it has been shown that the inclusion measure is very effective in evaluating communities and usually leads to improved community detection results without requiring the a-priori specification of the number of communities. | en |
| heal.abstract | Ο εντοπισμός κοινοτήτων παίζει σημαντικό ρόλο στην κοινωνιολογία, βιολογία, επιστήμη υπολογιστών καθώς και σε όλους τους τομείς όπου πολύπλοκα συστήματα , συχνά αναπαρίστανται ως γραφήματα η δίκτυα. Μία από τις πιο ενδιαφέρουσες ιδιότητες που έχει η αναπαράσταση με γραφήματα, είναι η δομή του σε κοινότητες, δηλαδή, η διαμέριση του γράφου σε συστάδες που απαρτίζονται από κόμβους που συνδέονται με πολλούς κόμβους της ίδιας συστάδας μέσο ακμών, και όσο δυνατόν λιγότερους κόμβους που ανήκουν σε άλλες συστάδες. Αυτό το πρόβλημα, παρά την δυσκολία του, έχει κεντρίσει το ενδιαφέρων διάφορων επιστημών τα τελευταία χρόνια, με αποτέλεσμα να προταθούν αρκετές τεχνικές επίλυσης του προβλήματος, κυρίως για τις περιπτώσεις όπου ο αριθμός των συστάδων δεν είναι γνωστός εκ των προτέρων. Η πιο γνωστή οικογένεια μεθόδων εντοπισμού κοινοτήτων είναι βασισμένη στην βελτιστοποίηση του κριτηρίου ‘modularity’ με διάφορες τεχνικές ομαδοποίησης. Το modularity για μια κοινότητα ορίζεται ως ένα κλάσμα των ακμών μέσα σε μία συστάδα μείον τον κλάσμα των αναμενόμενων ακμών αν οι ακμές είχαν τοποθετηθεί τυχαία. Παρόλα αυτά, το κριτήριο modularity, έχει αρκετά μειονεκτήματα όπως για παράδειγμα η ανικανότητά του να ανιχνεύσει μικρές σε μέγεθος κοινότητες. Σε αυτήν την εργασία, προτείνουμε ένα καινούρια κριτήριο διαμέρισης, εν ονόματι ‘inclusion’. Αυτό το κριτήριο εκτιμάει πόσο καλά ένα κόμβος ‘συμπεριλαμβάνεται’ στην κοινότητα του εξετάζοντας την ύπαρξη ακμών αλλά και την μη-ύπαρξη ακμών. Έχουμε υλοποιήσει αρκετές τεχνικές για την βελτιστοποίηση του κριτηρίου. Η πρώτη τεχνική ακολουθεί την agglomerative λογική , καθώς ξεκινάει τοποθετώντας κάθε κόμβο σε ξεχωριστή κοινότητα και έπειτα συνενώνει κοινότητες έτσι ώστε να βελτιωθεί το inclusion. Η επόμενη τεχνική που υλοποιήσαμε, έχει παρόμοια αρχική κατάσταση με την πρώτη, αλλά αντί να συνενώνει κοινότητες, μετακινεί ένα κόμβο κάθε φορά σε άλλη κοινότητα. Μία άλλη τεχνική, ήταν να αξιολογήσουμε τις λύσεις που παρήγαγε ο αλγόριθμος του spectral clustering. Στην πειραματική αξιολόγηση που κάναμε, τα αποτελέσματα έδειξαν πως το κριτήριο inclusion είναι αρκετά αποδοτικό στον εντοπισμό κοινοτήτων και συνήθως οδηγεί σε καλύτερες λύσεις του προβλήματος χωρίς να χρειάζεται να προσδιορίσουμε τον αριθμό των κοινοτήτων εκ των προτέρων. | el |
| heal.advisorName | Λύκας, Αριστείδης | el |
| heal.committeeMemberName | Λύκας, Αριστείδης | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 56 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΥ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΚΟΥΦΟΣ ΝΙΚΟΛΑΟΣ 2017.pdf | 1.15 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
