Community detection in undirected graphs using a new quality measure
Loading...
Date
Authors
Κουφός, Νικόλαος
Journal Title
Journal ISSN
Volume Title
Publisher
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Abstract
Type
Type of the conference item
Journal type
Educational material type
Conference Name
Journal name
Book name
Book series
Book edition
Alternative title / Subtitle
Description
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.
Ο εντοπισμός κοινοτήτων παίζει σημαντικό ρόλο στην κοινωνιολογία, βιολογία, επιστήμη υπολογιστών καθώς και σε όλους τους τομείς όπου πολύπλοκα συστήματα , συχνά αναπαρίστανται ως γραφήματα η δίκτυα. Μία από τις πιο ενδιαφέρουσες ιδιότητες που έχει η αναπαράσταση με γραφήματα, είναι η δομή του σε κοινότητες, δηλαδή, η διαμέριση του γράφου σε συστάδες που απαρτίζονται από κόμβους που συνδέονται με πολλούς κόμβους της ίδιας συστάδας μέσο ακμών, και όσο δυνατόν λιγότερους κόμβους που ανήκουν σε άλλες συστάδες. Αυτό το πρόβλημα, παρά την δυσκολία του, έχει κεντρίσει το ενδιαφέρων διάφορων επιστημών τα τελευταία χρόνια, με αποτέλεσμα να προταθούν αρκετές τεχνικές επίλυσης του προβλήματος, κυρίως για τις περιπτώσεις όπου ο αριθμός των συστάδων δεν είναι γνωστός εκ των προτέρων. Η πιο γνωστή οικογένεια μεθόδων εντοπισμού κοινοτήτων είναι βασισμένη στην βελτιστοποίηση του κριτηρίου ‘modularity’ με διάφορες τεχνικές ομαδοποίησης. Το modularity για μια κοινότητα ορίζεται ως ένα κλάσμα των ακμών μέσα σε μία συστάδα μείον τον κλάσμα των αναμενόμενων ακμών αν οι ακμές είχαν τοποθετηθεί τυχαία. Παρόλα αυτά, το κριτήριο modularity, έχει αρκετά μειονεκτήματα όπως για παράδειγμα η ανικανότητά του να ανιχνεύσει μικρές σε μέγεθος κοινότητες. Σε αυτήν την εργασία, προτείνουμε ένα καινούρια κριτήριο διαμέρισης, εν ονόματι ‘inclusion’. Αυτό το κριτήριο εκτιμάει πόσο καλά ένα κόμβος ‘συμπεριλαμβάνεται’ στην κοινότητα του εξετάζοντας την ύπαρξη ακμών αλλά και την μη-ύπαρξη ακμών. Έχουμε υλοποιήσει αρκετές τεχνικές για την βελτιστοποίηση του κριτηρίου. Η πρώτη τεχνική ακολουθεί την agglomerative λογική , καθώς ξεκινάει τοποθετώντας κάθε κόμβο σε ξεχωριστή κοινότητα και έπειτα συνενώνει κοινότητες έτσι ώστε να βελτιωθεί το inclusion. Η επόμενη τεχνική που υλοποιήσαμε, έχει παρόμοια αρχική κατάσταση με την πρώτη, αλλά αντί να συνενώνει κοινότητες, μετακινεί ένα κόμβο κάθε φορά σε άλλη κοινότητα. Μία άλλη τεχνική, ήταν να αξιολογήσουμε τις λύσεις που παρήγαγε ο αλγόριθμος του spectral clustering. Στην πειραματική αξιολόγηση που κάναμε, τα αποτελέσματα έδειξαν πως το κριτήριο inclusion είναι αρκετά αποδοτικό στον εντοπισμό κοινοτήτων και συνήθως οδηγεί σε καλύτερες λύσεις του προβλήματος χωρίς να χρειάζεται να προσδιορίσουμε τον αριθμό των κοινοτήτων εκ των προτέρων.
Ο εντοπισμός κοινοτήτων παίζει σημαντικό ρόλο στην κοινωνιολογία, βιολογία, επιστήμη υπολογιστών καθώς και σε όλους τους τομείς όπου πολύπλοκα συστήματα , συχνά αναπαρίστανται ως γραφήματα η δίκτυα. Μία από τις πιο ενδιαφέρουσες ιδιότητες που έχει η αναπαράσταση με γραφήματα, είναι η δομή του σε κοινότητες, δηλαδή, η διαμέριση του γράφου σε συστάδες που απαρτίζονται από κόμβους που συνδέονται με πολλούς κόμβους της ίδιας συστάδας μέσο ακμών, και όσο δυνατόν λιγότερους κόμβους που ανήκουν σε άλλες συστάδες. Αυτό το πρόβλημα, παρά την δυσκολία του, έχει κεντρίσει το ενδιαφέρων διάφορων επιστημών τα τελευταία χρόνια, με αποτέλεσμα να προταθούν αρκετές τεχνικές επίλυσης του προβλήματος, κυρίως για τις περιπτώσεις όπου ο αριθμός των συστάδων δεν είναι γνωστός εκ των προτέρων. Η πιο γνωστή οικογένεια μεθόδων εντοπισμού κοινοτήτων είναι βασισμένη στην βελτιστοποίηση του κριτηρίου ‘modularity’ με διάφορες τεχνικές ομαδοποίησης. Το modularity για μια κοινότητα ορίζεται ως ένα κλάσμα των ακμών μέσα σε μία συστάδα μείον τον κλάσμα των αναμενόμενων ακμών αν οι ακμές είχαν τοποθετηθεί τυχαία. Παρόλα αυτά, το κριτήριο modularity, έχει αρκετά μειονεκτήματα όπως για παράδειγμα η ανικανότητά του να ανιχνεύσει μικρές σε μέγεθος κοινότητες. Σε αυτήν την εργασία, προτείνουμε ένα καινούρια κριτήριο διαμέρισης, εν ονόματι ‘inclusion’. Αυτό το κριτήριο εκτιμάει πόσο καλά ένα κόμβος ‘συμπεριλαμβάνεται’ στην κοινότητα του εξετάζοντας την ύπαρξη ακμών αλλά και την μη-ύπαρξη ακμών. Έχουμε υλοποιήσει αρκετές τεχνικές για την βελτιστοποίηση του κριτηρίου. Η πρώτη τεχνική ακολουθεί την agglomerative λογική , καθώς ξεκινάει τοποθετώντας κάθε κόμβο σε ξεχωριστή κοινότητα και έπειτα συνενώνει κοινότητες έτσι ώστε να βελτιωθεί το inclusion. Η επόμενη τεχνική που υλοποιήσαμε, έχει παρόμοια αρχική κατάσταση με την πρώτη, αλλά αντί να συνενώνει κοινότητες, μετακινεί ένα κόμβο κάθε φορά σε άλλη κοινότητα. Μία άλλη τεχνική, ήταν να αξιολογήσουμε τις λύσεις που παρήγαγε ο αλγόριθμος του spectral clustering. Στην πειραματική αξιολόγηση που κάναμε, τα αποτελέσματα έδειξαν πως το κριτήριο inclusion είναι αρκετά αποδοτικό στον εντοπισμό κοινοτήτων και συνήθως οδηγεί σε καλύτερες λύσεις του προβλήματος χωρίς να χρειάζεται να προσδιορίσουμε τον αριθμό των κοινοτήτων εκ των προτέρων.
Description
Keywords
Graphic methods, Quality measures, Datasets & results
Subject classification
Graphic methods
Citation
Link
Language
en
Publishing department/division
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Advisor name
Λύκας, Αριστείδης
Examining committee
Λύκας, Αριστείδης
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Table of contents
Sponsor
Bibliographic citation
Βιβλιογραφία : σ. 54-56
Name(s) of contributor(s)
Number of Pages
56 σ.