| Περίληψη: | Η παρούσα Διπλωματική Εργασία διαπραγματεύεται το ζήτημα του υπολογισμού της κεντρικότητας κόμβων κατευθυνόμενων γραφημάτων βάσει πρόσφατων τεχνικών που δεν έχουν διερευνηθεί επαρκώς στη βιβλιογραφία. Οι μέθοδοι που μελετώνται βασίζονται α) στην αναπαράσταση κατευθυνόμενων γραφημάτων με ερμιτιανά μιγαδικά μητρώα [30] αντί των μη συμμετρικών μητρώων που είναι η επικρατούσα αναπαράσταση και β) τον υπολογισμό συναρτήσεων μητρώων και ειδικότερα του αντιστρόφου χρησιμοποιώντας ειδικές μεθόδους pathsums που βασίζονται σε συνδυασμό γραφοθεωρίας και θεωρίας μητρώων [22]. Οι τεχνικές αυτές αναλύονται και αναπτύσσονται προγράμματα σε περιβάλλον Matlab για την αξιολόγησή τους σε σύγκριση με υπάρχουσες μετρικές κεντρικότητας και αλγορίθμους υπολογισμού της. Ο κώδικας που αναπτύχθηκε εφαρμόστηκε σε αραιά μητρώα γραφημάτων που έχουν προέλθει από εφαρμογές. Δείχνουμε ότι η μέθοδος αντιστροφής επιτυγχάνεται σημαντικά με κατάλληλη αναδιάταξη γραμμών και στηλών του αραιού μητρώου γειτνίασης. Συγκεκριμένα δοκιμάζουμε την μέθοδο αναδιάταξης reverse Cuthill-McKee [11], η οποία έχει ως αποτέλεσμα την συγκέντρωση των περισσότερων μη μηδενικών στοιχείων προς την κύρια διαγώνιο Επίσης αναλύεται εμπειρικά η ευστάθεια του αλγορίθμου αντιστροφής path-sum. Συμπεραίνουμε ότι οι μέθοδοι αναπαράστασης με ερμιτιανά μητρώα οδηγούν σε κεντρικότητες με διαφορετικά χαρακτηριστικά από εκείνα μεθόδων όπως κεντρικότητα βάσει ιδιοδιανυσμάτων και κεντρικότητα HITS, ενώ αποφεύγει τις δυσκολίες που παρουσιάζονται από την ύπαρξη μιγαδικών ιδιοτιμών στα μητρώα γειτνίασης. Αφήνουμε ανοικτό και προς διερεύνηση το ζήτημα της πληροφορίας που μπορεί να εξαχθεί από τις τιμές δυνάμεων των μιγαδικών αυτών μητρώων.
|
|---|
