Κατεύθυνση Στατιστική και Επιχειρησιακή Έρευνα
Library of the School of Science

2020-01-21

2020

Katogianni Ioanna

Σ. Τρέβεζας
Λέκτορας
Τμήμα Μαθηματικών
Ε.Κ.Π.Α.

Προσομοίωση τυχαίων γραφημάτων με περιορισμούς στην ακολουθία βαθμών

Greek

Προσομοίωση τυχαίων γραφημάτων με περιορισμούς στην ακολουθία βαθμών

Ένα σημαντικό πρόβλημα στη θεωρία των γράφων είναι η δημιουργία γράφων με μια δοθείσα κατανομή βαθμών,το οποίο είναι ισοδύναμο με τη δημιουργία τυχαίων γράφων,οι οποίοι έχουν ένα συγκεκριμένο αριθμό ακμών υπό τον περιορισμό των βαθμών.Τα κίνητρα για τη μελέτη είναι: α) να μπορούμε να έχουμε ετερογενείς ακμές,το οποίο δεν είναι δυνατό στο κλασικό μοντέλο των Erdos-Renyi,καθώς αυτό επιτρέπει καλύτερη προσαρμογή σε πραγματικές εφαρμογές και β) να σχεδιάσουμε αποτελεσματικά ένα τυχαίο γράφο με αυτούς τους περιορισμούς.Προηγούμενοι αλγόριθμοι συχνά βρίσκονται σε αδιέξοδο ή σε ατέρμονο βρόχο 'η παράγουν πολλαπλές ακμές.Αυτό επιτυγχάνεται με τον αλγόριθμο των Blitzstein & Diaconis,ο οποίος βασίζεται στην ιδέα της ακολουθιακής δειγματοληψίας σπουδαιότητας.Για αυτό χρησιμοποιείται μια επέκταση του χαρακτηρισμού Erdos-Gallai και μια κατάλληλα επιλεγμένη σειρά επιλογής ακμών.

Science

Random graphs

Yes

1

No

23

66

File access is restricted only to the intranet of UoA.

https://pergamos.lib.uoa.gr/uoa/dl/object/2895465