The foreseen massive deployment of the internet of things (IoT) is expected to suffer from high security risks. This mainly results from the difficulty to monitor and cure the IoT devices in such large-scale deployment. In this thesis, we propose a spatial random deployment of special nodes (firewalls) which can detect and cure infected nodes within certain radius. An important concern is to add sufficient number of firewalls to make an epidemics finite and, hence, prevent malware outbreak over the whole network. The problem will be analyzed using percolation theory. Namely, we derive an upperbound for the critical intensity of spatial firewalls which guarantees prevention of large-scale network epidemics, regardless of the intensity of regular nodes. Using tools from percolation theory, we analyze the proposed solution and show the conditions required to ensure its efficiency.

This essay will present the vertex pursuit game of cops and robbers and the problem that made it famous: Meinyel's conjecture. The conjecture stood unproved from 1987 until 2010 when Łuczak and Prałat proved the conjecture with their "Zig-Zag Theorem", which is also covered in the essay.

No description available.

Over the last twenty years, as biological, technological, and social net- works have risen in prominence and importance, the study of complex networks has attracted researchers from a wide range of fields. As a result, there is a large and diverse body of literature concerning the properties and development of models for complex networks. However, many of the models that have been previously developed, although quite successful at capturing many observed properties of complex networks, have failed to capture the fundamental semantics of the networks. In this thesis, we propose a robust and general model for complex networks that incorporates at a fundamental level semantic information. We show that for a large range of average degrees and with a suitable choice of parameters, this model exhibits the three hallmark properties of complex networks: small diameter, clustering, and skewed degree distribution. Additionally, we provide a structural interpretation of assortativity and apply this strucutral assortativity to the random dot product graph model. We also extend the results of Chung, Lu, and Vu on the spectral gap of the expected degree sequence model to a general class of random graph models with independent edges. We apply this result to the recently developed Stochastic Kronecker graph model of Leskovec, Chakrabarti, Kleinberg, and Faloutsos.

The phenomenon of scale dependent spectral dimension has attracted special interest in the quantum gravity community over the last eight years. It was first observed in computer simulations of the causal dynamical triangulation (CDT) approach to quantum gravity and refers to the reduction of the spectral dimension from 4 at classical scales to 2 at short distances. Thereafter several authors confirmed a similar result from different approaches to quantum gravity. Despite the contribution from different approaches, no analytical model was proposed to explain the numerical results as the continuum limit of CDT. In this thesis we introduce graph ensembles as toy models of CDT and show that both the continuum limit and a scale dependent spectral dimension can be defined rigorously. First we focus on a simple graph ensemble, the random comb. It does not have any dynamics from the gravity point of view, but serves as an instructive toy model to introduce the characteristic scale of the graph, study the continuum limit and define the scale dependent spectral dimension. Having defined the continuum limit, we study the reduction of the spectral dimension on more realistic toy models, the multigraph ensembles, which serve as a radial approximation of CDT. We focus on the (recurrent) multigraph approximation of the two-dimensional CDT whose ensemble measure is analytically controlled. The latter comes from the critical Galton-Watson process conditioned on non-extinction. Next we turn our attention to transient multigraph ensembles, corresponding to higher-dimensional CDT. Firstly we study their fractal properties and secondly calculate the scale dependent spectral dimension and compare it to computer simulations. We comment further on the relation between Horava-Lifshitz gravity, asymptotic safety, multifractional spacetimes and CDT-like models.

Spanning tree congestion was defined by Ostrovskii (2004) as a measure of how well a network can perform if only minimal connection can be maintained. We compute the parameter for several families of graphs. In particular, by partitioning a hypercube into pieces with almost optimal edge-boundaries, we give tight estimates of the parameter thereby disproving a conjecture of Hruska (2008). For a typical random graph, the parameter exhibits a zigzag behaviour reflecting the feature that it is not monotone in the number of edges. This motivates the study of the most congested graphs where we show that any graph is close to a graph with small congestion. Next, we enumerate independent sets. Using the independent set polynomial, we compute the extrema of averages in trees and graphs. Furthermore, we consider inverse problems among trees and resolve a conjecture of Wagner (2009). A result in a more general setting is also proved which answers a question of Alon, Haber and Krivelevich (2011). After briefly considering polynomial invariants of general graphs, we specialize into trees. Three levels of tree distinguishing power are exhibited. We show that polynomials which do not distinguish rooted trees define typically exponentially large equivalence classes. On the other hand, we prove that the rooted Ising polynomial distinguishes rooted trees and that the Negami polynomial determines the subtree polynomial, strengthening results of Bollobás and Riordan (2000) and Martin, Morin and Wagner (2008). The top level consists of the chromatic symmetric function and it is proved to be a complete invariant for caterpillars.

Automatic memory management is crucial in implementation of runtime systems even though it induces a significant computational overhead. In this thesis I explore the use of statistical properties of the directed graph describing the set of live data to decide between garbage collection and heap expansion in a memory management algorithm combining the dynamic array represented heaps with a mark and sweep garbage collector to enhance its performance. The sampling method predicting the density and the distribution of useful data is implemented as a partial marking algorithm. The algorithm randomly marks the nodes of the directed graph representing the live data at different depths with a variable probability factor p. Using the information gathered by the partial marking algorithm in the current step and the knowledge gathered in the previous iterations, the proposed empirical formula predicts with reasonable accuracy the density of live nodes on the heap, to decide between garbage collection and heap expansion. The resulting heuristics are tested empirically and shown to improve overall execution performance significantly in the context of the Jinni Prolog compiler's runtime system.

This thesis consists of an introduction and five papers, of which two contribute to the theory of directed random graphs and three to the theory of greedy walks on point processes.           We consider a directed random graph on a partially ordered vertex set, with an edge between any two comparable vertices present with probability p, independently of all other edges, and each edge is directed from the vertex with smaller label to the vertex with larger label. In Paper I we consider a directed random graph on ℤ2 with the vertices ordered according to the product order and we show that the limiting distribution of the centered and rescaled length of the longest path from (0,0) to (n, [na] ), a<3/14, is the Tracy-Widom distribution. In Paper II we show that, under a suitable rescaling, the closure of vertex 0 of a directed random graph on ℤ with edge probability n−1 converges in distribution to the Poisson-weighted infinite tree. Moreover, we derive limit theorems for the length of the longest path of the Poisson-weighted infinite tree.           The greedy walk is a deterministic walk on a point process that always moves from its current position to the nearest not yet visited point. Since the greedy walk on a homogeneous Poisson process on the real line, starting from 0, almost surely does not visit all points, in Paper III we find the distribution of the number of visited points on the negative half-line and the distribution of the index at which the walk achieves its minimum. In Paper IV we place homogeneous Poisson processes first on two intersecting lines and then on two parallel lines and we study whether the greedy walk visits all points of the processes. In Paper V we consider the greedy walk on an inhomogeneous Poisson process on the real line and we determine sufficient and necessary conditions on the mean measure of the process for the walk to visit all points.

Dizemos que um grafo e conectado se existe um caminho de arestas entre quaisquer par de vértices. O grafo aleatório de Erdös-Rényi com n vértices e obtido conectando cada par de vértice com probabilidade pn ∈ (0, 1), independentemente dos outros. Neste trabalho, estudamos em detalhe o limiar da conectividade na probabilidade de conexão pn para grafos aleatórios Erdös-Rényi quando o número de vértices n diverge. Para este estudo, revisamos algumas ferramentas probabilísticas básicas (convergência de variáveis aleatórias e Métodos do primeiro e segundo momento), que também irão auxiliar ao melhor entendimento de resultados mais complexos. Além disto, aplicamos os conceitos anteriores para um modelo com uma topologia simples, mais especificamente estudamos o comportamento assintótico da probabilidade de não existência de vértices isolados, e discutimos a conectividade ou não do grafo. Por m mostramos a convergência em distrubuição do número de vértices isolados para uma Distribuição Poisson do modelo estudado. / We say that a graph is connected if there is a path edges between any pair of vertices. Random graph Erdös-Rényi with n vertices is obtained by connecting each pair of vertex with probability pn ∈ (0, 1) independently of the others. In this work, we studied in detail the connectivity threshold in the connection probability pn for random graphs Erdös-Rényi when the number of vertices n diverges. For this study, we review some basic probabilistic tools (convergence of random variables and methods of the first and second moment), which will lead to a better understanding of more complex results. In addition, we apply the above concepts for a model with a simple topology, specifically studied the asymptotic behavior of the probability of non-existence of isolated vertices, and we discussed the connectivity or not of the graph. Finally we show the convergence in distribution of the number of isolated vertices for a Poisson distribution of the studied model.

Recentemente, a teoria de grafos aleatórios vem sendo aplicada para modelar interações neurais do cérebro. Enquanto as propriedades dos grafos aleatórios vem sendo vastamente estudadas na literatura, o desenvolvimento de métodos de inferência estatística para essa classe de objetos tem recebido menos atenção. Nesse trabalho propomos um teste de hipóteses não paramétrico para testar se duas amostras de grafos aleatórios provém da mesma distribuição de probabilidade. Nós provamos como computar de maneira eficiente a estatística do teste e estudamos o desempenho do teste em dados simulados de grafos. A principal motivação deste trabalho é a aplicação do teste proposto em dados de eletroencefalograma. / The theory of random graphs has been successfully applied in recent years to model neural interactions in the brain. While the probabilistic properties of random graphs has been extensively studied in the literature, the development of statistical inference methods for this class of objects has received less attention. In this work we propose a non parametric test of hypotheses to decide if two samples of random graphs are originated from the same probability distribution. We show how to compute efficiently the test statistic and we study the performance of the test on simulated data. The main motivation of this work is to apply this test to analyze neural networks constructed from electroencephalographic data.