Εντοπισµός εξελικτικών µοντέλων σε πραγµατικά και συνθετικά δίκτυα

Abstract

Τις τελευταίες δύο δεκαετίες, η συζήτηση της επιστημονικής κοινότητας περί του εξελικτικού μοντέλου στο οποίο ταξινομούνται διάφορα είδη πραγματικών δικτύων έχει υπάρξει έντονη, συνοδευόμενη από πληθώρα αντικρουόμενων ερευνών πάνω στο θέμα αυτό. Επιπλέον, πρόσφατα εισήχθη η θεώρηση ότι μεγάλο ποσοστό των πραγματικών δικτύων αποτελούνται από συνιστώσες που χαρακτηρίζονται από διαφορετικά εξελικτικά μοντέλα. Τα γεγονότα αυτά ενέπνευσαν την επιλογή του αντικειμένου της παρούσας εργασίας, η οποία αποσκοπεί στην διερεύνηση της συχνότητας εμφάνισης κάθε εξελικτικού μοντέλου στα πραγματικά δίκτυα, και την ισχύ της προαναφερθείσας θεώρησης. Για την πραγματοποίηση του στόχου αυτού, αξιολογήθηκαν αρχικά 20 μετρικές δικτύων σχετικά με την καταλληλότητά τους για χρήση ως είσοδοι ενός ταξινομητή. Έπειτα, δημιουργήθηκε ένα σύνολο 600 συνθετικών δικτύων, και υπολογίστηκαν οι τιμές των επιλεγμένων μετρικών για αυτά. Ύστερα οι τιμές αυτές χρησιμοποιήθηκαν ως τα δεδομένα εκπαίδευσης και ελέγχου μίας σειράς ταξινομητών, οι οποίοι αξιολογήθηκαν με σκοπό την επιλογή του βέλτιστου. Ο βέλτιστος ταξινομητής χρησιμοποιήθηκε για την ταξινόμηση 17 πραγματικών δικτύων, τα οποία ύστερα τμηματοποιήθηκαν με χρήση επιλεγμένου αλγορίθμου τμηματοποίησης, και οι συνιστώσες που προέκυψαν ταξινομήθηκαν και αυτές. Η ανάλυση των αποτελεσμάτων έδειξε πως πιο συχνά εμφανίζονται τα Δίκτυα Μικρού Κόσμου (Small-World) και τα Μη-Κλιμακούμενα Δίκτυα (Scale-Free). Ακόμη, η παρουσία του μοντέλου Small-World είναι ιδιαίτερα εκτεταμένη στα δίκτυα μεταφορών, ενώ το Scale-Free εμφανίζεται ως επί το πλείστον ως η μεγαλύτερη συνιστώσα σε κοινωνικά δίκτυα. Το μοντέλο Waxman επίσης εμφανίζεται συχνά ως συνιστώσα στα κοινωνικά δίκτυα, ενώ για τα υπόλοιπα μοντέλα δεν παρατηρήθηκε κάποιο μοτίβο. Τέλος, συμπεραίνουμε πως η θεώρηση σχετικά με την ύπαρξη συνιστωσών με διαφορετικά μοντέλα στα δίκτυα είναι σωστή.