Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/155
Title: Σχεδιασμός και ανάλυση αλγορίθμων σε Τυχαία Γραφήματα Τομής
Other Titles: Design and analysis of algorithms on Random Intersection Graphs
Authors: Ραπτόπουλος, Χριστόφορος
Issue Date: 2007-05-16T11:16:47Z
Keywords: Τυχαίο Γράφημα Τομής
Πιθανοτικός αλγόριθμος
Ανεξάρτητο σύνολο κορυφών
Keywords (translated): Random Intersection Graph
Randomized algorithm
Independent set
Abstract: Στη διπλωματική αυτή εργασία ορίζουμε δυο νέα μοντέλα τυχαίων γραφημάτων τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα \\\\emph{τυχαίο} υποσύνολο ενός πεπερασμένου) σύμπαντος $M$ από $m$ στοιχεία και βάζοντας μια ακμή μεταξύ δυο κορυφών αν και μόνον εάν τα αντίστοιχα σύνολά τους έχουν μη κενή τομή. Συγκεκριμενοποιώντας την κατανομή που ακολουθεί το τυχαίο υποσύνολο που αντιστοιχείται σε κάθε κορυφή παίρνουμε διαφορετικά μοντέλα τυχαίων γραφημάτων τομής. Στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής κάθε στοιχείο $i$ του $M$ επιλέγεται ανεξάρτητα από κάθε κορυφή με πιθανότητα $p_i$. Το ομοιόμορφο μοντέλο τυχαίων γραφημάτων τομής ετικετών αποτελεί μια ειδική περίπτωση του γενικευμένου μοντέλου όπου η πιθανότητα επιλογής των στοιχείων του $M$ είναι ίση με $p$, δηλαδή ίδια για όλα τα στοιχεία του $M$. Όπως θα δούμε, για ορισμένες τιμές των παραμέτρων $m$ και $p$, το ομοιόμορφο μοντέλο είναι ισοδύναμο με το μοντέλο $G_{n, \\\\hat{p}}$, δηλαδή με το μοντέλο τυχαίων γραφημάτων στο οποίο κάθε πλευρά εμφανίζεται στοχαστικά ανεξάρτητα με πιθανότητα $\\\\hat{p}$. Τέλος, στο κανονικό μοντέλο τυχαίων γραφημάτων τομής ετικετών το υποσύνολο του $M$ που αντιστοιχείται σε κάθε κορυφή έχει σταθερό αριθμό στοιχείων. Λόγω της στοχαστικής εξάρτησης που υποννοείται για την ύπαρξη πλευρών, τα γραφήματα αυτά θεωρούνται αρκετά ρεαλιστικά μοντέλα (σε σχέση με τα κλασσικά τυχαία γραφήματα) σε πολλές πρακτικές εφαρμογές, ιδιαίτερα σε αλγοριθμικά θέματα δικτύων. Στην εργασία αυτή αρχικά παρουσιάζουμε μερικά χαρακτηριστικά αποτελέσματα από τη σχετική βιβλιογραφία για τα μοντέλα αυτά. Ακόμα, μελετάμε, για πρώτη φορά στη βιβλιογραφία, την ύπαρξη ανεξάρτητων συνόλων κορυφών μεγέθους $k$ στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής ετικετών, υπολογίζοντας τη μέση τιμή και τη διασπορά του αριθμού τους. Επίσης, προτείνουμε και αναλύουμε τρείς πιθανοτικούς αλγόριθμους που τρέχουν σε μικρό πολυωνυμικό χρόνο (ως προς τον αριθμό των κορυφών και τον αριθμό των στοιχείων του $M$) για την εύρεση αρκετά μεγάλων συνόλων ανεξάρτητων κορυφών.
Abstract (translated): In this Master thesis we define and analyse two new models of random intersection graphs. A random intersection graph is produced by assigning to each vertex a random subset of a (finite) universe $M$ of $m$ elements and by drawing an edge between two vertices if and only if their corresponding subsets have some elements in common. By specifying the distribution of the subsets assigned to each vertex, we get various models of random intersection graphs. In the generalized random intersection graphs model each element $i$ in $M$ is chosen independently with probability $p_i$. The uniform random intersection graphs model is a special case of the generalized model where the probability of selecting an element of $M$ is $p$, i.e. the same for every element. As we will see, for some range of values of the parameters $m$ and $p$, the uniform model is equivalent in some sense with the model $G_{n, \\\\hat{p}}$, i.e. the random graphs model in which each edge appears independently with probability $\\\\hat{p}$. Finally, in the regular random intersection graphs model, the subset of $M$ assigned to each vertex has a fixed number of elements. Due to the dependence implied in the appearance of edges, these models are considered to be more realistic (than classic random graphs) in many applications. This thesis begins by presenting several important results concearning these models. Also, we study for the first time the existence of independent sets of size $k$ in the generalized random intersection graphs model, and we give exact formulae for the mean and variance of their number. Additionally, we propose three randomized algorithms, that run in small polynomial time (with respect to the number of vertices and the number of elements of $M$), for finding large independent sets of vertices.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
306.pdf483.24 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.