Το χαρακτηριστικό μήκος διαδρομής (Characteristic Path Length - L) είναι μια θεμελιώδης μετρική της θεωρίας γραφημάτων που ποσοτικοποιεί πόσο «συμπαγές» είναι ένα δίκτυο. Αντιπροσωπεύει τον μέσο όρο των συντομότερων διαδρομών ανάμεσα σε όλα τα ζεύγη κόμβων και λειτουργεί ως δείκτης της ταχύτητας και της ανθεκτικότητας της πληροφορίας σε όλο το σύστημα.
Για ένα δίκτυο με n κόμβους, ορίζεται ως:
L = (1 / n(n-1)) × Σi≠j dij
όπου dij είναι η γεωδαιτική απόσταση (αριθμός ακμών στην συντομότερη διαδρομή) μεταξύ κόμβων i και j. Στα βαρύνωμενα δίκτυα, το dij αντικαθίσταται από το άθροισμα βαρών της ελάχιστης-κόστους διαδρομής.
Μικρό L σημαίνει γρήγορη εξάπλωση: ειδήσεις σε κοινωνικά δίκτυα, επιδημίες σε δίκτυα επαφών, ενημερώσεις routing σε διαδίκτυο. Το φαινόμενο «έξι βαθμών αποχωρισμού» αντικατοπτρίζει ακριβώς αυτό: παγκόσμιο L ≈ 6.
Δίκτυα με χαμηλό L (συνήθως small-world ή scale-free) διαθέτουν πολλαπλές εναλλακτικές διαδρομές. Η αποτυχία ενός κόμβου ή σύνδεσης σπάνια διακόπτει την επικοινωνία. Αντίθετα, δίκτυα με υψηλό L (π.χ. αλυσίδες, πλέγματα) είναι ευάλωτα: η απομάκρυνση ενός κρίσιμου κόμβου μπορεί να διασπάσει το δίκτυο.
Στα νευρωνικά δίκτυα και τα κατανεμημένα συστήματα, μικρό L επιτρέπει γρήγορη συγχρονισμό. Υψηλό L εισάγει καθυστερήσεις που μπορεί να προκαλέσουν race conditions ή ασταθειά.
Η επίτευξη χαμηλού L απαιτεί συνήθως «συντομεύσεις» (long-range connections). Στα μεταφορτικά δίκτυα, αυτό σημαίνει άμεσες συνδέσεις μεταξύ 메τρόπολων. Στο Διαδίκτυο, τα IXPs και τα backbone links λειτουργούν ως τέτοιες συντομεύσεις, μειώνοντας δραματικά το L.
| Τύπος Δικτύου | Τυπικό L | Επίδραση |
|---|---|---|
| Κοινωνικό (Facebook, Twitter) | 3.5 - 4.5 | Εξαιρετικά γρήγορη διάδοση, viral potential |
| Διαδίκτυο (AS level) | 3 - 4 | Αποδοτική δρομολόγηση παγκοσμίως |
| Μεταφορτικό (αεροπορικές γραμμές) | 2 - 3 (hub-and-spoke) | Γρήγορη κίνηση, αλλά ευάλωτο στα hubs |
| Νευρωνικό (C. elegans) | ~2.6 | Άμεσος συντονισμός κυτταρικών διεργασιών |
| Πλέγμα 2D (χωρικά δίκτυα) | ~√n | Αργή διάδοση, υψηλό κόστος επεκτάσεως |
Η μείωση του L δεν είναι πάντα το μοναδικό στόχος. Στε φαίνεται:
Η ιδανική αρχιτεκτονική εξαρτάται από την εφαρμογή: στα κέντρα δεδομένων ζητάμε ελάχιστο L (fat-tree, Clos topologies). Στα αισθητηριακά δίκτυα, η ενέργεια και η διάρκεια ζωής μπαταρίας μπορεί να προτιμώνται έναντι της ταχύτητας.
Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα διατηρούνται.