Zufallsgraphen sind Graphen, die durch einen zufälligen Prozess erzeugt werden. Ein im Zusammenhang mit Zufallsgraphen häufig auftretendes Phänomen ist, dass sich die typischen Eigenschaften eines Graphen durch Hinzufügen einer relativ kleinen Anzahl von zufälligen Kanten radikal verändern. Wir betrachten den Zufallsgraphen G(n,p), der n Knoten enthält und in dem zwei Knoten unabhängig und mit Wahrscheinlichkeit p durch eine Kante verbunden sind. Erdös und Rényi zeigten, dass ein Graph für p = c/n und c < 1 mit hoher Wahrscheinlichkeit aus Komponenten mit O(log n) Knoten besteht. Für p = c/n und c > 1 enthält G(n,p) mit hoher Wahrscheinlichkeit genau eine Komponente mit Theta(n) Knoten, welche viel größer als alle anderen Komponenten ist. Dieser Punkt in der Entwicklung des Graphen, an dem sich die Komponentenstruktur durch eine kleine Erhöhung der Anzahl von Kanten stark verändert, wird Phasenübergang genannt. Wenn p = (1+epsilon)/n, wobei epsilon eine Funktion von n ist, die gegen 0 geht, sind wir in der kritischen Phase, welche eine der interessantesten Phasen der Entwicklung des Zufallsgraphen ist. In dieser Arbeit betrachten wir drei verschiedene Modelle von Zufallsgraphen. In Kapitel 4 studieren wir den Minimalgrad-Graphenprozess. In diesem Prozess werden sukzessive Kanten vw hinzugefügt, wobei v ein zuällig ausgewählter Knoten von minimalem Grad ist. Wir beweisen, dass es in diesem Graphenprozess einen Phasenübergang, und wie im G(n,p) einen Doppelsprung, gibt. Die zwei anderen Modelle sind Zufallsgraphen mit einer vorgeschriebenen Gradfolge und zufällige gerichtete Graphen. Für diese Modelle wurde bereits in den Arbeiten von Molloy und Reed (1995), Karp (1990) und Luczak (1990) gezeigt, dass es einen Phasenübergang bezüglich der Komponentenstruktur gibt. In dieser Arbeit untersuchen wir in Kapitel 5 und 6 die kritische Phase dieser Prozesse genauer, und zeigen, dass sich diese Modelle ähnlich zum G(n,p) verhalten. / Random graphs are graphs which are created by a random process. A common phenomenon in random graphs is that the typical properties of a graph change radically by the addition of a relatively small number of random edges. This phenomenon was first investigated in the seminal papers of Erdös and Rényi. We consider the graph G(n,p) which contains n vertices, and where any two vertices are connected by an edge independently with probability p. Erdös and Rényi showed that if p = c/n$ and c < 1, then with high probability G(n,p) consists of components with O(log n) vertices. If p = c/n$ and c>1, then with high probability G(n,p) contains exactly one component, called the giant component, with Theta(n) vertices, which is much larger than all other components. The point at which the giant component is formed is called the phase transition. If we let $p = (1+epsilon)/n$, where epsilon is a function of n tending to 0, we are in the critical phase of the random graph, which is one of the most interesting phases in the evolution of the random graph. In this case the structure depends on how fast epsilon tends to 0. In this dissertation we consider three different random graph models. In Chapter 4 we consider the so-called minimum degree graph process. In this process edges vw are added successively, where v is a randomly chosen vertex with minimum degree. We prove that a phase transition occurs in this graph process as well, and also that it undergoes a double jump, similar to G(n,p). The two other models we will consider, are random graphs with a given degree sequence and random directed graphs. In these models the point of the phase transition has already been found, by Molloy and Reed (1995), Karp (1990) and Luczak (1990). In Chapter 5 and 6 we investigate the critical phase of these processes, and show that their behaviour resembles G(n,p).

This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”. In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees. In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees. In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution. In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.

We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.

Η παρούσα διπλωματική εργασία βρίσκεται στον ευρύτερο χώρο της μαθηματικής στατιστικής θεωρίας των γραφημάτων. Κύριος στόχος μας, όπως αναφέρει και ο τίτλος, είναι η μοντελοποίηση γραφημάτων, με απώτερο σκοπό την προσαρμογή, προσομοίωση και διάγνωση αυτών μέσω μοντέλων εκθετικών τυχαίων γραφημάτων. Το πρώτο κεφάλαιο δίνει μια συνοπτική παρουσίαση της διατύπωσης του προβλήματος και της θεωρίας των μοντέλων των εκθετικών τυχαίων γραφημάτων. Η βασική ιδέα είναι να θεωρήσουμε ως τυχαίες μεταβλητές τους δυνατούς δεσμούς μεταξύ των κόμβων ενός δοθέντος γραφήματος. Η γενική μορφή ενός μοντέλου εκθετικά τυχαίου γραφήματος καθορίζεται από κάποιες υποθέσεις σχετικές με τις εξαρτήσεις μεταξύ αυτών των τυχαίων μεταβλητών. Παρουσιάζουμε κάποιες διαφορετικές υποθέσεις εξάρτησης και τα αντίστοιχα μοντέλα, όπως τα γραφημάτα Bernoulli, τα δυαδικώς - ανεξάρτητα και τα τυχαία γραφήματα Markov. Επίσης, εξετάζουμε την ενσωμάτωση των χαρακτηριστικών, που μπορούν να έχουν οι κόμβοι, σε μοντέλα κοινωνικής επιλογής, δηλαδή, σε περιπτώσεις που οι συνδέσεις του γραφήματος μπορούν να προβλέψουν τα χαρακτηριστικά των κόμβων. Συνοψίζουμε κάποιες καινούργιες υποθέσεις εξάρτησης, που είναι πολυπλοκότερες των πρώτων τέτοιων υποθέσεων της σχετικής βιβλιογραφίας. Συζητούμε τις διαδικασίες της στατιστικής εκτίμησης, συμπεριλαμβανομένων των νέων μεθόδων για την εκτίμηση της μέγιστης πιθανοφάνειας Monte Carlo. Τέλος, παρουσιάζουμε τις νέες προδιαγραφές για μοντέλα εκθετικών τυχαίων γραφημάτων, που έχουν προτείνει οι Snijders et al., οι οποίες βελτιώνουν σημαντικά τα αποτελέσματα της προσαρμογής εμπειρικών δεδομένων για εκθετικά μοντέλα ομοιογενών τυχαίων γραφημάτων Markov. Επιπλέον, οι νέες αυτές προδιαγραφές μας βοηθούν να αποφύγουμε το πρόβλημα του σχεδόν-εκφυλισμού, που συχνά παρεμβάλλεται στη διαδικασία της προσαρμογής μοντέλων εκθετικών τυχαίων γραφημάτων Markov, ιδιαίτερα όταν αυτά προέρχονται από εμπειρικά δεδομένα, που έχουν υψηλό βαθμό μεταβατικότητας. Η μελέτη μιας τέτοιας νέας στατιστικής με υψηλότερης τάξης μεταβατικότητα επιτρέπει την εκτίμηση των παραμέτρων των μοντέλων των εκθετικών γραφημάτων σε πολλές (αλλά όχι όλες) περιπτώσεις, στις οποίες διαφορετικά θα ήταν αδύνατο να εκτιμηθούν οι παράμετροι των μοντέλων των ομοιογενών γραφημάτων Markov. Στο δεύτερο, τρίτο και τέταρτο κεφάλαιο της εργασίας εφαρμόζουμε τις παραπάνω μεθόδους, αντιστοίχως, για τρείς αναλύσεις εμπειρικών δεδομένων: το δίκτυο Florentine, το δίκτυο Faux Magnolia High και τα δίκτυα IPRED και SWPAT. Σε αυτά τα κεφάλαια, παρουσιάζουμε τις διαδικασίες της προσαρμογής, προσομοίωσης και διάγνωσης με παράθεση των αντίστοιχων εντολών, χρησιμοποιώντας τα πακέτα statnet - ermg και sna, τα οποία δουλεύουν στο περιβάλλον του πακέτου ελεύθερου λογισμικού R. Τέλος, στο παράρτημα της εργασίας δίνουμε μια σύντομη εισαγωγή στο περιβάλλον R και σε κάποιες γενικές εντολές αυτού. / This specific project has to do with mathematical statistical graph theory. Our main target is to fit, simulate and diagnose models through exponential random graph models. In the first chapter we give a short presentation of the problem and the theory of exponential random graph models. The main idea is to consider each tie of a given network (graph) as a random variable. The general form of an exponential random graph model is defined from some relative assumptions that have to do with the dependence between those random variables. We present some different dependence assumptions and the corresponding models, such as Bernoulli graphs, dyadic-independent and Markov random graphs. We also examine the incorporation of the characteristics that a node may have in social networks. We also discuss the process of statistical estimation, including three new methods for the estimation of Monte Carlo maximum likelihood. Finally, we present new specifications for exponential random graph models, which Snijders et al. have proposed. These new specifications allow us to avoid the problem of degeneration. In the second, third and fourth chapter we apply the above methods in order to analyze Florentine network data, Faux Magnolia High data and IPred And Swpat data. In those chapters, we present the procedures of fit, simulate and diagnose exponential random graph models displaying the corresponding commands of statnet-ergm and sna packages that work in R. Finally we give a short introduction to R and to some relative commands.

Le processus de contact est l'un des systèmes de particules en interaction les plus étudiés. Il peut s'interpréter comme un modèlepour la propagation d'un virus dans une population ou sur un réseau. L'objectif de cette thèse est d'étudier la relation entre la structure locale du réseau et le comportement global du processus sur le réseau tout entier.Le cadre typique dans lequel on se place est celui d’une suite de graphes aléatoires $(G_n)$ convergeant localement vers un graphe limite $G$.On étudie alors le comportement asymptotique du temps d’extinction $tau_n$ du processussur $G_n$; lorsqu’initialement tous les individus sont infectés. Nous montrons sur plusieurs exemples qu’il existe unetransition de phase lorsque $lambda$ - le taux d'infection du processus - traverse une valeur critique $ lambda_c (G)$, qui ne dépend que de $G$.Plus précisément, pour certains modèles de graphes aléatoires comme le modèle de configuration, le graphe d'attachement préférentiel, le graphe géométrique aléatoire, le graphe inhomogène, nous montrons que $ tau_n $ est d'ordre soit logarithmique soit exponentiel; selon que $ lambda$ est soit inférieur ou supérieur à $lambda_c (G) $.De plus, dans certains cas, nous montrons des résultats de métastablité: en régime sur-critique, $ tau_n $ divisé par son espérance converge en loi vers une variable aléatoire exponentielle de moyenne $1$, et la densité des sites infectés reste stable (et non nulle) sur une période de temps d’ordre typiquement $tau_n$. / The contact process is one of the most studied interacting particle systems and is also often interpreted as a model for the spread of a virus in a population or a network. The aim of this thesis is to study the relationship of the local structure of the network and the global behavior of the contact process (the virus) on the whole network. Let $(G_n)$ be a sequence of random graphs converging weakly to a graph $G$. Then we study $tau_n$, the extinction time of the contact process on $G_n$ starting from full occupancy. We prove in some examples that there is a phase transition of $tau_n$ when $lambda$ - the infection rate of the contact process crosses a critical value $lambda_c(G)$ depending only on $G$. More precisely, for some models of random graphs, such as the configuration model, preferential attachment graph, random geometric graph, inhomogeneous graph, we show that $tau_n$ is of logarithmic (resp. exponential) order when $lambda < lambda_c(G)$ (resp. $lambda < lambda_c(G)$). Moreover, in some cases we also prove metastable results: in the super-critical regime, $tau_n$ divided by its expectation converges in law to an exponential random variable with mean $1$, and the density of the infected sites is stable for a long time.

Une donnée peut avoir diverses formes et peut provenir d'un large panel d'applications. Habituellement, une donnée possède beaucoup de bruit et peut être soumise aux effets du hasard. Les récents progrès en apprentissage automatique ont relancé les recherches théoriques sur les limites des différentes méthodes probabilistes de traitement du signal. Dans cette thèse, nous nous intéressons aux questions suivantes : quelle est la meilleure performance possible atteignable ? Et comment peut-elle être atteinte, i.e., quelle est la stratégie algorithmique optimale ?La réponse dépend de la forme des données. Les sujets traités dans cette thèse peuvent tous être représentés par des modèles graphiques. Les propriétés des données déterminent la structure intrinsèque du modèle graphique correspondant. Les structures considérées ici sont soit éparses, soit denses. Les questions précédentes peuvent être étudiées dans un cadre probabiliste, qui permet d'apporter des réponses typiques. Un tel cadre est naturel en physique statistique et crée une analogie formelle avec la physique des systèmes désordonnés. En retour, cela permet l'utilisation d'outils spécifiques à ce domaine et de résoudre des problèmes de satisfaction de contraintes et d'inférence statistique. La problématique de performance optimale est directement reliée à la structure des extrema de la fonction d'énergie libre macroscopique, tandis que les aspects algorithmiques proviennent eux de la minimisation de la fonction d'énergie libre microscopique (c'est-à-dire, dans la forme de Bethe).Cette thèse est divisée en quatre parties. Premièrement, nous aborderons par une approche de physique statistique le problème de la coloration de graphes aléatoires et mettrons en évidence un certain nombre de caractéristiques. Dans un second temps, nous calculerons une nouvelle limite supérieure de la taille de l'ensemble contagieux. Troisièmement, nous calculerons le diagramme de phase du modèle de Dawid et Skene dans la région dense en modélisant le problème par une factorisation matricielle de petit rang. Enfin, nous calculerons l'erreur optimale de Bayes pour une classe restreinte de l'estimation matricielle de rang élevé. / Datasets come in a variety of forms and from a broad range of different applications. Typically, the observed data is noisy or in some other way subject to randomness. The recent developments in machine learning have revived the need for exact theoretical limits of probabilistic methods that recover information from noisy data. In this thesis we are concerned with the following two questions: what is the asymptotically best achievable performance? And how can this performance be achieved, i.e., what is the optimal algorithmic strategy? The answer depends on the properties of the data. The problems in this thesis can all be represented as probabilistic graphical models. The generative process of the data determines the structure of the underlying graphical model. The structures considered here are either sparse random graphs or dense (fully connected) models. The above questions can be studied in a probabilistic framework, which leads to an average (or typical) case answer. Such a probabilistic formulation is natural to statistical physics and leads to a formal analogy with problems in disordered systems. In turn, this permits to harvest the methods developed in the study of disordered systems, to attack constraint satisfaction and statistical inference problems. The formal analogy can be exploited as follows. The optimal performance analysis is directly related to the structure of the extrema of the macroscopic free energy. The algorithmic aspects follow from the minimization of the microscopic free energy (that is, the Bethe free energy in this work) which is closely related to message passing algorithms. This thesis is divided into four contributions. First, a statistical physics investigation of the circular coloring problem is carried out that reveals several distinct features. Second, new rigorous upper bounds on the size of minimal contagious sets in random graphs, with bounded maximum degree, are obtained. Third, the phase diagram of the dense Dawid-Skene model is derived by mapping the problem onto low-rank matrix factorization. The associated approximate message passing algorithm is evaluated on real-world data. Finally, the Bayes optimal denoising mean square error is derived for a restricted class of extensive rank matrix estimation problems.

Submitted by (ana.araujo@ufrpe.br) on 2016-05-25T13:54:35Z No. of bitstreams: 1 Aranildo Rodrigues de Lima Junior.pdf: 636074 bytes, checksum: 5f3ad98d36eb71272e1ee3c218fe2afb (MD5) / Made available in DSpace on 2016-05-25T13:54:35Z (GMT). No. of bitstreams: 1 Aranildo Rodrigues de Lima Junior.pdf: 636074 bytes, checksum: 5f3ad98d36eb71272e1ee3c218fe2afb (MD5) Previous issue date: 2011-02-11 / In the majority-vote model with noise, defined in a network, a given site (spin) assumes the posite state (sign) of the majority of its neighboring spins with probability q and it takes the same state with probability (1−q). The noise parameter q is homogeneous for all sites. In this work, we investigate a more general and realistic version of the majority-vote model, in which a given site i has its own noise parameter qi satisfying a mixed probability distribution. In this way, there is a heterogeneous distribution of noise among the sites in the network. We consider the case of a distribution defined by P(qi) = bd (qi)+(1−b)d (qi−q), where b is the fraction of sites without noise and q is taken from a Gaussian distribution. We perform Monte Carlo simulations on random graphs of different sizes and three average connectivity, for several values of the parameter b. We calculate the magnetization, the susceptibility and the Binder’s fourth-order cumulant as functions of q. We note that the system presents an order-disorder phase transition at a critical value of the parameter noise qc, which is an increasing function of the fraction of sites without noise. We use finite-size scaling theory to construct the phase diagram of the model and estimate the critical exponents b /n , g / nd 1/n . These exponents satisfy the hyperscaling relation with effective dimensionality equals to unity, for all values of average connectivity and b. Finally we conclude that, the majority-vote model with mixed distribution of noise on random graphs belongs to a different universality class from the model with homogeneous distribution of noise. / No modelo do voto da maioria com ruído, definido em uma rede, um dado sítio (spin) toma o estado contrário (sinal) à maioria dos seus vizinhos com probabilidade q e concorda com o estado da maioria dos seus vizinhos com probabilidade (1−q), onde q é o parâmetro de ruído homogêneo para todos os sítios. Nessa dissertação investigamos o modelo do voto da maioria com distribuição mista de ruídos, no qual cada sítio tem o parâmetro q satisfazendo uma distribuição mista de probabilidade de forma que há uma distribuição heterogênea com relação aos ruídos dos sítios da rede. Consideramos o caso de uma distribuição dada por P(qi) = bd (qi)+(1−b)d (qi −q), onde b é a fração de sítios com ausência de ruído e q é dado por uma distribuição Gaussiana. Realizamos simulações de Monte Carlo para diversos valores do parâmetro b, em grafos aleatórios de diferentes tamanhos N e três valores da conectividade média. Calculamos a magnetização, a susceptibilidade e o cumulante de Binder como funções de q. Notamos que o sistema apresenta uma transição de fase do tipo ordem-desordem em um valor crítico do parâmetro de ruído qc, o qual é uma função crescente da fração de sítios com ausência de ruído. A partir da teoria de escala de tamanho finito construímos o diagrama de fases do modelo no plano qc versus b e estimamos os expoentes críticos b /n , g /n e 1/n . Esses expoentes satisfazem a relação de hiper-escala com a dimensionalidade efetiva do sistema D = 1 para todos os valores da conectividade média e b. Por fim concluímos que o modelo do voto da maioria com distribuição mista de ruído, pertence a uma classe de universalidade diferente do modelo com distribuição homogênea de ruído em grafos aleatórios.

Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit. / We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way

Peer to peer networks are becoming increasingly popular among Internet users as the downloading peers share the storage and upload bandwidth load of the system. This makes it possible for a large number of users to share a data file available at a server without the server upload bandwidth becoming a bottleneck. The P2P technology is being widely used not only for file sharing but also for video on demand, live streaming and IPTV. The delay deadlines are more stringent in live streaming and IPTV than those in file sharing as the traffic is real time. The performance perceived by a user depends upon whether the video stream is being downloaded at the streaming rate. Coolstreaming is the first large scale P2P IPTV system. We model the multi-channel Coolstreaming system via an open queueing network. The peer dynamics at a channel is modelled by a closed queueing network working at a faster rate. We compute the expected number of substreams in the overlay of New Coolstreaming which are not being received at the proper rate. The computation of the Markov chain with a very large state space is handled using the two time scale decomposition. Further we characterize the end to end delay encountered by a video stream originating from the server and received at a user of New Coolstreaming. Three factors contribute towards the delay. The first factor is the mean path length in terms of overlay hops of the partnership graph. The second factor is the mean number of routers between any two overlay peers in the network layer and the third factor is the queueing delay at a router in the Internet. The mean shortest path length in terms of overlay peers in the New Coolstreaming graph is shown to be O(logn)where nis the number of peers in the overlay. This is done by modelling the overlay by a random graph. The mean shortest path in terms of routers in the Internet’s router level topology is seen to be at most O(logNI)where NIis the number of routers in the Internet. We also discuss a method by which we can get the mean delay at a router in the Internet. Thus, the mean end to end delay in New Coolstreaming is shown to be upper bounded by O(lognlogNIE[W])where E[W]is the mean delay at a router in the Internet.

This thesis describes design and implementation of an approach to the mobile robot localization. The proposed method is based purely on images taken by a monocular camera. The described solution handles localization as an association problem and, therefore, falls in the category of topological localization methods. The method is based on a generative probabilistic model of the environment appearance. The proposed solution is capable to eliminate some of the difficulties which are common in traditional localization approaches.