Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Nesta dissertaÃÃo, investigamos por meio de extensiva simulaÃÃo numÃrica o processo de invasÃo que ocorre no interior de um meio poroso desordenado. Neste processo, a invasÃo comeÃa em um poÃo denominado de injeÃÃo e se estende atà atingir outros poÃos denominados de extraÃÃo. Em nosso estudo, o poÃo de injeÃÃo està localizado no centro de uma rede quadrada de tamanho L e os quatro poÃos de extraÃÃo estÃo situados simetricamente em torno do poÃo de injeÃÃo a uma distÃncia r deste. NÃs estudamos duas estratÃgias de exploraÃÃo: (A) todos os poÃos sÃo perfurados simultaneamente; (B) os poÃos de extraÃÃo sÃo perfurados, a medida que a produÃÃo atravÃs do poÃo perfurado previamente apresenta um declÃnio, ou seja, quando a frente de propagaÃÃo atingir este poÃo. Quando o modelo de percolaÃÃo invasiva à aplicado como um modelo simples para simular o deslocamento de um fluido viscoso por meio de um outro fluido menos viscoso, o comportamento da distribuiÃÃo de massa dos agregados invadidos pertence a diferentes classes de universalidade, dependendo do critÃrio utilizado para finalizar o processo. Nossa anÃlise considera o limite onde a pressÃo no poÃo de extraÃÃo Pe à zero, em outras palavras, a produÃÃo para logo que o fluido invasor atingi o poÃo de extraÃÃo. Nossos resultados mostram que, como esperado, a probabilidade de pararmos o processo de extraÃÃo com pequenas quantidades de massa extraÃda à muito reduzida quando se considera mÃltiplos poÃos. Neste trabalho, mostramos tambÃm quando à mais eficiente perfurar ou nÃo um poÃo de extraÃÃo adicional. Mostramos que a probabilidade de aumentarmos a quantidade de fluido extraÃda pela adiÃÃo de um novo poÃo ao processo depende da quantidade total extraÃda atravÃs do poÃo perfurado anteriormente. Os resultados obtidos aqui podem ser relevantes para determinar uma estratÃgia eficiente na exploraÃÃo de petrÃleo.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / In this thesis we study systems where some form of disorder or non-homogeneity has a significant role at the complexity of the structural building or of the dynamics regulation of the system. First, we study the dynamics of Boolean networks, where the rules to update the state of the nodes are randomly chosen and control the global behavior of the system. At the critical threshold, and near to it, we propose that the transition to the critical regime can be characterized by the divergence of the relaxation time Tr. Based on simple scaling arguments, we show that the cumulative probability distribution of Tr decays as a power-law , with exponent iqual -1, for the annealed model at the critical region. Then, we study a novel method for network decomposition, which we apply to scale-free networks, that have the broad degree distribution as a fundamental feature. This method consists in a simultaneous and iterative remotion of groups of nodes with degree K until there are no more nodes with this degree in the network. Thus, we define new variables that characterize the process of decomposition and we obtain a set of well define exponents and parameters. From the behavior of these variables we can see, through some mathematical manipulations, that our method is self-consistent, serving as a useful tool for the study of the structural features of the network. At last, we study the backbones of the percolation cluster, where we use a network model with layers arranged in a disorderly way to represent some kind of anisotropy resistance to the percolation. Our numerical results indicate a break at the universality class on the fractal dimension and on the mass distribution of the backbones. / Nesta tese estudaremos sistemas onde alguma forma de desordem ou nÃo-homogeneidade tem um importante papel na complexidade da formaÃÃo estrutural ou da regulagem dinÃmica do sistema. Primeiramente estudaremos a dinÃmica das redes Booleanas, onde as regras de atualizaÃÃo escolhidas aleatoriamente controlam o comportamento global do sistema. Na condiÃÃo crÃtica e prÃximo dela, propomos que a transiÃÃo para o regime crÃtico pode ser caracterizado pela divergÃncia do tempo de relaxaÃÃo Tr. Baseados em simples argumentos de escalonamento, mostramos, alÃm de outros resultados, que a probabilidade acumulativa da distribuiÃÃo de Tr decai como uma lei de potÃncia, com o expoente igual a -1, para o modelo annealed na regiÃo crÃtica. Em seguida estudamos um novo mÃtodo de decomposiÃÃo de redes aplicado Ãs redes livres de escalas, onde a ampla distribuiÃÃo de conectividade à um aspecto fundamental. O mÃtodo consiste basicamente na retirada simultÃnea e iterativa de grupos de vÃrtices com um determinado grau K de conectividade atà que nÃo haja mais sÃtios com este mesmo grau de conectividade na rede. Deste modo, definimos algumas variÃveis que caractarizam o processo de decomposiÃÃo e obtemos uma sÃrie de expoentes e parÃmetros bem definidos. A partir do comportamento destas variÃveis pudemos constatar por meio de algumas manipulaÃÃes matemÃticas que nosso mÃtodo à auto-consistente, servindo como Ãtima ferramenta para estudo dos aspectos estruturais de uma rede. Por fim, estudamos os backbones, onde utilizamos um modelo de rede em que a desordem està no arranjo aleatÃrio de camadas fÃceis e difÃceis à percolaÃÃo. Os resultados numÃricos indicam a quebra na classe de universalidade da geometria fractal e da distribuiÃÃo de tamanhos de massa do backbones e tambÃm um comportamento assintÃtico da dimensÃo fractal no limite de grandes valores de massa e/ou anisotropia.

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.

FundaÃÃo de Amparo à Pesquisa do Estado do Cearà / CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Na natureza todo material se quebra dependendo do valor de tensÃo aplicada. Dependendo do tipo, forma e outras caracterÃsticas do material ou atà mesmo do ponto de tensÃo, podemos produzir {it fraturas} distintas, como um rasgo em uma folha de papel tensionada, um congestionamento na rede de trÃnsito de uma cidade ou solos rachados por climas Ãridos. Tais fraturas se relacionam economicamente com a extraÃÃo de petrÃleo de reservatÃrios subterrÃneos, com a extraÃÃo de calor e vapor de reservatÃrios geotÃrmicos e atà mesmo com a preservaÃÃo dos lenÃÃis freÃticos. Fenomenologicamente, podemos imaginar que processos de fraturas sÃo aqueles que dividem o sistema em duas ou mais partes, destruindo sua conectividade global. Nesse contexto, construÃmos dois modelos computacionais para estudar, caracterizar e elucidar o comportamento de fenÃmenos naturais semelhantes aos processos de fraturas. No primeiro modelo, exploramos conceitos de percolaÃÃo invasiva aplicados à descriÃÃo da geometria irregular das cumeeiras de montanhas que dividem bacias hidrogrÃficas. Mostramos de forma robusta o carÃcter auto-similar das linhas de divisores de Ãguas, com expoente fractal $D=1.21pm0.001$ para paisagens artificiais nÃo-correlacionadas e, $D=1.10pm0.01$ e $D=1.11pm0.01$ para paisagens correlacionadas reais dos Alpes SuÃÃos e das Montanhas do Himalaia, respectivamente. No segundo modelo, utilizamos caminhos Ãtimos que sÃo sequencialmente interrompidos, levando ao colapso do sistema, produzindo uma fratura percolante. No caso bidimensional, consideramos paisagens artificiais nÃo-correlacionadas com desordem fraca e forte. Em ambos os regimes obtivemos o mesmo expoente fractal para o esqueleto da fratura, $D=1.22pm0.01$. Para paisagens artificiais correlacionadas, encontramos que a dimensÃo fractal do esqueleto da fratura decresce com o aumento do expoente de {it Hurst}. No caso tridimensional, consideramos apenas paisagens nÃo-correlacionadas artificiais com desordem forte. Nesse caso, obtivemos uma superfÃcie percolante com dimensÃo fractal $D=2.47pm0.05$ que fratura o sistema em duas partes. / In the nature all material breaks down depending on the value of stress applied. Depending of kind, shape and other characteristics of the material or even the stress point, we can produce distinct {it fractures}, like a tear on stressed sheet of paper, a congestion in the network traffic of a city or cracked soils by arid climates. Such fractures are economically related with the extraction of oil from the underground reservoirs, with the extraction of heat and steam from geothermal reservoirs and even the preservation of the groundwater. Phenomenologically, we can imagine that fracture processes are the ones that divides the system in two or more parts, destroying its global connectivity. In this context, we built two computer models to study, characterize and elucidate the behavior of natural phenomena similar to fracture processes. In the first model, we explored concepts of invasion percolation applied to description of the irregular geometry of the ridge of mountains that divides hydrographic basins. We shown robustly the self-similar nature of the watershed lines, with fractal exponent $D=1.21pm0.001$ for artificial uncorrelated landscapes and, $D=1.10pm0.01$ and $D=1.11pm0.01$, for real correlated landscapes of the Swiss Alps and the Himalaya Mountains, respectively. In the second model, we used optimal paths that are cracked sequentialy providing the collapse of the system, producing a percolating fracture. In the two-dimensional case, we considered artificial uncorrelated landscapes in the weak and strong disorder. In both regimes, we obtained the same fractal exponent for the backbone fracture, $D=1.22pm0.01$. For artificial correlated landscapes, we found that the fractal dimension of the backbone decreases with increasing of the {it Hurst} exponent. In the three-dimensional case, we considered only artificial uncorrelated landscapes with strong disorder. In this case, we obtained a percolating surface with fractal dimension $D=2.47pm0.05$ that cracks the system in two parts.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Nesta dissertaÃÃo, investigamos por meio de simulaÃÃo computacional propriedades geomÃtricas e de transportes relacionadas ao fenÃmeno de invasÃo em meios porosos desordenados no regime de invasÃo muito lento em sistemas bidimensionais e tridimensionais. O meio poroso considerado aqui à representado por meio de uma estrutura desordenada onde a cada poro que compÃe este meio se associa um nÃmero aleatÃrio obtido a partir de uma distribuiÃÃo uniforme. Considerando o regime lento de invasÃo, onde as forÃas capilares dominam o escoamento em relaÃÃo as forÃas viscosas, utilizando para a dinÃmica de invasÃo o modelo de percolaÃÃo invasiva sem aprisionamento. Introduzimos um variante no modelo de percolaÃÃo invasiva, assumindo o aspecto de mÃltiplas invasÃes, onde a cada nova invasÃo apenas parte do substrato utilizado na invasÃo anterior pode ser invadido novamente. Em uma primeira parte, estudamos como o processo de mÃltipla invasÃo altera as caracterÃsticas do agregado invadido. Valores estimados para a dimensÃo fractal da regiÃo invadida revelam que os expoentes crÃticos variam em funÃÃo do nÃmero de geraÃÃo G, isto Ã, o nÃmero de vezes que o processo de invasÃo foi repetido. Com base em dados numÃricos, mostramos que a massa mÃdia do agregado invadido decresce na forma de uma lei de potÃncia como funÃÃo de G, M ~ G^{-β}, com o expoente β = 0.59 (2D) e 0.73 (3D). Investigamos como a dimensÃo fractal do agregado invadido varia em funÃÃo dos repetitivos processo de invasÃo, mostrando que as mesmas variam de df = 1.89  0.02 atà ds = 1.22  0.02 para o caso (2D) e df = 2.52  0.02 atà ds = 1.46  0.02 para o caso (3D). Os resultados confirmam que o processo de mÃltiplas invasÃes segue uma transiÃÃo continua entre as classes de universalidade do modelo de percolaÃÃo invasiva sem aprisionamento e Ãtimo caminho, sendo este comportamento observado em duas e trÃs dimensÃes. Um outro aspecto investigado nessa dissertaÃÃo, foi o fenÃmeno de avalanche que ocorre durante o processo de invasÃo. Investigamos como a distribuiÃÃo de tamanhos de avalanche, que se comporta na forma de uma lei de potÃncia P(S, L) ~ S^{-τ} , altera-se em funÃÃo das mÃltiplas invasÃes. Mais precisamente, calculamos como o expoente que governa o comportamento das avalanches se altera em funÃÃo do nÃmero de geraÃÃo G. Verificamos que este comportamento do expoente em funÃÃo de G à semelhante para duas e trÃs dimensÃes, apresentando uma regiÃo de mudanÃa suave seguida por uma mudanÃa mais acentuada atà atingir um limite de saturaÃÃo, onde o sistema se comporta de maneira parecida com o caso unidimensional. / In this dissertation, we investigate by means of numerical simulations geometrical and transport properties related with the invasion phenomena through disordered porous media in a very slow invasion regime, using two and three dimensions porous medias. Here, the porous media is modeling by means of a random structure, where each pore is represented by a random number comes from a uniform distribution. We assume that the invasion process occurs in the limit of very low viscous force, which means that the invasion process is controlled by capillary force. In this limit the invasion percolation model without trap is suitable. The new aspect incorporated here, consists basically of a multiple invasion process, where after the first invasion takes place only part of the structure of the porous, that was invaded previous, can be invaded again. We study, how the multiple invasion changes the fractal dimension of the invaded cluster. Estimated values for the fractal dimension of the invaded region reveal that the critical exponents vary as a function of the generation number G, i.e., where the number of times the invasion takes place. On base in numerical datas, we show the averaged mass M of the invaded region decreases with a power law as a function of G, M ∼ G{−β} , where the exponents β ≈ 0.59 (2D) and β ≈ 0.73 (3D). We also investigated, how the fractal dimension changes as a function of G, find that the fractal dimension of the invaded cluster changes from df = 1.89  0.02 to ds = 1.22  0.02 and df = 2.52  0.02 to ds = 1.46  0.02 for (2D) and (3D), respectively. These results confirm that the multiple invasion process follows a continuous transition from one universality class (nontrapping invasion percolation) to another (optimal path), furthermore these change are continuos for both dimensionality. Another aspect investigated, was the avalanche distribution in the invasion process. We analyzed how the distribution of avalanche changes as function of G, more precisely, how the multiple invasion process changes the exponent τ of the power law distribution. Regardless the values, we find that the behaviour of the exponents τ looks like the same for both dimensions studied. The exponents τ , initially change in a very slow way until reach a region, of certain value of G which depend on the dimension, they start to decrease in a deep way until reach the saturation value. The saturation value is close, for (2D), to one-dimension case.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Usamos EvoluÃÃes de Schramm-Loewner (SLE) para expor a origem de interfaces anisotrÃpicas presentes em percolaÃÃo. Mais precisamente, nossos resultados, obtidos atravÃs de extensas simulaÃÃes numÃricas, indicam que os perÃmetros de agregados encontrados em duas variantes do modelo de percolaÃÃo tÃm como limite termodinÃmico evoluÃÃes de Loewner dirigidas por movimentos Brownianos anÃmalos. PercolaÃÃo em multi-camadas exibe comportamento superdifusivo e percolaÃÃo direcionada subdifusivo. Testamos a conexÃo entre difusÃo anÃmala e anisotropia usando sÃries temporais com correlaÃÃo de longo alcance em lei de potÃncia (movimentos Brownianos fracionÃrios) como funÃÃes diretoras nas SLE@. Nossa hipÃtese à corroborada pelo fato de que os traÃos obtidos sÃo distintamente anisotrÃpicos. Sob a estrutura conceitual das SLE, nosso estudo revela novas perspectivas para interpretaÃÃes matemÃticas e fÃsicas de processos nÃo-Markovianos em termos de caminhos anisotrÃpicos em criticalidade, e vice-versa. / We disclose the origin of anisotropic percolation perimeters in terms of the Stochastic Loewner Evolution (SLE) process. Precisely, our results from extensive numerical simulations indicate that the perimeters of multi-layered and directed percolation clusters at criticality have as scaling limits the Loewner evolution of an anomalous Brownian motion, being superdiffusive and subdiffusive, respectively. The connection between anomalous diffusion and fractal anisotropy is further tested by using long-range power-law correlated time series (fractional Brownian motion) as driving functions in the evolution process. The fact that the resulting traces are distinctively anisotropic corroborates our hypothesis. Under the conceptual framework of SLE, our study therefore reveals new perspectives for mathematical and physical interpretations of non-Markovian processes in terms of anisotropic paths at criticality and vice-versa.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / In this work, we study some parameters of monophonic convexity in some classes of graphs and we present our results about this subject. We prove that decide if the $m$-interval number is at most 2 and decide if the $m$-percolation time is at most 1 are NP-complete problems even on bipartite graphs. We also prove that the $m$-convexity number is as hard to approximate as the maximum clique problem, which is, $O(n^{1-varepsilon})$-unapproachable in polynomial-time, unless P=NP, for each $varepsilon>0$. Finally, we obtain polynomial time algorithms to compute the $m$-convexity number on hereditary graph classes such that the computation of the clique number is polynomial-time solvable (e.g. perfect graphs and planar graphs). / Neste trabalho, estudamos alguns parÃmetros para a convexidade monofÃnica em algumas classes de grafos e apresentamos nossos resultados acerca do assunto. Provamos que decidir se o nÃmero de $m$-intervalo à no mÃximo 2 e decidir se o tempo de $m$-percolaÃÃo à no mÃximo 1 sÃo problemas NP-completos mesmo em grafos bipartidos. TambÃm provamos que o nÃmero de $m$-convexidade à tÃo difÃcil de aproximar quanto o problema da Clique MÃxima, que Ã, $O(n^{1-varepsilon})$-inaproximÃvel em tempo polinomial, a menos que P=NP, para cada $varepsilon>0$. Finalmente, apresentamos um algoritmo de tempo polinomial para determinar o nÃmero de $m$-convexidade em classes hereditÃrias de grafos onde a computaÃÃo do tamanho da clique mÃxima à em tempo polinomial (como grafos perfeitos e grafos planares).