Τυχαίος γράφος

Στην θεωρία γράφων, ένας τυχαίος γράφος είναι ένας γράφος ο οποίος δημιουργείται από κάποια στοχαστική διαδικασία. Η θεωρία των τυχαίων γράφων βρίσκεται στη διασταύρωση μεταξύ της θεωρίας γράφων, της θεωρίας πιθανοτήτων και της μελέτης των ιδιοτήτων των τυπικών τυχαίων γράφων.

Μοντέλα τυχαίων γράφων

Ένας τυχαίος γράφος δημιουργείται ξεκινώντας με ένα σύνολο από $n$ κόμβους και προσθέτοντας ακμές μεταξύ τους τυχαία. Διαφορετικά μοντέλα τυχαίων γράφων παράγουν διαφορετικές κατανομές πιθανότητας στους γράφους.

Το μοντέλο που μελετάται πιο συχνά είναι αυτό που έχει προταθεί από τον Edgar Gilbert, που συμβολίζεται $G(n,p)$, και στο οποίο κάθε δυνατή ακμή εμφανίζεται ανεξάρτητα με πιθανότητα $p$. Ένα στενά συνδεδεμένο μοντέλο, είναι το μοντέλο Erdős-Rényi, που συμβολίζεται ως $G(n,M)$ και το οποίο δίνει ίση πιθανότητα για όλα τα γραφήματα με ακριβώς $M$ ακμές. Το τελευταίο μοντέλο μπορεί να θεωρηθεί ως ένα στιγμιότυπο σε μια συγκεκριμένη χρονική στιγμή ($M$) της τυχαίας διαδικασίας του γραφήματος ${\tilde {G}}_{n}$, η οποία είναι μια στοχαστική διαδικασία που ξεκινά με $n$ κορυφές και χωρίς ακμές και σε κάθε βήμα προσθέτει μια νέα ακμή επιλεγόμενη ομοιόμορφα από το σύνολο των ακμών που λείπουν.

Αν, αντίθετα, ξεκινάμε με ένα άπειρο σύνολο κορυφών, και πάλι ας κάθε δυνατή ακμή εμφανίζεται ανεξάρτητα με πιθανότητα $p$, τότε θα έχουμε ένα αντικείμενο $G$ το οποίο ονομάζεται άπειρο τυχαίο γράφημα. Εκτός από τις συνήθεις περιπτώσεις, όταν το $p$ είναι $0$ ή $1$, ένα τέτοιο αντικείμενο $G$ σχεδόν σίγουρα έχει την ακόλουθη ιδιότητα:

Για οποιαδήποτε $n+m$ στοιχεία $a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V$, υπάρχει μια κορυφή $c\in V$ που είναι γειτονική με καθεμία από τις άλλες $a_{1},\ldots ,a_{n}$ και δεν είναι γειτονική με καμία από τις άλλες $b_{1},\ldots ,b_{m}$.

Αποδεικνύεται ότι αν το σύνολο των κόμβων είναι μετρήσιμο τότε υπάρχει, μόνο ένας γράφος (με ισότητα (μέχρι ισομορφισμού) με αυτήν την ιδιότητα, γνωστός και ως γράφος Rado. Κατά συνέπεια, κάθε αριθμήσιμα άπειρος τυχαίος γράφος είναι σχεδόν σίγουρα ο γράφος Rado, ο οποίος για αυτόν τον λόγο μερικές φορές καλείται απλά τυχαίο τυχαίος γράφος. Ωστόσο, το ανάλογο αποτέλεσμα δεν ισχύει και για μη-αριθμήσιμους γράφυς, εκ των οποίων υπάρχουν πολλοί μη-ισομορφικοί γράφοι που ικανοποιούν την παραπάνω ιδιότητα.

Ένα άλλο μοντέλο, το οποίο γενικεύει το τυχαίο μοντέλο γράφου Gilbert, είναι το τυχαίο dot-product μοντέλο. Ένα τυχαίο dot-product γράφημα αντιστοιχεί με κάθε κορυφή ένα πραγματικό διάνυσμα. Η πιθανότητα της ακμής uv μεταξύ οποιωνδήποτε κορυφών u και v είναι κάποια λειτουργία του dot-product u•v των αντίστοιχων διανυσμάτων τους.

Η μήτρα πιθανότητας γράφου μοντελοποιεί τυχαίους γράφους μέσω των πιθανοτήτων των ακμών, οι οποίες αντιπροσωπεύουν την πιθανότητα $p_{i,j}$ ότι μια συγκεκριμένη ακμή $e_{i,j}$ υπάρχει για μια καθορισμένη χρονική περίοδο. Το μοντέλο αυτό είναι επεκτάσιμο σε κατευθυνόμενους, μη κατευθυνόμενους, σταθμισμένους, μη σταθμισμένους, στατικούς ή δυναμικούς γράφους.

Για $M\simeq pn$ τα δύο πιο ευρέως χρησιμοποιούμενα μοντέλα, $G(n,M)$ και $G(n,p)$, είναι σχεδόν εναλλάξιμα. Οι απλοί τυχαίοι γράφοι αποτελούν μια ειδική περίπτωση, με ιδιότητες που μπορεί να διαφέρουν από τα τυχαία γραφήματα σε γενικές γραμμές.

Ιδιότητες των τυχαίων γράφων

Η θεωρία των τυχαίων γράφων μελετά τυπικές ιδιότητες των τυχαίων γράφων, εκείνες δηλαδή που ισχύουν με μεγάλη πιθανότητα για γράφους που προέρχονται από μια συγκεκριμένη κατανομή. Για παράδειγμα, μπορούμε να ρωτήσουμε για μια δεδομένη τιμή του $n$ και $p$ ποια είναι η πιθανότητα ότι ο $G(n,p)$ είναι συνδεδεμένος. Μελετώντας αυτά τα ερωτήματα, οι ερευνητές συχνά επικεντρώνονται στην ασυμπτωτική συμπεριφορά των τυχαίων γράφων - το γεγονός ότι διάφορες πιθανότητες συγκλίνουν όσο το $n$ γίνεται πολύ μεγάλο. Η θεωρία διήθησης χαρακτηρίζει τον βαθμό σύνδεσης των τυχαίων γράφων, ειδικά των απείρως μεγάλων γράφων.

Η διήθηση έχει σχέση με την ευρωστία του γράφου (που ονομάζεται επίσης και δίκτυο). Λαμβάνουμε έναν τυχαίο γράφο με $n$ κόμβους και μέσο βαθμό $k$. Στη συνέχεια αφαιρούμε τυχαία ένα κλάσμα $1-p$ των κόμβων και αφήνουμε μόνο ένα κλάσμα $p$. Υπάρχει ένα κρίσιμο όριο διήθησης p_c=1/<k> κάτω από το οποίο το δίκτυο έχει κατακερματιστεί, ενώ πάνω από το όριο υπάρχει ένα γιγαντιαίο συνεκτικό στοιχείο. Τα τυχαία γραφήματα χρησιμοποιούνται ευρέως στην πιθανολογική μέθοδο, όπου κάποιος προσπαθεί να αποδείξει την ύπαρξη γραφημάτων με συγκεκριμένες ιδιότητες. Η ύπαρξη μιας ιδιότητας σε τυχαίο γράφο μπορεί συχνά να συνεπάγεται, μέσω της διάσημης Szemerédi regularity lemma, την ύπαρξη των ιδιοτήτων αυτών σχεδόν σε όλα τα γραφήματα.

Αλληλοεξαρτώμενα γραφήματα

Αλληλοεξαρτώμενα γραφήματα ή δίκτυα είναι ένα σύστημα συνδεδεμένων δικτύων όπου οι κόμβοι του ένα ή περισσότερα δίκτυα οι οποίοι εξαρτώνται από τους κόμβους σε άλλα δίκτυα. Η εξάρτηση αυτή ενισχύεται από τις εξελίξεις στη σύγχρονη τεχνολογία. Τέτοιες εξαρτήσεις μπορεί να οδηγήσουν σε διαδοχικές αποτυχίες (cascading failures) μεταξύ των δικτύων και μια σχετικά μικρή βλάβη μπορεί να οδηγήσει σε μια καταστροφική κατάρρευση του συστήματος. Τα blackouts είναι μια συναρπαστική επίδειξη του σημαντικού ρόλου που διαδραματίζουν οι εξαρτήσεις μεταξύ των δικτύων. Μια πρόσφατη μελέτη ανέπτυξε ένα πλαίσιο για τη μελέτη των διαδοχικών αποτυχιών σε έναν αλληλεξαρτώμενο σύστημα δικτύων.

Ιστορία

Τα τυχαία γραφήματα ορίστηκαν για πρώτη φορά από τους Paul Erdős και Alfréd Rényi το 1959 στην εργασία τους με τίτλο "On Random Graphs" και ανεξάρτητα από τον Gilbert στην εργασία του "Random Graphs".