| Περίληψη: | Τα τελευταία χρόνια έχει παρατηρηθεί ιδιαίτερο ερευνητικό ενδιαφέρον στη μελέτη δικτύων (γραφημάτων) που προκύπτουν από διάφορες κοινωνικές, τεχνολογικές και επιστημονικές δραστηριότητες. Χαρακτηριστικά παραδείγματα αποτελούν το γράφημα του Διαδικτύου, το γράφημα του Παγκοσμίου Ιστού, κοινωνικά δίκτυα αναπαράστασης της αλληλεπίδρασης των ατόμων στην κοινωνία ή των χρηστών σε υπηρεσίες κοινωνικής δικτύωσης, δίκτυα μοντελοποίησης της συνεργασίας μεταξύ οντοτήτων, βιολογικά δίκτυα, κ.α.. Βασικό χαρακτηριστικό των γραφημάτων αυτών αποτελεί το μεγάλο μέγεθός τους, κάτι που πολλές φορές δυσχαιρένει την ανάλυση και μελέτη τους. Επιπλέον, τα γραφήματα αυτά στις περισσότερες περιπτώσεις δεν είναι στατικά, αλλά εξελίσσονται στο χρόνο με την προσθήκη-διαγραφή κόμβων και ακμών. Έτσι, ορισμένα από τα ερωτήματα που προκύπτουν και έχουν απασχολήσει την ερευνητική κοινότητα είναι πώς μπορούμε να αναλύσουμε τέτοιου είδους γραφήματα και να εξάγουμε ενδιαφέρουσα πληροφορία, ποια είναι η δομή των γραφημάτων αυτών, καθώς και ο τρόπος με τον οποίο δομούνται και εξελίσσονται στο χρόνο.
Ένα σημαντικό θέμα που σχετίζεται με τη δομή των γραφημάτων αυτών, αποτελεί η έννοια της ανθεκτικότητας. Γενικά, ένα γράφημα χαρακτηρίζεται ως ανθεκτικό, αν έχει τη δυνατότητα να διατηρήσει τη δομή του και τις ιδιότητες συνεκτικότητας που κατέχει, ύστερα από την απώλεια ενός μέρους των κόμβων και ακμών του. Η ιδιότητα της ανθεκτικότητας σε πραγματικά γραφήματα είναι άμεσα συνυφασμένη με την έννοια της δομής κοινοτήτων (community structure), δηλαδή της οργάνωσης των κόμβων σε ομάδες με υψηλό πλήθος συνδέσεων μεταξύ κόμβων της ίδιας ομάδας και μικρό πλήθος μεταξύ κόμβων που ανήκουν σε διαφορετικές ομάδες.
Πώς μπορούμε να κάνουμε μια γρήγορη εκτίμηση των ιδιοτήτων ανθεκτικότητας ενός γραφήματος, χωρίς να επιτελέσουμε μια διαδικασία διαγραφής κόμβων και ακμών όπου σε κάθε βήμα υπολογίζεται η συνεκτικότητα; Με άλλα λόγια, υπάρχει κάποιος δείκτης (μετρική) που μπορεί να μας ενημερώσει τόσο για την ανθεκτικότητα όσο και για τις ιδιότητες δομής κοινοτήτων ενός γραφήματος, ο οποίος θα μπορεί να υπολογιστεί αρκετά γρήγορα ακόμα και για γραφήματα με εκατομμύρια κόμβους και ακμές; Επιπλέον, εάν το γράφημα εξελίσσεται στο χρόνο, τι μπορούμε να πούμε για την ανθεκτικότητά του και κατ' επέκταση, για τις ιδιότητες δομής κοινοτήτων που διαθέτει; Υπάρχει κάποια κοινή ιδιότητα (πρότυπο) στα κοινωνικά γραφήματα που σχετίζεται με τη χρονική εξέλιξη των ιδιοτήτων αυτών;
Στα πλαίσια της παρούσας εργασίας προσπαθούμε να απαντήσουμε τα παραπάνω ερωτήματα, μελετώντας τις ιδιότητες επέκτασης κοινωνικών γραφημάτων μεγάλης κλίμακας. Αρχικά παρουσιάζουμε μια μετρική που έχει τη δυνατότητα να χαρακτηρίσει τόσο την ανθεκτικότητα όσο και τις ιδιότητες δομής κοινοτήτων ενός γραφήματος και περιγράφουμε πώς μπορούμε να την υπολογίσουμε αποδοτικά και αποτελεσματικά εκμεταλλευόμενοι ορισμένες ιδιαίτερες φασματικές ιδιότητες των πραγματικών γραφημάτων. Στη συνέχεια, εφαρμόζουμε τη μετρική αυτή σε ένα μεγάλο πλήθος στατικών κοινωνικών γραφημάτων μεγάλης κλίμακας και παρατηρούμε ορισμένες ενδιαφέρουσες ιδιότητες που σχετίζονται με την ανθεκτικότητά του και κατ΄ επέκταση με τις ιδιότητες δομής κοινοτήτων που εμφανίζουν. Μελετάμε πώς οι ιδιότητες αυτές αλλάζουν στον χρόνο, καθώς το γράφημα εξελίσσεται και παρατηρούμε ορισμένα ενδιαφέροντα πρότυπα. Τέλος, παρουσιάζουμε πώς μπορούμε να εντοπίσουμε ανωμαλίες σε γραφήματα που εξελίσσονται στο χρόνο, μελετώντας τις ιδιότητες που σχετίζονται με την ανθεκτικότητά του.
|
|---|
