Χρήστης:GeorgiosPapaeliou/πρόχειρο

Ορισμός Γράφου (Δικτύου): Ένας γράφος G είναι ο συνδυασμός ενός μη κενού συνόλου N κόμβων v και ενός (όχι απαραίτητα μη κενού) συνόλου M ακμών ε={vi,vj}

V = (v 1 , v 2 , ..., v n ), n ∈ N είναι το σύνολο των κόμβων (ή κορυφών).

E = ({v 2 , v 3 }, {v 3 , v 1 }, ..., {v m , v n }), 1 ≤ i ≤ M και 

1 ≤ i, j ≤ N είναι το σύνολο των ακμών (ή συνδέσμων).

Ένας γράφος(δίκτυο) είναι ένα σύνολο σημείων(ή κόμβων), που συμβολίζονται αυθαιρέτως και ενώνονται μεταξύ τους από ακμές. Ακμή είναι η κατευθυνόμενη διαδρομή που ενώνει έναν κόμβο(ν1) με έναν άλλον(ν2), όπου μπορεί να είναι ο ίδιος κόμβος(ν1=ν2). Ο συμβολισμός τους δεν είναι αυθαίρετος, οπότε κάθε ακμή κληρωνομεί το συμβολισμό της απ' τους κόμβους που συνδέει: μιά ακμή που ενώνει το ν1-->ν2 συμβολίζεται {ν1,ν2}, ενώ ενδέχεται να υπάρχει και η αντίθετή της {ν2,ν1}, χωρίς οι δύο να ταυτίζονται, μιας και όπως είπαμε, η ακμή είναι εν γένει μια κατευθυνόμενη διαδρομή. Σε μία ακμή, που ορίζει την σχέση μεταξύ δύο κόμβων, η σχέση αυτή μπορεί να ορίζεται ποικιλοτρόπως: με μια τιμή 0, όταν δεν υπάρχει συσχέτιση, 1 όταν υπάρχει πλήρης συσχέτιση ή κάποια εξίσωση που περιγράφει την μεταβλητή σχέση ως προς κάποιον παράγωντα(π.χ. τον χρόνο). Τέλος αναφορικά, όπως προκύπτει και απ' τον ορισμό, ακμές που δεν εννώνουν 2 κόμβους δεν ορίζονται, ενώ κόμβοι που δεν επικοινωνούν με άλλους λόγω απουσίας ακμών μεταξύ τους ορίζονται, γεγονός που επιτρέπει την ύπαρξη ασύνδετων κόμβων, αλλά όχι ακμών που δεν οδηγούν πουθενά.

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

ι) βαθμός γειτνείασης (ή βαθμός) ενός κόμβου είναι ένας ακέραιος αριθμός k, που είναι ίσος με το πλήθος των κόμβων που συνδέονται άμεσα με τον κόμβο αυτό. Ο βαθμός είναι απ' τα πιο βασικά μεγέθη, που χαρακτηρίζουν έναν κόμβο, καθώς ορίζει το πόσο συνδεδεμένος είναι στο υπόλοιπο δίκτυο. Επίσης αν σε ένα γράφο(δίκτυο) γνωρίζουμε τους βαθμούς k όλων των κόμβων -πράγμα εύκολο- μπορούμε υπολογίσουμε την κατανομή που έχει το μέγεθος k ως προς το πλήθος κόμβων N ή πιο απλά να παραστήσουμε γραφικά στο ίδιο διάγραμμα τι πλήθος κόμβων αντιστοιχεί σε κάθε k, που είναι μία συνάρτηση . Η συνάρτηση αυτή κανονικοποιημένη στο πλήθος των κόμβων N, έτσι ώστε το εμβαδόν κάτω απ' την καμπύλη κατανομής να είναι ίσο με 1, η μετατρέπεται σε κατανομή πιθανότητας η οποία μας πληροφορεί για το ποιά η πιθανότητα, ο κόμβος που διαλέξαμε στην τύχη, να έχει 8 γείτονες κόμβους(). Η κατανομή αυτής της πιθανότητας είναι γνώση βαρύνουσας σημασίας και εύκολο υπολογιστικά να αποκτηθεί, αποτελόντας ένα κοινό και ισχυρό μέτρο για την περιγραφή ενός γράφου. ιι) Συντελεστής ομαδοποίησης Ci (clustering coefficient) είναι ένα μέτρο που χαρακτηρίζει τον κάθε i γείτονα κόμβο ενός κεντρικού κόμβου με n γείτονες. Ο μέσος όρος <C> των Ci όλων των n γειτόνων είναι μέτρο, που χαρακτηρίζει ένα δίκτυο. Ο συντελεστής ομαδοποίησης είναι ο λόγος του πλήθους των υπαρκτών ακμών E προς το πλήθος των δυνατών ακμών (), που ενώνουν όλους τους n γείτονες ενός κεντρικού κόμβου.

, .

Η πιο απλή μονάδα πλήρους ομαδοποίησης είναι το τρίγωνο, δηλαδή τρείς κόμβοι που εννώνονται όλοι μεταξύ τους ακμές, οπότε ο μέσος συντελεστής ομαδοποίησης είναι το μέτρο τις πυκνότητας τριγώνων ή καλύτερα ο λόγος υπαρκτών προς δυνατών τριγώνων σε ένα δίκτυο. ιιι) Ενδιαφέρον παρουσιάζει το θεώρημα που συνδέει τον άθροισμα όλων των βαθμών με το πλήθος των ακμών E σε ένα δίκτυο n κόμβων. Ισχύει ότι:, δηλαδή σε ένα δίκτυο το άθροισμα όλων των βαθμών είναι διπλάσια του πλήθους των ακμών, πράγμα λογικό αφού στο άθροισμα όλων των βαθμών κάθε ακμή μετράται διπλά!

ι) Ως μονοπάτι(path) ορίζεται σύνολο συναπτών και μοναδικών ακμών, η αλληλουχία των οποίον συνήθως αναπαριστά μια διαδικασία, ενώ ως μήκος του μονοπατιού εκλαμβάνεται το πλήθος των ακμών που το αποτελούν. Το πιο απλό είδος μοοπατιού είναι η θηλεία(loop), ένα μονοπάτι με μόνο μία ακμή που αρχίζει και τελειώνει στον ίδιο κόμβο και συμβολίζει την ενάδραση ενός κόμβου με τον εαυτό του. Αν ένα μονοπάτι ξεκινά και τελειώνει στον ίδιο κόμβο, ενώ παρεμβάλονται και άλλοι, τότε ονομάζεται κύκλος και μπορεί να είναι κατευθυνόμενος ή όχι ανάλογα με το είδος των ακμών που τον αποτελούν. Οι σύνολο των κόμβων που ανήκουν σε έναν κατευθυνόμενο κύκλο, συνήθως απ' εικονίζει ένα υποσύστημα αντικειμένων που επιτυγχάνουν κάποια ρυθμιστική εργασία. Εγγύτατο μονοπάτι(shortest path) είναι το μονοπάτι με το μικρότερο μήκος, που συνδέει δύο κόμβους και ο υπολογισμός του προϋποθέτει τον υπολογισμό όλων των δυνατών μονοπατιών, που έχουν την ίδια ιδιότητα.Σε ένα δίκτυο μπορεί να υπολογιστεί και να ταξινομηθεί το σύνολο όλων των εγγύτατων μονοπατιών και αυτό με το μεγαλύτερο μήκος ονομάζεται διάμετρος. Η διάμετρος είναι ένας δείκτης του μεγέθους του δικτύου, αλλά μειονεκτεί λόγω μεγάλων υπολογιστικών απαιτήσεων σε πολλυπληθή δίκτυα. ιι) Συμπλέγματα(clusters) ή υποδίκτυα είναι τμήματα δικτύων, που αποτελούνται από κόμβους, που ομαδοποιούνται με βάση μια ξεχωριστή -ίσως και αρκετά αφηρημένη- ιδιότητα σε σχέση με το υπόλοιπο δίκτυο ή απλώς ξεχωρίζουν οπτικά απ' το υπόλοιπο δίκτυο. Ένα απ' τα βασικά είδη συμπλέγματος είναι οι κλίκες. Κλίκα(clique) είναι οποιοδήποτε δίκτυο(ή υποδίκτυο) όπου διαθέτει τον μέγιστο αριθμό ακμών, γεγονός που έχει ως αποτέλεσμα όλοι οι κόμβοι να συνδέονται μεταξύ τους. Άλλη μορφή συμπλέγματος είναι το EGO δίκτυο, όπου ένα τέτοιο αποτελείται από έναν κόμβο και όλους τους γειτονές ως προ αυτόν. Στην περίπτωση του EGO δικτύου ο μέσος συντελεστής ομαδοποίησης εκφράζει το πόσοι απ' τους γειτονες του κεντρικού είναι γείτονες μεταξύ τους, ένα μέτρο συνεκτικότητας του EGO δικτύου. Όταν η συνεκτικότητα είναι μέγιστη, που σημαίνει ότι όλοι οι γείτονες συνδέονται μεταξύ τους και το EGO δίκτυο ονομάζεται κλίκα. Παρ' ολ' αυτά μια κλίκα δεν είναι υποχρεωτικά EGO δίκτυο, μιας και κλίκα σημαίνει δίκτυο πλήρους συνεκτικότητας, που δεν σχετίζεται απαραίτητα με την κεντρική συμμετρία των EGO.

Μοντέλα Δικτύων: ι) Boolean ιι) Petri ιιι) ODEs & PDEs ιν) Bayesian (πιθανολογικά) Μοντέλα Δικτύων: Στην προσπάθεια να περιγραφούν διάφορες βιολογικές σχέσεις με την βοήθεια δικτύων, έχουν δημιουργηθεί πολλά διαφορετικά είδη δικτύων που μοτελοποιούν με διαφορετικό τρόπο, τόσο τους συντελεστές(κόμβους) όσο και της σχέσεις(ακμές) μεταξύ τους. Έτσι προκύπτουν τα εξής βασικά δίκτυα, με σειρά δημοτικότητας: i) δυαδικά δίκτυα ή Boolean Networks, ii) πιθανολογικά δίκτυα Bayesian Networks, iii) μεταβλητά δίκτυα συνήθων και μερικών διαφορικών εξισώσεων ODEs & PDEs Netwoks και τέλος iv) τα δίκτυα χωρικής μετάβασης (place-transition) ή δίκτυα Petri.

i) Τα Boolean Networks(δυαδικά δίκτυα), ίσως τα πιο βασικά, με μεγάλη ευκολία στην κατασκευή και την ερμηνεία, που βασίζεται στην λιτότητα της φύσης τους. Όλοι κόμβοι συμβολίζουν τους συντελεστές του δικτύου και η ακμές την ύπαρξη σχέσης μεταξύ δύο εξ αυτών. Φορμαλιστικά η ακμή παίρνει μόνο τις τιμές 0 και 1, έτσι ώστε για την τιμή 0 να εξαφανίζεται η ακμή, ενώ για την τιμή 1 απλώς υφίσταται. Παρ' ότι τα Boolean δίκτυα δεν μπορούν να αποδόσουν πλήρως την σχέσεις μεταξύ των κόμβων τους, σε πολλές περιπτώσεις που μια τέτοια λεπτομέρια δεδομένων δεν υπάρχει ή δεν ενδιαφέρει, αποτελούν μονόδρόμο. Κατασκευαστικό χαρακτηριστικό τους είναι το κατώφλι(threshold), μία τιμή που ενοίκει στο διάστημα (0,1) και όποια ακμή έχει τιμή πάνω απ' το κατώφλι επαναορίζεται ως 1, ενώ κάτω απ' αυτό ως 0. Με αυτό τον τρόπο κατορθώνουμε να ψηφιοποιήσουμε(0 1) τα πειραματικά αναλογικά δεδομένα (0-1) που διαθέτουμε. Η εκλογή του κατάλληλου κατωφλίου είναι μείζωνος σημασίας, μιας και η αλλαγή του μπορεί να επιρρεάσει ριζικά το εικόνα του δικτύου, οπότε και εγκολπώνει όλη την περιπλωκότητα των κατά τα άλλα απλών Boolean, με αποτέλεσμα απαιτούνται πολλές δοκιμές και διερεύνηση.{Που τα θέλουμε}

ii) Τα Bayesian Networks(πιθανολογικά δίκτυα) είναι όμοια με τα Boolean, με την διαφορά ότι οι ακμές παίρνουν τιμές στο συνεχές διάστημα [0,1]. Εδώ επίσης χρειάζεται η επιβολή κατωφλίου με τις ίδιες ιδιότητες και δυσκολίες, προκειμένου να εξαιρεθούν οι ακμές που έχουν πολύ μικρή πιθανότητα, κάτω του κατωφλίου, οπότε δεν μπορούν να ξεχωρίσουν απ' τον θόρυβο της μέτρησης των δεδομένων. {Που τα θέλουμε}

iii) Τα μεταβλητά δίκτυα συνήθων και μερικών διαφορικών εξισώσεων ODEs & PDEs Netwoks είναι δίκτυα που η ακμές δεν έχουν συγκεκριμένες τιμές, αλλά συγκεκριμένες εξισώσεις που διέπουν την σχέση δύο κόμβων. Οι εξισώσεις αυτές μπορούν να είναι είτε μονοπαραμετρικές, οπότε έχουμε Συνήθεις Διαφορικές Εξισώσεις(ODEs) ή πολύπαραμετρικές, οπότε έχουμε Διαφορικές Εξισώσεις μετά Μερικών Παραγώγων -Μερικές Διαφορικές Εξισώσεις- (PDEs). Παρ' ότι η πληροφορία που δίνουν είναι η πλουσιότερη δυνατή, παρουσιάζουν προβλήματα, κυρίως ως προς τις τεράστιες υπολογιστικές απαιτήσεις. Επίσης σε ένα βιολογικό σύστημα η απόκτηση μια τόσο ντετερμινιστικής γνώσης -όπως μια εξίσωση- είναι δύσκολη και αμφισβητήσιμη. {Που τα θέλουμε}

iv) Τα Petri Networks (δίκτυα χωρικής μετάβασης) είναι μία ειδική κατηγορία δικτύων, με πολλές ιδιομορφίες και δεν έχουν ευρεία χρήση. Αναφορικά, δεν αποτελούνται μόνο από κόμβους και ακμές, αλλά έχουν ένα επιπλέον συμβολισμό την μάρκα(token). Οι ακμές είναι υποχρεοτικά κατευθυνόμενες και δεν χαρακτηρίζονται ούτε από κάποια τιμη, ούτε από εξίσωση, παρά είναι επιφορτισμένες με την μετακίνηση των μαρκών(tokens) από κόμβο σε κόμβο. Οι κόμβοι με την σειρά τους έχουν κάποια χωρητικότητα σε μάρκες, ενώ χωρητικότητα μία μόνο μάρκας έχουν και οι ακμές. Είναι εν ολίγοις δίκτυα διακίνησης μαρκών(tokens). Δεν μπορούν να απεικονίσουν οποιοδήποτε σύστημα, αλλά μπορούν να απεικονίζουν πολύ καλά συστήματα, που τα παραπάνω μοντέλα αδυνατούν. {Που τα θέλουμε}