Μέθοδοι εντοπισμού κοινωνιών σε δίκτυα

Abstract

Ο εντοπισμός κοινωνιών σε δίκτυα είναι ένα απο τα πιο δημοφιλή θέματα της σύγχρονης επιστήμης δικτύων. Ένα απο τα πιο βασικά χαρακτηριστικά ενός δικτύου, το οποίο αναπαρίσταται απο έναν γράφο, είναι η κοινοτική του δομή. Ο εντοπισμός της κοινοτικής δομής σε ένα δίκτυο ή συσταδοποίησή του, δηλαδή η οργάνωση των κορυφών του σε ομάδες, με πολλές ακμές που ενώνουν κορυφές της ίδιας ομάδας και συγκριτικά με αυτές λιγότερες ακμές που ενώνουν κορυφές διαφορετικών ομάδων, είναι ένα θέμα που μελετάται και εξελίσσεται διαρκώς μέχρι και σήμερα. Σε επιστήμες όπως κοινωνιολογία, βιολογία ή επιστήμη των υπολογιστών όπου τα δίκτυα αναπαρίστανται ως γράφοι, ο εντοπισμός κοινοτήτων σε δίκτυα είναι μεγάλης σημασίας. Το πρόβλημα της συσταδοποίησης δικτύου ή γράφου, είναι ένα σύγχρονο επιστημονικό αντικείμενο, το οποίο έχει μελετηθεί απο διαφορετικές επιστημονικές σκοπιές. Στην παρούσα εργασία θα προσπαθήσουμε να κάνουμε μια διεξοδική ανάλυση του θέματος, απο τον ορισμό των βασικών συστατικών του, πάνω στα οποία δεν υπάρχει κοινώς αποδεκτό πρωτόκολλο, μέχρι την ανάλυση πολλών μεθόδων που έχουν αναπτυχθεί ανα τα χρόνια, ξεκινώντας απο παραδοσιακές μεθόδους και καταλήγοντας σε σύγχρονες. Στο τέλος θα κάνουμε μια σύγκριση αλγορίθμων απο διάφορες κατηγορίες μεθόδων που αναλύθηκαν, χρησιμοποιώντας συνθετικά δεδομένα (τεχνητά δίκτυα αναφοράς).