Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Um nÃmero significativo de redes reais possui caracterÃsticas locais ou nÃo-locais bem definidas. NÃs estudamos como estas caracterÃsticas podem influenciar processos de navegaÃÃo e processos percolativos que venham a ocorrer nas mesmas. Primeiramente, estudamos o problema de navegaÃÃo em redes regulares com ligaÃÃes de longo alcance e sujeitas a um vÃnculo de custo. Neste caso, a rede à construÃda a partir de uma rede regular de dimensÃo d a ser melhorada por meio da adiÃÃo de ligaÃÃes de longo alcance (atalhos) com uma probabilidade $P_{ij} sim r_{ji}^{-alpha}$ , onde $r_{ij}$ à a distÃncia de Manhattan entre os sÃtios $i$ e $j$. Mostramos que a condiÃÃo de navegaÃÃo Ãtima, $alpha = d+1$, permanece Ãtima, independente da estratÃgia de navegaÃÃo utilizada, seja ela baseada em um conhecimento local ou global da estrutura da rede. Em seguida, apresentamos um processo de crescimento de agregados que fornece uma clara conexÃo entre a MecÃnica EstatÃstica no equilÃbrio e o processo percolativo nÃo-local conhecido como PercolaÃÃo Explosiva. Mostramos que dois ingredientes sÃo suficientes para obter uma transiÃÃo abrupta na fraÃÃo do sistema ocupada pelo maior agregado: (i) os tamanhos de todos os agregados devem ser mantidos aproximadamente iguais durante o processo percolativo e (ii) a inclusÃo de ligaÃÃes de fusÃo (i.e., ligaÃÃes que conectam agregados diferentes) deve dominar o processo em detrimento de ligaÃÃes redundantes (i.e., ligaÃÃes que conectam sÃtios em um mesmo agregado). Por Ãltimo, introduzimos um modelo que generaliza a regra do produto para PercolaÃÃo Explosiva que revela os efeitos da nÃo-localidade no comportamento crÃtico do processo de percolaÃÃo. Mais precisamente, pares de ligaÃÃes nÃo ocupadas sÃo escolhidos de acordo com uma probabilidade que decai em lei de potÃncia com sua distÃncia de Manhattan, e apenas a ligaÃÃo que conecta agregados para os quais o produto de seus tamanho à o menor, à ocupada. Nossos resultados para redes regulares finitas em diversas dimensÃes sugerem que, na criticalidade, o expoente da lei de potÃncia tem uma influÃncia significativa nos expoentes de escala, onde observa-se uma transiÃÃo nos expoentes da percolaÃÃo tradicional para os expoentes da percolaÃÃo explosiva (nÃo-local) em determinados casos. / A significant number of real networks have well-defined local and nonlocal features. We investigate the influence of these features in the navigation through small-world networks and in explosive percolation. First, we investigate the navigation problem in lattices with long-range connections and subject to a cost constraint. Our network is built from a regular d-dimensional lattice to be improved by adding long-range connections (shortcuts) with probability $P_{ij} sim r_{ij}^{-alpha}, where $r_{ij}$ is the Manhattan distance between nodes $i$ and $j$, and a is $alpha$ variable exponent. We find optimal transport in the system for $alpha = d+1$. Remarkably, this condition remains optimal, regardless of the strategy used for navigation being based on local or global knowledge of the network structure. Second, we present a cluster growth process that provides a clear connection between equilibrium statistical mechanics and the nonlocal explosive percolation process. We show that the following two ingredients are sufficient for obtaining an abrupt transition in the fraction of the system occupied by the largest cluster: (i) the size of all growing clusters should be kept approximately the same, and (ii) the inclusion of merging bonds (i.e., bonds connecting nodes in different clusters) should dominate with respect to the redundant bonds (i.e., bonds connecting nodes in the same cluster). Finally, we introduce a generalization of the product rule for explosive percolation that reveals the effect of nonlocality on the critical behavior of the percolation process. Precisely, pairs of unoccupied bonds are chosen according to a probability that decays as a power law of their Manhattan distance, and only that bond connecting clusters whose product of their sizes is the smallest becomes occupied. Our results for d-dimensional lattices at criticality shows that the power law exponent of the product rule has a significant influence on the finite-size scaling exponents for the spanning cluster, the conducting backbone, and the cutting bonds of the system. For all these types of clusters, we observe a clear transition from ordinary to (nonlocal) explosive percolation.

REIS, Saulo Davi Soares e. Local and global effects on navigation in small-world networks and explosive percolation. 2012. 86 f. Tese (Doutorado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2012. / Submitted by Edvander Pires (edvanderpires@gmail.com) on 2015-06-16T20:35:22Z No. of bitstreams: 1 2012_tese_sdsreis.pdf: 3097854 bytes, checksum: 3798beb23c0415893113a8072fc802fe (MD5) / Approved for entry into archive by Edvander Pires(edvanderpires@gmail.com) on 2015-06-18T18:21:41Z (GMT) No. of bitstreams: 1 2012_tese_sdsreis.pdf: 3097854 bytes, checksum: 3798beb23c0415893113a8072fc802fe (MD5) / Made available in DSpace on 2015-06-18T18:21:41Z (GMT). No. of bitstreams: 1 2012_tese_sdsreis.pdf: 3097854 bytes, checksum: 3798beb23c0415893113a8072fc802fe (MD5) Previous issue date: 2012 / A significant number of real networks have well-defined local and nonlocal features. We investigate the influence of these features in the navigation through small-world networks and in explosive percolation. First, we investigate the navigation problem in lattices with long-range connections and subject to a cost constraint. Our network is built from a regular d-dimensional lattice to be improved by adding long-range connections (shortcuts) with probability $P_{ij} sim r_{ij}^{-alpha}, where $r_{ij}$ is the Manhattan distance between nodes $i$ and $j$, and a is $alpha$ variable exponent. We find optimal transport in the system for $alpha = d+1$. Remarkably, this condition remains optimal, regardless of the strategy used for navigation being based on local or global knowledge of the network structure. Second, we present a cluster growth process that provides a clear connection between equilibrium statistical mechanics and the nonlocal explosive percolation process. We show that the following two ingredients are sufficient for obtaining an abrupt transition in the fraction of the system occupied by the largest cluster: (i) the size of all growing clusters should be kept approximately the same, and (ii) the inclusion of merging bonds (i.e., bonds connecting nodes in different clusters) should dominate with respect to the redundant bonds (i.e., bonds connecting nodes in the same cluster). Finally, we introduce a generalization of the product rule for explosive percolation that reveals the effect of nonlocality on the critical behavior of the percolation process. Precisely, pairs of unoccupied bonds are chosen according to a probability that decays as a power law of their Manhattan distance, and only that bond connecting clusters whose product of their sizes is the smallest becomes occupied. Our results for d-dimensional lattices at criticality shows that the power law exponent of the product rule has a significant influence on the finite-size scaling exponents for the spanning cluster, the conducting backbone, and the cutting bonds of the system. For all these types of clusters, we observe a clear transition from ordinary to (nonlocal) explosive percolation. / Um número significativo de redes reais possui características locais ou não-locais bem definidas. Nós estudamos como estas características podem influenciar processos de navegação e processos percolativos que venham a ocorrer nas mesmas. Primeiramente, estudamos o problema de navegação em redes regulares com ligações de longo alcance e sujeitas a um vínculo de custo. Neste caso, a rede é construída a partir de uma rede regular de dimensão d a ser melhorada por meio da adição de ligações de longo alcance (atalhos) com uma probabilidade $P_{ij} sim r_{ji}^{-alpha}$ , onde $r_{ij}$ é a distância de Manhattan entre os sítios $i$ e $j$. Mostramos que a condição de navegação ótima, $alpha = d+1$, permanece ótima, independente da estratégia de navegação utilizada, seja ela baseada em um conhecimento local ou global da estrutura da rede. Em seguida, apresentamos um processo de crescimento de agregados que fornece uma clara conexão entre a Mecânica Estatística no equilíbrio e o processo percolativo não-local conhecido como Percolação Explosiva. Mostramos que dois ingredientes são suficientes para obter uma transição abrupta na fração do sistema ocupada pelo maior agregado: (i) os tamanhos de todos os agregados devem ser mantidos aproximadamente iguais durante o processo percolativo e (ii) a inclusão de ligações de fusão (i.e., ligações que conectam agregados diferentes) deve dominar o processo em detrimento de ligações redundantes (i.e., ligações que conectam sítios em um mesmo agregado). Por último, introduzimos um modelo que generaliza a regra do produto para Percolação Explosiva que revela os efeitos da não-localidade no comportamento crítico do processo de percolação. Mais precisamente, pares de ligações não ocupadas são escolhidos de acordo com uma probabilidade que decai em lei de potência com sua distância de Manhattan, e apenas a ligação que conecta agregados para os quais o produto de seus tamanho é o menor, é ocupada. Nossos resultados para redes regulares finitas em diversas dimensões sugerem que, na criticalidade, o expoente da lei de potência tem uma influência significativa nos expoentes de escala, onde observa-se uma transição nos expoentes da percolação tradicional para os expoentes da percolação explosiva (não-local) em determinados casos.

Random graph processes are basic mathematical models for large-scale networks evolving over time. Their systematic study was pioneered by Erdös and Rényi around 1960, and one key feature of many 'classical' models is that the edges appear independently. While this makes them amenable to a rigorous analysis, it is desirable, both mathematically and in terms of applications, to understand more complicated situations. In this thesis the main goal is to improve our rigorous understanding of evolving random graphs with significant dependencies. The first model we consider is known as an Achlioptas process: in each step two random edges are chosen, and using a given rule only one of them is selected and added to the evolving graph. Since 2000 a large class of 'complex' rules has eluded a rigorous analysis, and it was widely believed that these could give rise to a striking and unusual phenomenon. Making this explicit, Achlioptas, D'Souza and Spencer conjectured in Science that one such rule yields a very abrupt (discontinuous) percolation phase transition. We disprove this, showing that the transition is in fact continuous for all Achlioptas process. In addition, we give the first rigorous analysis of the more 'complex' rules, proving that certain key statistics are tightly concentrated (i) in the subcritical evolution, and (ii) also later on if an associated system of differential equations has a unique solution. The second model we study is the H-free process, where random edges are added subject to the constraint that they do not complete a copy of some fixed graph H. The most important open question for such 'constrained' processes is due to Erdös, Suen and Winkler: in 1995 they asked what the typical final number of edges is. While Osthus and Taraz answered this in 2000 up to logarithmic factors for a large class of graphs H, more precise bounds are only known for a few special graphs. We close this gap for the cases where a cycle of fixed length is forbidden, determining the final number of edges up to constants. Our result not only establishes several conjectures, it is also the first which answers the more than 15-year old question of Erdös et. al. for a class of forbidden graphs H.