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.