Novel critical phenomena in optimization driven processes on networks

Abstract

The work presented in this Ph.D thesis was developed in the context of complex network theory, from a statistical physics standpoint. We examine two distinct problems in this research field, taking a special interest in their respective critical properties. In both cases, the emergence of criticality is driven by a local optimization dynamics. Firstly, a recently introduced class of percolation problems that attracted a significant amount of attention from the scientific community, and was quickly followed up by an abundance of other works. Percolation transitions were believed to be continuous, until, recently, an 'explosive' percolation problem was reported to undergo a discontinuous transition, in [93]. The system's evolution is driven by a metropolis-like algorithm, apparently producing a discontinuous jump on the giant component's size at the percolation threshold. This finding was subsequently supported by number of other experimental studies [96, 97, 98, 99, 100, 101]. However, in [1] we have proved that the explosive percolation transition is actually continuous. The discontinuity which was observed in the evolution of the giant component's relative size is explained by the unusual smallness of the corresponding critical exponent, combined with the finiteness of the systems considered in experiments. Therefore, the size of the jump vanishes as the system's size goes to infinity. Additionally, we provide the complete theoretical description of the critical properties for a generalized version of the explosive percolation model [2], as well as a method [3] for a precise calculation of percolation's critical properties from numerical data (useful when exact results are not available). Secondly, we study a network flow optimization model, where the dynamics consists of consecutive mergings and splittings of currents flowing in the network. The current conservation constraint does not impose any particular criterion for the split of current among channels outgoing nodes, allowing us to introduce an asymmetrical rule, observed in several real systems. We solved analytically the dynamic equations describing this model in the high and low current regimes. The solutions found are compared with numerical results, for the two regimes, showing an excellent agreement. Surprisingly, in the low current regime, this model exhibits some features usually associated with continuous phase transitions.

O trabalho apresentado nesta tese foi desenvolvido no contexto da teoria de redes complexas, na perspectiva da física estatística. So analisados dois problemas distintos neste campo de investigação, dando especial importância às respectivas propriedades críticas. Em ambos os casos, o estado crítico é produzido por mecanismos de optimização local. Em primeiro lugar, estudamos uma classe de modelos de percolação recentemente proposta, que atraiu uma quantidade significativa da atenção da comunidade científica, e foi prontamente acompanhada por uma abundância de outros trabalhos. As transições de percolação julgavam-se continuas, ate recentemente ter sido relatado, em [93], um problema de percolação 'explosiva', que possui uma transição de fase descontínua. A evolução do sistema é impelida por um algoritmo do tipo metropolis, o que aparentemente produz um salto no tamanho do componente gigante. Esta noção foi subsequentemente apoiada por vários outros estudos experimentais [96, 97, 98, 99, 100, 101]. Contudo, em [1] nós provámos que a transição de percolação explosiva é, na verdade, contínua. A descontinuidade observada na evolução do tamanho relativo do componente gigante e explicada pela invulgar pequenez do expoente crítico correspondente, combinada com o carácter finito dos sistemas considerados nas experiências. Assim, o salto desaparece quando o tamanho do sistema vai para infinito. Adicionalmente, fornecemos a descrição teórica completa das propriedades críticas de um modelo [2] que generalizada o problema da percolação explosiva, assim como, um método [3] que permite o cálculo preciso dessas propriedades a partir de dados numéricos (útil na ausência de resultados exactos). Em segundo lugar, estudamos um modelo de optimização de fluxo em redes, onde a dinâmica consiste em consecutivas junções e divisões das correntes. A condição de conservação de corrente não impõe qualquer critério em particular para a divisão da corrente pelos canais de saída dos nodos, o que permite introduzir uma regra assimétrica, observada em vários sistemas reais. Resolvemos analiticamente as equações dinâmicas que descrevem estes sistemas para os regimes de altas e baixas correntes. As soluções encontradas são comparadas com resultados numéricos, em ambos os regimes, e mostram uma excelente concordância. Surpreendentemente, no regime de baixas corrente, este modelo exibe alguns dos atributos geralmente associados a transições de fase contínuas.