Σχεδιασμός και ανάλυση αλγορίθμων για τυχαία και εξελικτικά δίκτυα

Abstract

Let $V$ be a set of $i$ vertices and let ${\cal M}$ be a finite set of $m$ labels. An intersection graph is then constructed by assigning to each vertex $v \in V$ a subset $S_v$ of ${\cal M}$ and then connecting every pair of vertices that have common labels in their corresponding label sets. This thesis concerns the study of combinatorial properties, as well as the design and analysis of algorithms on two kinds of random intersection graphs models that arise from different choices of the distribution that we use to construct the sets $S_v$. In the first of these models, called \emph{Random Intersection Graphs Model} ${\cal G}_{n, m, p}$, each set of labels $S_v$ is constructed by choosing independently each label with probability $p$. In the second model, called \emph{Uniform Random Intersection Graphs Model} ${\cal G}_{n, m, \lambda}$, each label set $S_v$ is selected equiprobably (and independently for each vertex $v$) among all subsets of ${\cal M}$ of size $\lambda$. These models can be used to abstract situations that concern the efficient and secure communication in sensor networks, but can also be used to model the conflicts that occur in oblivious resource sharing in distributed settings. Moreover, random intersection graph models can be used to model social graphs, in which two entities are connected when they have a common feature. In the Random Intersection Graphs Model ${\cal G}_{n, m, p}$, we first study the existence and efficient construction of Hamilton cycles. More specifically, we give an upper bound for the probability $p$ that is needed for almost every random instance $G_{n, m, p}$ of the model to have a Hamilton cycle. We also present two polynomial time, randomized algorithms for constructing Hamilton cycles in a wide range of the parameters $m, p$. Moreover, we show that almost every random instance of the ${\cal G}_{n, m, p}$ model is an expander, even for $p$ very close to the connectivity threshold. Finally, we give close to optimal bounds (that hold with probability that goes to 1 for a wide range of the parameters of the model) for important quantities (like the mixing time and the cover time) concerning random walks on random instances of ${\cal G}_{n, m, p}$. In the Uniform Random Intersection Graphs Model ${\cal G}_{n, m, \lambda}$ we study the existence of Hamilton cycles for a ce rtain range of the parameters $m, \lambda$. Finally, by using the probabilistic method we compute the independence number of ${\cal G}_{n, m, \lambda}$.

Έστω $V$ ένα σύνολο $n$ κορυφών και έστω ${\cal M}$ ένα πεπερασμένα αριθμήσιμο σύνολο $m$ ετικετών. Ένα γράφημα ετικετών προκύπτει αν αντιστοιχήσουμε σε κάθε κορυφή $v \in V$ ένα υποσύνολο $S_v$ του ${\cal M}$ και στη συνέχεια ενώσουμε όποιες κορυφές έχουν κοινά στοιχεία στα αντίστοιχα σύνολα ετικετών τους. Η παρούσα διδακτορική διατριβή ασχολείται με την εξέταση συνδυαστικών ιδιοτήτων και το σχεδιασμό και ανάλυση αλγορίθμων που σχετίζονται με δυο μοντέλα τυχαίων γραφημάτων που προκύπτουν από την επιλογή των συνόλων $S_v$ με βάση συγκεκριμένες κατανομές. Το πρώτο από αυτά τα μοντέλα ονομάζεται \emph{Μοντέλο Τυχαίων Γραφημάτων Τομής Ετικετών} ${\cal G}_{n, m, p}$ (\textlatin{random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ διαμορφώνεται επιλέγοντας ανεξάρτητα κάθε ετικέτα με πιθανότητα $p$. Το δεύτερο μοντέλο ονομάζεται \emph{Ομοιόμορφο Μοντέλο Τυχαίων Γραφημάτων Τομής Ετικετών} ${\cal G}_{n, m, \lambda}$ (\textlatin{uniform random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ επιλέγεται (ανεξάρτητα για κάθε κορυφή) ισοπίθανα ανάμεσα σε όλα τα υποσύνολα του ${\cal M}$ μεγέθους $\lambda$. Τα μοντέλα αυτά μπορούν να χρησιμοποιηθούν για να μοντελοποιήσουν καταστάσεις που αφορούν θέματα ασφάλειας σε δίκτυα αισθητήρων, αλλά και για την αναπαράσταση των συγκρούσεων (\textlatin{conflicts}) που δημιουργούνται σε περιπτώσεις διαμοιρασμού πόρων. Ακόμα, μπορούν να χρησιμοποιηθούν για τη μοντελοποίηση κοινωνικών γραφημάτων (\textlatin{social graphs}) στα οποία δυο οντότητες συνδέονται όταν έχουν κάποιο κοινό χαρακτηριστικό. Στο Μοντέλο Τυχαίων Γραφημάτων Τομής Ετικετών ${\cal G}_{n, m, p}$ μελετάμε καταρχήν το πρόβλημα της ύπαρξης κύκλων \textlatin{Hamilton}. Συγκεκριμένα, αποδεικνύουμε ένα άνω φράγμα για την πιθανότητα επιλογής ετικετών $p$ έτσι ώστε κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ να περιέχει ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1 καθώς το $n$ τείνει στο άπειρο. Ακόμα, αναλύουμε δυο πιθανοτικούς αλγορίθμους που, για ορισμένες τιμές των παραμέτρων $m, p$ του μοντέλου, καταφέρνουν να κατασκευάσουν ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1, δηλαδή σχεδόν πάντα. Επίσης, δείχνουμε ότι σχεδόν κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ έχει καλή επεκτασιμότητα (\textlatin{expansion}), ακόμα και για $p$ πολύ κοντά στο κατώφλι συνεκτικότητας του μοντέλου. Στη συνέχεια, δίνουμε βέλτιστα άνω φράγματα (που ισχύουν με πιθανότητα που τείνει στο 1 σε ένα ευρύ πεδίο τιμών των παραμέτρων του μοντέλου) για σημαντικές ποσότητες που αφορούν τυχαίους περιπάτους σ ε στιγμιότυπα του ${\cal G}_{n, m, p}$ όπως ο χρόνος μίξης (\textlatin{mixing time}) και ο χρόνος κάλυψης (\textlatin{cover time}). Στο Ομοιόμορφο Μοντέλο Τυχαίων Γραφημάτων Τομής Ετικετών ${\cal G}_{n, m, \lambda}$ μελετάμε την ύπαρξη κύκλων \textlatin{Hamilton} σε ένα ορισμένο πεδίο τιμών των παραμέτρων $m, \lambda$ του μοντέλου. Τέλος, υπολογίζουμε με τη βοήθεια της Πιθανοτικής Μεθόδου το κατώφλι ύπαρξης ανεξάρτητων συνόλων κορυφών.