Μονάδα:
Κατεύθυνση Στατιστική και Επιχειρησιακή ΈρευναΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2020-01-21
Συγγραφέας:
Κατωγιάννη Ιωάννα
Στοιχεία επιβλεπόντων καθηγητών:
Σ. Τρέβεζας
Λέκτορας
Τμήμα Μαθηματικών
Ε.Κ.Π.Α.
Πρωτότυπος Τίτλος:
Προσομοίωση τυχαίων γραφημάτων με περιορισμούς στην ακολουθία βαθμών
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Προσομοίωση τυχαίων γραφημάτων με περιορισμούς στην ακολουθία βαθμών
Περίληψη:
Ένα σημαντικό πρόβλημα στη θεωρία των γράφων είναι η δημιουργία γράφων με μια δοθείσα κατανομή βαθμών,το οποίο είναι ισοδύναμο με τη δημιουργία τυχαίων γράφων,οι οποίοι έχουν ένα συγκεκριμένο αριθμό ακμών υπό τον περιορισμό των βαθμών.Τα κίνητρα για τη μελέτη είναι: α) να μπορούμε να έχουμε ετερογενείς ακμές,το οποίο δεν είναι δυνατό στο κλασικό μοντέλο των Erdos-Renyi,καθώς αυτό επιτρέπει καλύτερη προσαρμογή σε πραγματικές εφαρμογές και β) να σχεδιάσουμε αποτελεσματικά ένα τυχαίο γράφο με αυτούς τους περιορισμούς.Προηγούμενοι αλγόριθμοι συχνά βρίσκονται σε αδιέξοδο ή σε ατέρμονο βρόχο 'η παράγουν πολλαπλές ακμές.Αυτό επιτυγχάνεται με τον αλγόριθμο των Blitzstein & Diaconis,ο οποίος βασίζεται στην ιδέα της ακολουθιακής δειγματοληψίας σπουδαιότητας.Για αυτό χρησιμοποιείται μια επέκταση του χαρακτηρισμού Erdos-Gallai και μια κατάλληλα επιλεγμένη σειρά επιλογής ακμών.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Τυχαία γραφήματα
Αρ. σελίδων ευρετηρίου:
1
Αρ. βιβλιογραφικών αναφορών:
23
Αρχείο:
Δεν επιτρέπεται η πρόσβαση στο αρχείο. H πρόσβαση επιτρέπεται μόνο εντός του δικτύου του ΕΚΠΑ.
text.pdf
761 KB
Δεν επιτρέπεται η πρόσβαση στο αρχείο. H πρόσβαση επιτρέπεται μόνο εντός του δικτύου του ΕΚΠΑ.
