Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums
Η παρούσα Διπλωματική Εργασία διαπραγματεύεται το ζήτημα του υπολογισμού της κεντρικότητας κόμβων κατευθυνόμενων γραφημάτων βάσει πρόσφατων τεχνικών που δεν έχουν διερευνηθεί επαρκώς στη βιβλιογραφία. Οι μέθοδοι που μελετώνται βασίζονται α) στην αναπαράσταση κατευθυνόμενων γραφημάτων με ερμιτιανά μι...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2020
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/14191 |
| id |
nemertes-10889-14191 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-141912022-09-05T14:11:07Z Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums Centrality measures for directed graphs with Hermitian adjacency matrices and Path-Sums method Καρακίτσου, Ελευθερία-Σοφία Karakitsou, Eleftheria-Sofia Κεντρικότητα γραφημάτων Κεντρικότητα Katz Κεντρικότητα γραφημάτων βάσει ερμιτιανών μητρώων Μέθοδος αντιστροφής path-sums Centrality Hermitian adjacency matrices Η παρούσα Διπλωματική Εργασία διαπραγματεύεται το ζήτημα του υπολογισμού της κεντρικότητας κόμβων κατευθυνόμενων γραφημάτων βάσει πρόσφατων τεχνικών που δεν έχουν διερευνηθεί επαρκώς στη βιβλιογραφία. Οι μέθοδοι που μελετώνται βασίζονται α) στην αναπαράσταση κατευθυνόμενων γραφημάτων με ερμιτιανά μιγαδικά μητρώα [30] αντί των μη συμμετρικών μητρώων που είναι η επικρατούσα αναπαράσταση και β) τον υπολογισμό συναρτήσεων μητρώων και ειδικότερα του αντιστρόφου χρησιμοποιώντας ειδικές μεθόδους pathsums που βασίζονται σε συνδυασμό γραφοθεωρίας και θεωρίας μητρώων [22]. Οι τεχνικές αυτές αναλύονται και αναπτύσσονται προγράμματα σε περιβάλλον Matlab για την αξιολόγησή τους σε σύγκριση με υπάρχουσες μετρικές κεντρικότητας και αλγορίθμους υπολογισμού της. Ο κώδικας που αναπτύχθηκε εφαρμόστηκε σε αραιά μητρώα γραφημάτων που έχουν προέλθει από εφαρμογές. Δείχνουμε ότι η μέθοδος αντιστροφής επιτυγχάνεται σημαντικά με κατάλληλη αναδιάταξη γραμμών και στηλών του αραιού μητρώου γειτνίασης. Συγκεκριμένα δοκιμάζουμε την μέθοδο αναδιάταξης reverse Cuthill-McKee [11], η οποία έχει ως αποτέλεσμα την συγκέντρωση των περισσότερων μη μηδενικών στοιχείων προς την κύρια διαγώνιο Επίσης αναλύεται εμπειρικά η ευστάθεια του αλγορίθμου αντιστροφής path-sum. Συμπεραίνουμε ότι οι μέθοδοι αναπαράστασης με ερμιτιανά μητρώα οδηγούν σε κεντρικότητες με διαφορετικά χαρακτηριστικά από εκείνα μεθόδων όπως κεντρικότητα βάσει ιδιοδιανυσμάτων και κεντρικότητα HITS, ενώ αποφεύγει τις δυσκολίες που παρουσιάζονται από την ύπαρξη μιγαδικών ιδιοτιμών στα μητρώα γειτνίασης. Αφήνουμε ανοικτό και προς διερεύνηση το ζήτημα της πληροφορίας που μπορεί να εξαχθεί από τις τιμές δυνάμεων των μιγαδικών αυτών μητρώων. This Thesis deals with the issue of calculating graph centrality based on recent techniques that have not been sufficiently explored in the literature. The methods studied are based on a) the representation of directed graphs with Hermitian adjacency matrices, instead of asymmetric adjacency matrices, which are commonly used and b) calculation of matrix functions and in particular the inverse matrix using the path-sums method, which is based on a combination of graph theory and linear algebra. These techniques are analyzed and the corresponding code is developed in Matlab for their evaluation in comparison with existing centrality metrics and its calculation algorithms. The code developed was applied to sparse adjacency matrices derived from applications. We experiment with the reverse Cuthill-McKee reordering which brings most non-zero elements towards the diagonal and show that this is quite effective in reducing runtimes for several examples of network related sparse matrices. We provide numerical experiments that indicate that our implementation of the path-sum method is numerically stable. We conclude that the centrality method using Hermitian adjacency matrices lead to centralities with different outcome from those of methods such as eigenvector centrality and HITS centrality, while avoiding the difficulties presented by the existence of complex eigenvalues of the adjacency matrix. We leave open for discussion the issue of the information that can be extracted from the power of the hermitian adjacency matrices. 2020-11-18T21:26:07Z 2020-11-18T21:26:07Z 2020-11-13 http://hdl.handle.net/10889/14191 gr application/pdf winrar |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Κεντρικότητα γραφημάτων Κεντρικότητα Katz Κεντρικότητα γραφημάτων βάσει ερμιτιανών μητρώων Μέθοδος αντιστροφής path-sums Centrality Hermitian adjacency matrices |
| spellingShingle |
Κεντρικότητα γραφημάτων Κεντρικότητα Katz Κεντρικότητα γραφημάτων βάσει ερμιτιανών μητρώων Μέθοδος αντιστροφής path-sums Centrality Hermitian adjacency matrices Καρακίτσου, Ελευθερία-Σοφία Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums |
| description |
Η παρούσα Διπλωματική Εργασία διαπραγματεύεται το ζήτημα του υπολογισμού της κεντρικότητας κόμβων κατευθυνόμενων γραφημάτων βάσει πρόσφατων τεχνικών που δεν έχουν διερευνηθεί επαρκώς στη βιβλιογραφία. Οι μέθοδοι που μελετώνται βασίζονται α) στην αναπαράσταση κατευθυνόμενων γραφημάτων με ερμιτιανά μιγαδικά μητρώα [30] αντί των μη συμμετρικών μητρώων που είναι η επικρατούσα αναπαράσταση και β) τον υπολογισμό συναρτήσεων μητρώων και ειδικότερα του αντιστρόφου χρησιμοποιώντας ειδικές μεθόδους pathsums που βασίζονται σε συνδυασμό γραφοθεωρίας και θεωρίας μητρώων [22]. Οι τεχνικές αυτές αναλύονται και αναπτύσσονται προγράμματα σε περιβάλλον Matlab για την αξιολόγησή τους σε σύγκριση με υπάρχουσες μετρικές κεντρικότητας και αλγορίθμους υπολογισμού της. Ο κώδικας που αναπτύχθηκε εφαρμόστηκε σε αραιά μητρώα γραφημάτων που έχουν προέλθει από εφαρμογές. Δείχνουμε ότι η μέθοδος αντιστροφής επιτυγχάνεται σημαντικά με κατάλληλη αναδιάταξη γραμμών και στηλών του αραιού μητρώου γειτνίασης. Συγκεκριμένα δοκιμάζουμε την μέθοδο αναδιάταξης reverse Cuthill-McKee [11], η οποία έχει ως αποτέλεσμα την συγκέντρωση των περισσότερων μη μηδενικών στοιχείων προς την κύρια διαγώνιο Επίσης αναλύεται εμπειρικά η ευστάθεια του αλγορίθμου αντιστροφής path-sum. Συμπεραίνουμε ότι οι μέθοδοι αναπαράστασης με ερμιτιανά μητρώα οδηγούν σε κεντρικότητες με διαφορετικά χαρακτηριστικά από εκείνα μεθόδων όπως κεντρικότητα βάσει ιδιοδιανυσμάτων και κεντρικότητα HITS, ενώ αποφεύγει τις δυσκολίες που παρουσιάζονται από την ύπαρξη μιγαδικών ιδιοτιμών στα μητρώα γειτνίασης. Αφήνουμε ανοικτό και προς διερεύνηση το ζήτημα της πληροφορίας που μπορεί να εξαχθεί από τις τιμές δυνάμεων των μιγαδικών αυτών μητρώων. |
| author2 |
Karakitsou, Eleftheria-Sofia |
| author_facet |
Karakitsou, Eleftheria-Sofia Καρακίτσου, Ελευθερία-Σοφία |
| author |
Καρακίτσου, Ελευθερία-Σοφία |
| author_sort |
Καρακίτσου, Ελευθερία-Σοφία |
| title |
Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums |
| title_short |
Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums |
| title_full |
Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums |
| title_fullStr |
Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums |
| title_full_unstemmed |
Υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους Path-Sums |
| title_sort |
υπολογισμοί κεντρικότητας κατευθυνόμενων γραφημάτων με ερμιτιανά μητρώα και μεθόδους path-sums |
| publishDate |
2020 |
| url |
http://hdl.handle.net/10889/14191 |
| work_keys_str_mv |
AT karakitsoueleutheriasophia ypologismoikentrikotētaskateuthynomenōngraphēmatōnmeermitianamētrōakaimethodouspathsums AT karakitsoueleutheriasophia centralitymeasuresfordirectedgraphswithhermitianadjacencymatricesandpathsumsmethod |
| _version_ |
1771297240081498112 |
