| Περίληψη: | Ο στόχος αυτής της εργασίας είναι η μελέτη
κάποιων μαθηματικών μεθόδων για τη μοντελοποίηση σε μπλοκ δικτύων με
βάρη -- όπως μελετήθηκαν στην διδακτορική διατριβή του 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, θα εφαρμόσουμε τις μεθόδους της μοντελοποίησης σε μπλοκ σε διάφορα εμπειρικά και τεχνητά παραδείγματα. Ακόμα, στα παραδείγματα αυτά, οι προτεινόμενες προσεγγίσεις θα συγκριθούν ως προς τα θεωρητικά
χαρακτηριστικά τους και την απόδοσή τους.
|
|---|
