Μοντελοποίηση σε μπλοκ δικτύων με βάρη
Ο στόχος αυτής της εργασίας είναι η μελέτη κάποιων μαθηματικών μεθόδων για τη μοντελοποίηση σε μπλοκ δικτύων με βάρη -- όπως μελετήθηκαν στην διδακτορική διατριβή του Ziberna (2007). Στο μεγαλύτερό τους μέρος, οι μέθοδοι της μοντελοποίησης σε μπλοκ είχαν αναπτυχθεί αρχικά μόνο για δυαδικά και προ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2009
|
| Θέματα: | |
| Διαθέσιμο Online: | http://nemertes.lis.upatras.gr/jspui/handle/10889/2002 |
| id |
nemertes-10889-2002 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Μοντελοποίηση Δίκτυα Blockmodeling 302.011 |
| spellingShingle |
Μοντελοποίηση Δίκτυα Blockmodeling 302.011 Δημητρακόπουλος, Κωνσταντίνος Μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| description |
Ο στόχος αυτής της εργασίας είναι η μελέτη
κάποιων μαθηματικών μεθόδων για τη μοντελοποίηση σε μπλοκ δικτύων με
βάρη -- όπως μελετήθηκαν στην διδακτορική διατριβή του Ziberna (2007). Στο μεγαλύτερό τους μέρος, οι μέθοδοι της μοντελοποίησης σε μπλοκ είχαν αναπτυχθεί αρχικά μόνο για δυαδικά και προσημασμένα δίκτυα κυρίως από τους Doreian et al. (2005). Στην διατριβή του Ziberna (2007) συζητήθηκαν και αξιολογήθηκαν οι υπάρχουσες
προσεγγίσεις και επεκτάθηκαν για την μοντελοποίηση σε μπλοκ δικτύων με βάρη. Για τις έμμεσες προσέγγισεις,
σύμφωνα με τον γνωστό ορισμό της κανονικής ισοδυναμίας, ο Ziberna πρότεινε κάποιες σχετικές τροποποιήσεις.
Αυτό έγινε επίσης με στόχο να βρεθούν οι καλύτερες μέθοδοι
για τη μοντελοποίηση σε μπλοκ διαφορετικών τύπων
δικτύων με βάρη και για την αναζήτηση
των βέλτιστων λύσεων, που έχουν διαφορετικά χαρακτηριστικά (σύμφωνα με τους χρησιμοποιούμενους διαφορετικούς τύπους ισοδυναμίας, όπως θα δούμε στο Κεφάλαιο 2).
Η μοντελοποίηση σε μπλοκ των δικτύων αποτελεί μέρος της ανάλυσης κοινωνικών δικτύων (Wasserman και Faust, 1994), που είναι περιοχή της Μαθηματικής Κοινωνιολογίας. Στη θεωρία αυτή, μια σύντομη ανασκόπηση της οποίας θα δώσουμε στο Κεφάλαιο 1, ένα (κοινωνικό) δίκτυο είναι ένα σύνολο μονάδων,
οι οποίες συνδέονται μεταξύ τους με μια ή περισσότερες σχέσεις, που ορίζονται σε αυτές. Η μοντελοποίηση σε μπλοκ (κοινωνικών) δικτύων είναι μια μέθοδος για τη διαμέριση (ή ομαδοποίηση - clustering) των μονάδων ενός δικτύου και για τον προσδιορισμό της δομής
των αθροιστικών σχέσεων μεταξύ των ομάδων, που σχηματίζονται από τις ομαδοποιημένες (διαμερισμένες) μονάδες. Έτσι, η
μοντελοποίηση σε μπλοκ αναζητεί ομάδες ισοδύναμων μονάδων με βάση
κάποια συγκεκριμένη έννοια ισοδυναμίας. Όπως παρατηρεί ο
Doreian (1988), ``η ισοδυναμία έχει γίνει μια θεμελιώδης έννοια
της ανάλυσης κοινωνικών δικτύων". Οι δύο ευρύτερα
χρησιμοποιούμενες έννοιες ισοδυναμίας είναι η δομική και η
κανονική ισοδυναμία.
Για τους σκοπούς της παρούσας εργασίας, όπως θα δούμε στο Κεφάλαιο 2, οι μέθοδοι της μοντελοποίησης σε
μπλοκ διαιρούνται στις έμμεσες και τις άμεσες προσεγγίσεις. Οι έμμεσες προσεγγίσεις υπολογίζουν αρχικά κάποιο μέτρο ομοιότητας ή
ανομοιότητας μεταξύ των μονάδων ενός δικτύου με βάση ένα
επιλεγμένο μέτρο ισοδυναμίας και χρησιμοποιούν έπειτα μια από τις
κλασσικές τεχνικές ομαδοποίησης, για να προσδιορίσουν τις ομάδες των
μονάδων. Από την άλλη μεριά, οι άμεσες προσεγγίσεις αναζητούν άμεσα μια διαμέριση, η οποία ταιριάζει καλύτερα στην επιλεγμένη ισοδυναμία και η οποία μετράται σύμφωνα με μια επιλεγμένη συνάρτηση κριτηρίου (Batagelj, 1992). Η μέθοδος της γενικευμένης μοντελοποίησης σε μπλοκ βασίζεται στην άμεση προσέγγιση. Όταν συγκρίνεται με άλλες άμεσες προσεγγίσεις, η
κύρια δύναμή της είναι η προσαρμοστικότητά της. Μπορεί να
χρησιμοποιηθεί για να πραγματοποιήσει κάποια μοντελοποίηση σε μπλοκ σύμφωνα με διαφορετικούς τύπους ισοδυναμίας, συμπεριλαμβανομένης και της γενικευμένης ισοδυναμίας. Η γενικευμένη ισοδυναμία δεν είναι ένας
συγκεκριμένος τύπος ισοδυναμίας, αλλά περισσότερο μια έννοια για
την κατασκευή ``ειδικών" ισοδυναμιών. Ορίζεται σύμφωνα με έναν προηγούμενο καθορισμό των επιτρεπόμενων τύπων συνδέσεων μεταξύ των ομάδων και μεταξύ μονάδων μέσα στις ομάδες. Πάντως, ενώ η γενικευμένη μοντελοποίηση σε μπλοκ αρχικά είχε αναπτυχθεί για δυαδικά και προσημασμένα δίκτυα, ο Ziberna (2007) ήταν ο πρώτος που την μελέτησε για δίκτυα με βάρη. Για το σκοπό αυτό, ο Ziberna εισήγαγε κάποιους νέους τύπους μπλοκ, που είναι κατάλληλοι για δίκτυα με βάρη.
Τα κοινά χαρακτηριστικά όλων των προσεγγίσεων
γενικευμένης μοντελοποίησης σε μπλοκ, εκτός από την κοινή βασική συνάρτηση κριτηρίου, περιλαμβάνουν την δυνατότητα προσδιορισμού της επιθυμητής λύσης είτε μέσω ενός τύπου ισοδυναμίας (που στη συνέχεια μεταφράζεται στους επιτρεπόμενους τύπους μπλοκ) ή μέσω κάποιας γενικευμένης ισοδυναμίας (η οποία ορίζεται άμεσα από τους επιτρεπόμενους τύπους μπλοκ ή, ακόμα ακριβέστερα, από το επιθυμητό μοντέλο των μπλοκ). Μια τέτοια έννοια ισοδυναμίας είναι η f-κανονική
ισοδυναμία για δίκτυα με βάρη, η οποία αντιστοιχεί στην κανονική ισοδυναμία για τα δυαδικά ή προσημασμένα δίκτυα.
Επιπλέον, θα μελετήσουμε στην εργασία αυτή κάποιους αλγόριθμους, που υλοποιούν τους υπολογισμούς για συγκεκριμένες μεθόδους μοντελοποίησης σε μπλοκ. Έτσι, για τις έμμεσες προσεγγίσεις, θα χρησιμοποιήσουμε τους αλγόριθμους REGE για τον υπολογισμό των
ομοιοτήτων ή ανομοιοτήτων κάτω από συνθήκες κανονικής ισοδυναμίας.
Στο Κεφάλαιο 3, όπου βρίσκεται ο πυρήνας της εργασίας,
αναπτύσσονται οι μέθοδοι της γενικευμένης μοντελοποίησης σε μπλοκ δικτύων με βάρη. Αυτές οι προσεγγίσεις είναι οι εξής: η μοντελοποίηση σε μπλοκ με βάρη, η ομοιογενής μοντελοποίηση σε μπλοκ και η πεπλεγμένη μοντελοποίηση σε μπλοκ. Επιπλέον, ακολουθώντας τον Ziberna (2007), οι ιδέες των Batagelj και Ferligoj (2000) συζητώνται και αναπτύσσονται περαιτέρω για την περίπτωση της πεπλεγμένης μοντελοποίησης σε μπλοκ. Για να ενσωματώσει τις προτάσεις του για διάφορους τύπους μοντελοποίησης δικτύων με βάρη, ο Ziberna (2007) έχει αναπτύξει ένα σχετικό υπολογιστικό πακέτο, το blockmodeling, το οποίο είναι δομημένο πάνω στο προγραμματιστικό περιβάλλον R (R Development Core Team 2006). Αυτό θα παρουσιαστεί και θα συζητηθεί στο τέλος του Κεφαλαίου 3.
Τέλος, στο Κεφάλαιο 4, θα εφαρμόσουμε τις μεθόδους της μοντελοποίησης σε μπλοκ σε διάφορα εμπειρικά και τεχνητά παραδείγματα. Ακόμα, στα παραδείγματα αυτά, οι προτεινόμενες προσεγγίσεις θα συγκριθούν ως προς τα θεωρητικά
χαρακτηριστικά τους και την απόδοσή τους. |
| author2 |
Μπουντουρίδης, Μωυσής |
| author_facet |
Μπουντουρίδης, Μωυσής Δημητρακόπουλος, Κωνσταντίνος |
| format |
Thesis |
| author |
Δημητρακόπουλος, Κωνσταντίνος |
| author_sort |
Δημητρακόπουλος, Κωνσταντίνος |
| title |
Μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| title_short |
Μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| title_full |
Μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| title_fullStr |
Μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| title_full_unstemmed |
Μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| title_sort |
μοντελοποίηση σε μπλοκ δικτύων με βάρη |
| publishDate |
2009 |
| url |
http://nemertes.lis.upatras.gr/jspui/handle/10889/2002 |
| work_keys_str_mv |
AT dēmētrakopouloskōnstantinos montelopoiēsēsemplokdiktyōnmebarē |
| _version_ |
1771297286466306048 |
| spelling |
nemertes-10889-20022022-09-05T20:12:44Z Μοντελοποίηση σε μπλοκ δικτύων με βάρη Δημητρακόπουλος, Κωνσταντίνος Μπουντουρίδης, Μωυσής Αλεβίζος, Παναγιώτης Αλεβίζος, Φίλιππος Μπουντουρίδης, Μωυσής Μοντελοποίηση Δίκτυα Blockmodeling 302.011 Ο στόχος αυτής της εργασίας είναι η μελέτη κάποιων μαθηματικών μεθόδων για τη μοντελοποίηση σε μπλοκ δικτύων με βάρη -- όπως μελετήθηκαν στην διδακτορική διατριβή του Ziberna (2007). Στο μεγαλύτερό τους μέρος, οι μέθοδοι της μοντελοποίησης σε μπλοκ είχαν αναπτυχθεί αρχικά μόνο για δυαδικά και προσημασμένα δίκτυα κυρίως από τους Doreian et al. (2005). Στην διατριβή του Ziberna (2007) συζητήθηκαν και αξιολογήθηκαν οι υπάρχουσες προσεγγίσεις και επεκτάθηκαν για την μοντελοποίηση σε μπλοκ δικτύων με βάρη. Για τις έμμεσες προσέγγισεις, σύμφωνα με τον γνωστό ορισμό της κανονικής ισοδυναμίας, ο Ziberna πρότεινε κάποιες σχετικές τροποποιήσεις. Αυτό έγινε επίσης με στόχο να βρεθούν οι καλύτερες μέθοδοι για τη μοντελοποίηση σε μπλοκ διαφορετικών τύπων δικτύων με βάρη και για την αναζήτηση των βέλτιστων λύσεων, που έχουν διαφορετικά χαρακτηριστικά (σύμφωνα με τους χρησιμοποιούμενους διαφορετικούς τύπους ισοδυναμίας, όπως θα δούμε στο Κεφάλαιο 2). Η μοντελοποίηση σε μπλοκ των δικτύων αποτελεί μέρος της ανάλυσης κοινωνικών δικτύων (Wasserman και Faust, 1994), που είναι περιοχή της Μαθηματικής Κοινωνιολογίας. Στη θεωρία αυτή, μια σύντομη ανασκόπηση της οποίας θα δώσουμε στο Κεφάλαιο 1, ένα (κοινωνικό) δίκτυο είναι ένα σύνολο μονάδων, οι οποίες συνδέονται μεταξύ τους με μια ή περισσότερες σχέσεις, που ορίζονται σε αυτές. Η μοντελοποίηση σε μπλοκ (κοινωνικών) δικτύων είναι μια μέθοδος για τη διαμέριση (ή ομαδοποίηση - clustering) των μονάδων ενός δικτύου και για τον προσδιορισμό της δομής των αθροιστικών σχέσεων μεταξύ των ομάδων, που σχηματίζονται από τις ομαδοποιημένες (διαμερισμένες) μονάδες. Έτσι, η μοντελοποίηση σε μπλοκ αναζητεί ομάδες ισοδύναμων μονάδων με βάση κάποια συγκεκριμένη έννοια ισοδυναμίας. Όπως παρατηρεί ο Doreian (1988), ``η ισοδυναμία έχει γίνει μια θεμελιώδης έννοια της ανάλυσης κοινωνικών δικτύων". Οι δύο ευρύτερα χρησιμοποιούμενες έννοιες ισοδυναμίας είναι η δομική και η κανονική ισοδυναμία. Για τους σκοπούς της παρούσας εργασίας, όπως θα δούμε στο Κεφάλαιο 2, οι μέθοδοι της μοντελοποίησης σε μπλοκ διαιρούνται στις έμμεσες και τις άμεσες προσεγγίσεις. Οι έμμεσες προσεγγίσεις υπολογίζουν αρχικά κάποιο μέτρο ομοιότητας ή ανομοιότητας μεταξύ των μονάδων ενός δικτύου με βάση ένα επιλεγμένο μέτρο ισοδυναμίας και χρησιμοποιούν έπειτα μια από τις κλασσικές τεχνικές ομαδοποίησης, για να προσδιορίσουν τις ομάδες των μονάδων. Από την άλλη μεριά, οι άμεσες προσεγγίσεις αναζητούν άμεσα μια διαμέριση, η οποία ταιριάζει καλύτερα στην επιλεγμένη ισοδυναμία και η οποία μετράται σύμφωνα με μια επιλεγμένη συνάρτηση κριτηρίου (Batagelj, 1992). Η μέθοδος της γενικευμένης μοντελοποίησης σε μπλοκ βασίζεται στην άμεση προσέγγιση. Όταν συγκρίνεται με άλλες άμεσες προσεγγίσεις, η κύρια δύναμή της είναι η προσαρμοστικότητά της. Μπορεί να χρησιμοποιηθεί για να πραγματοποιήσει κάποια μοντελοποίηση σε μπλοκ σύμφωνα με διαφορετικούς τύπους ισοδυναμίας, συμπεριλαμβανομένης και της γενικευμένης ισοδυναμίας. Η γενικευμένη ισοδυναμία δεν είναι ένας συγκεκριμένος τύπος ισοδυναμίας, αλλά περισσότερο μια έννοια για την κατασκευή ``ειδικών" ισοδυναμιών. Ορίζεται σύμφωνα με έναν προηγούμενο καθορισμό των επιτρεπόμενων τύπων συνδέσεων μεταξύ των ομάδων και μεταξύ μονάδων μέσα στις ομάδες. Πάντως, ενώ η γενικευμένη μοντελοποίηση σε μπλοκ αρχικά είχε αναπτυχθεί για δυαδικά και προσημασμένα δίκτυα, ο Ziberna (2007) ήταν ο πρώτος που την μελέτησε για δίκτυα με βάρη. Για το σκοπό αυτό, ο Ziberna εισήγαγε κάποιους νέους τύπους μπλοκ, που είναι κατάλληλοι για δίκτυα με βάρη. Τα κοινά χαρακτηριστικά όλων των προσεγγίσεων γενικευμένης μοντελοποίησης σε μπλοκ, εκτός από την κοινή βασική συνάρτηση κριτηρίου, περιλαμβάνουν την δυνατότητα προσδιορισμού της επιθυμητής λύσης είτε μέσω ενός τύπου ισοδυναμίας (που στη συνέχεια μεταφράζεται στους επιτρεπόμενους τύπους μπλοκ) ή μέσω κάποιας γενικευμένης ισοδυναμίας (η οποία ορίζεται άμεσα από τους επιτρεπόμενους τύπους μπλοκ ή, ακόμα ακριβέστερα, από το επιθυμητό μοντέλο των μπλοκ). Μια τέτοια έννοια ισοδυναμίας είναι η f-κανονική ισοδυναμία για δίκτυα με βάρη, η οποία αντιστοιχεί στην κανονική ισοδυναμία για τα δυαδικά ή προσημασμένα δίκτυα. Επιπλέον, θα μελετήσουμε στην εργασία αυτή κάποιους αλγόριθμους, που υλοποιούν τους υπολογισμούς για συγκεκριμένες μεθόδους μοντελοποίησης σε μπλοκ. Έτσι, για τις έμμεσες προσεγγίσεις, θα χρησιμοποιήσουμε τους αλγόριθμους REGE για τον υπολογισμό των ομοιοτήτων ή ανομοιοτήτων κάτω από συνθήκες κανονικής ισοδυναμίας. Στο Κεφάλαιο 3, όπου βρίσκεται ο πυρήνας της εργασίας, αναπτύσσονται οι μέθοδοι της γενικευμένης μοντελοποίησης σε μπλοκ δικτύων με βάρη. Αυτές οι προσεγγίσεις είναι οι εξής: η μοντελοποίηση σε μπλοκ με βάρη, η ομοιογενής μοντελοποίηση σε μπλοκ και η πεπλεγμένη μοντελοποίηση σε μπλοκ. Επιπλέον, ακολουθώντας τον Ziberna (2007), οι ιδέες των Batagelj και Ferligoj (2000) συζητώνται και αναπτύσσονται περαιτέρω για την περίπτωση της πεπλεγμένης μοντελοποίησης σε μπλοκ. Για να ενσωματώσει τις προτάσεις του για διάφορους τύπους μοντελοποίησης δικτύων με βάρη, ο Ziberna (2007) έχει αναπτύξει ένα σχετικό υπολογιστικό πακέτο, το blockmodeling, το οποίο είναι δομημένο πάνω στο προγραμματιστικό περιβάλλον R (R Development Core Team 2006). Αυτό θα παρουσιαστεί και θα συζητηθεί στο τέλος του Κεφαλαίου 3. Τέλος, στο Κεφάλαιο 4, θα εφαρμόσουμε τις μεθόδους της μοντελοποίησης σε μπλοκ σε διάφορα εμπειρικά και τεχνητά παραδείγματα. Ακόμα, στα παραδείγματα αυτά, οι προτεινόμενες προσεγγίσεις θα συγκριθούν ως προς τα θεωρητικά χαρακτηριστικά τους και την απόδοσή τους. The aim of my work is to study and test approaches to the generalized blockmodeling of valued networks since so far the generalized blockmodeling approach has only been developed for binary and signed networks by Doreian et al. (2005). In addition, existing approaches that could be used for the blockmodeling of valued networks are discussed and evaluated. This is done with the aim to find the best methods or approaches for the blockmodeling of different types of valued networks1 in the search for optimal solutions with different characteristics. Generalized blockmodeling forms part of (social) network analysis. Simply put, a network is a set of units with one or more relations defined on them. Blockmodeling is a method for partitioning the units of a network and determining the pattern of relations among (obtained) clusters. Blockmodeling seeks clusters of equivalent units based on some notion of equivalence. The two most widely used equivalences are structural and regular equivalence. For the purpose of this dissertation, one of the most important divisions of blockmodeling approaches is into indirect and direct approaches. Indirect approaches first compute some measure of similarity or dissimilarity among the units of a network based on a selected measure of equivalence and then use one of the classical clustering techniques to uncover clusters of units, while direct approaches directly search for a partition that best fits the selected equivalence as measured by a selected criterion function. Generalized blockmodeling is based on the direct approach. When compared to other direct approaches, its main strength is its adaptability. It can be used to perform blockmodeling according to different types of equivalences, including generalized equivalence. Generalized equivalence is not a specific type of equivalence but more of a concept for building ‘custom’ equivalences. It is defined by specifying allowed types of connections between and within clusters. However, up till now generalized blockmodeling has only been developed for binary and signed networks. Here new approaches, by Ziberna, to the generalized blockmodeling of valued networks are discussed. However, as they can still be regarded as approaches to generalized blockmodeling as presented by Doreian et al. (2005) the same type of criterion function can be used. The most important differences between the approaches to generalized blockmodeling presented by Doreian et al. (2005) and those developed here is that the approaches presented by Doreian et al. (2005) can be applied to binary and signed networks, while those presented here can be applied to valued networks. To achieve that, new block types appropriate for valued networks are introduced by Ziberna. The common characteristics of all approaches to generalized blockmodeling are, in addition to the common basic criterion function, their ability to specify the desired solution either by a type of equivalence (which is then translated into allowed block types) or by generalized equivalence. Generalized equivalence is defined directly by the allowed block types or even more precisely by the desired blockmodel. In addition to generalized blockmodeling, other approaches to blockmodeling are reviewed (indirect blockmodeling and other direct approaches). For one family of algorithms that falls into the category of indirect approaches, the REGE algorithms for computing (dis)similarities in terms of regular equivalence, some modified versions are also presented. They and some other approaches are then tested on several empirical and constructed examples. The proposed approaches are compared based on their theoretical characteristics and their performance in the examples. 2009-10-09T10:34:25Z 2009-10-09T10:34:25Z 2009-06-30 2009-10-09T10:34:25Z Thesis http://nemertes.lis.upatras.gr/jspui/handle/10889/2002 gr Η ΒKΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου. 0 application/pdf |
