Analytical properties of horizontal visibility graphs in the Feigenbaum scenario

Time series are proficiently converted into graphs via the horizontal visibility (HV) algorithm, which prompts interest in its capability for capturing the nature of different classes of series in a network context. We have recently shown [B. Luque et al., PLoS ONE 6, 9 (2011)] that dynamical systems can be studied from a novel perspective via the use of this method. Specifically, the period-doubling and band-splitting attractor cascades that characterize unimodal maps transform into families of graphs that turn out to be independent of map nonlinearity or other particulars. Here, we provide an in depth description of the HV treatment of the Feigenbaum scenario, together with analytical derivations that relate to the degree distributions, mean distances, clustering coefficients, etc., associated to the bifurcation cascades and their accumulation points. We describe how the resultant families of graphs can be framed into a renormalization group scheme in which fixed-point graphs reveal their scaling properties. These fixed points are then re-derived from an entropy optimization process defined for the graph sets, confirming a suggested connection between renormalization group and entropy optimization. Finally, we provide analytical and numerical results for the graph entropy and show that it emulates the Lyapunov exponent of the map independently of its sign.

Time series irreversibility: a visibility graph approach

We propose a method to measure real-valued time series irreversibility which combines two different tools: the horizontal visibility algorithm and the Kullback-Leibler divergence. This method maps a time series to a directed network according to a geometric criterion. The degree of irreversibility of the series is then estimated by the Kullback-Leibler divergence (i.e. the distinguishability) between the in and out degree distributions of the associated graph. The method is computationally efficient and does not require any ad hoc symbolization process. We find that the method correctly distinguishes between reversible and irreversible stationary time series, including analytical and numerical studies of its performance for: (i) reversible stochastic processes (uncorrelated and Gaussian linearly correlated), (ii) irreversible stochastic processes (a discrete flashing ratchet in an asymmetric potential), (iii) reversible (conservative) and irreversible (dissipative) chaotic maps, and (iv) dissipative chaotic maps in the presence of noise. Two alternative graph functionals, the degree and the degree-degree distributions, can be used as the Kullback-Leibler divergence argument. The former is simpler and more intuitive and can be used as a benchmark, but in the case of an irreversible process with null net current, the degree-degree distribution has to be considered to identify the irreversible nature of the series

Phase transition in the countdown problem

We present a combinatorial decision problem, inspired by the celebrated quiz show called Countdown, that involves the computation of a given target number T from a set of k randomly chosen integers along with a set of arithmetic operations. We find that the probability of winning the game evidences a threshold phenomenon that can be understood in the terms of an algorithmic phase transition as a function of the set size k. Numerical simulations show that such probability sharply transitions from zero to one at some critical value of the control parameter, hence separating the algorithm's parameter space in different phases. We also find that the system is maximally efficient close to the critical point. We derive analytical expressions that match the numerical results for finite size and permit us to extrapolate the behavior in the thermodynamic limit.

Feigenbaum graphs at the onset of chaos

We analyze the properties of networks obtained from the trajectories of unimodal maps at the transi- tion to chaos via the horizontal visibility (HV) algorithm. We find that the network degrees fluctuate at all scales with amplitude that increases as the size of the network grows, and can be described by a spectrum of graph-theoretical generalized Lyapunov exponents. We further define an entropy growth rate that describes the amount of information created along paths in network space, and find that such en- tropy growth rate coincides with the spectrum of generalized graph-theoretical exponents, constituting a set of Pesin-like identities for the network.

Detecting periodicity with horizontal visibility graphs

The horizontal visibility algorithm was recently introduced as a mapping between time series and networks. The challenge lies in characterizing the structure of time series (and the processes that generated those series) using the powerful tools of graph theory. Recent works have shown that the visibility graphs inherit several degrees of correlations from their associated series, and therefore such graph theoretical characterization is in principle possible. However, both the mathematical grounding of this promising theory and its applications are in its infancy. Following this line, here we address the question of detecting hidden periodicity in series polluted with a certain amount of noise. We first put forward some generic properties of horizontal visibility graphs which allow us to define a (graph theoretical) noise reduction filter. Accordingly, we evaluate its performance for the task of calculating the period of noisy periodic signals, and compare our results with standard time domain (autocorrelation) methods. Finally, potentials, limitations and applications are discussed.

Proyecto de camino forestal de saca y acceso del monte comuna de buñola. Numero 5 del catalogo (provincia de Baleares)

Tratase de construir la vía principal de saca y acceso al monte citado. Hoy en día solo detestables caminos de carro ponen en comunicación este monte de 723,77 Has. y 500 m3 de posibilidad con el mundo exterior y las consecuencias son funestas tanto con respecto a la economía maderera como para la conservación y mejora de la masa forestal.

Horizontal visibility graphs generated by type-I intermittency

The type-I intermittency route to (or out of) chaos is investigated within the horizontal visibility (HV) graph theory. For that purpose, we address the trajectories generated by unimodal maps close to an inverse tangent bifurcation and construct their associatedHVgraphs.We showhowthe alternation of laminar episodes and chaotic bursts imprints a fingerprint in the resulting graph structure. Accordingly, we derive a phenomenological theory that predicts quantitative values for several network parameters. In particular, we predict that the characteristic power-law scaling of the mean length of laminar trend sizes is fully inherited by the variance of the graph degree distribution, in good agreement with the numerics. We also report numerical evidence on how the characteristic power-law scaling of the Lyapunov exponent as a function of the distance to the tangent bifurcation is inherited in the graph by an analogous scaling of block entropy functionals defined on the graph. Furthermore, we are able to recast the full set of HV graphs generated by intermittent dynamics into a renormalization-group framework, where the fixed points of its graph-theoretical renormalization-group flow account for the different types of dynamics.We also establish that the nontrivial fixed point of this flow coincides with the tangency condition and that the corresponding invariant graph exhibits extremal entropic properties.

Quasiperiodic graphs at the onset of chaos

We examine the connectivity fluctuations across networks obtained when the horizontal visibility (HV) algorithm is used on trajectories generated by nonlinear circle maps at the quasiperiodic transition to chaos. The resultant HV graph is highly anomalous as the degrees fluctuate at all scales with amplitude that increases with the size of the network. We determine families of Pesin-like identities between entropy growth rates and generalized graph-theoretical Lyapunov exponents. An irrational winding number with pure periodic continued fraction characterizes each family. We illustrate our results for the so-called golden, silver, and bronze numbers

Phase transitions in number theory: from the birthday problem to Sidon sets

In this work, we show how number theoretical problems can be fruitfully approached with the tools of statistical physics. We focus on g-Sidon sets, which describe sequences of integers whose pairwise sums are different, and propose a random decision problem which addresses the probability of a random set of k integers to be g-Sidon. First, we provide numerical evidence showing that there is a crossover between satisfiable and unsatisfiable phases which converts to an abrupt phase transition in a properly defined thermodynamic limit. Initially assuming independence, we then develop a mean-field theory for the g-Sidon decision problem. We further improve the mean-field theory, which is only qualitatively correct, by incorporating deviations from independence, yielding results in good quantitative agreement with the numerics for both finite systems and in the thermodynamic limit. Connections between the generalized birthday problem in probability theory, the number theory of Sidon sets and the properties of q-Potts models in condensed matter physics are briefly discussed

Quasiperiodic Graphs: Structural Design, Scaling and Entropic Properties

A novel class of graphs, here named quasiperiodic, are const ructed via application of the Horizontal Visibility algorithm to the time series generated along the quasiperiodic route to chaos. We show how the hierarchy of mode-locked regions represented by the Far ey tree is inherited by their associated graphs. We are able to establish, via Renormalization Group (RG) theory, the architecture of the quasiperiodic graphs produced by irrational winding numbers with pure periodic continued fraction. And finally, we demonstrate that the RG fixed-point degree distributions are recovered via optimization of a suitably defined graph entropy

Mapping Dynamics into Graphs. The Visibility Algorithm

Si no tenemos en cuenta posibles procesos subyacentes con significado físico, químico, económico, etc., podemos considerar una serie temporal como un mero conjunto ordenado de valores y jugar con él algún inocente juego matemático como transformar dicho conjunto en otro objeto con la ayuda de una operación matemática para ver qué sucede: qué propiedades del conjunto original se conservan, cuáles se transforman y cómo, qué podemos decir de alguna de las dos representaciones matemáticas del objeto con sólo atender a la otra... Este ejercicio sería de cierto interés matemático por sí solo. Ocurre, además, que las series temporales son un método universal de extraer información de sistemas dinámicos en cualquier campo de la ciencia. Esto hace ganar un inesperado interés práctico al juego matemático anteriormente descrito, ya que abre la posibilidad de analizar las series temporales (vistas ahora como evolución temporal de procesos dinámicos) desde una nueva perspectiva. Hemos para esto de asumir la hipótesis de que la información codificada en la serie original se conserva de algún modo en la transformación (al menos una parte de ella). El interés resulta completo cuando la nueva representación del objeto pertencece a un campo de la matemáticas relativamente maduro, en el cual la información codificada en dicha representación puede ser descodificada y procesada de manera efectiva. ABSTRACT Disregarding any underlying process (and therefore any physical, chemical, economical or whichever meaning of its mere numeric values), we can consider a time series just as an ordered set of values and play the naive mathematical game of turning this set into a different mathematical object with the aids of an abstract mapping, and see what happens: which properties of the original set are conserved, which are transformed and how, what can we say about one of the mathematical representations just by looking at the other... This exercise is of mathematical interest by itself. In addition, it turns out that time series or signals is a universal method of extracting information from dynamical systems in any field of science. Therefore, the preceding mathematical game gains some unexpected practical interest as it opens the possibility of analyzing a time series (i.e. the outcome of a dynamical process) from an alternative angle. Of course, the information stored in the original time series should be somehow conserved in the mapping. The motivation is completed when the new representation belongs to a relatively mature mathematical field, where information encoded in such a representation can be effectively disentangled and processed. This is, in a nutshell, a first motivation to map time series into networks.

Evaluación del impacto del programa Monumenta en los centros históricos del sur de Brasil : los casos de Pelotas, Porto Alegre (Rio Grande do Sul) y São Francisco do Sul (Santa Catarina)

Esta Tesis tiene como objetivo demostrar que los programas de preservación del patrimonio, durante su fase de implementación, deben someterse a un análisis multidisciplinar que haga un balance de su ejecución. Dicho análisis permitirá identificar resultados significativos, capaces de fundamentar la rectificación de las bases conceptuales de la política pública en cuestión. Este reajuste podrá darse, por lo tanto, durante su vigencia y, de forma más relevante, posteriormente, sus motivos y resultados permitirán elaborar nuevas estrategias que serán aplicadas en futuros programas de intervención. Por otro lado se indagó, además, si las ciudades participantes en un programa nacional de preservación del patrimonio, regidas por normas y metas comunes, podrían alcanzar resultados diferentes. Para atender a estos objetivos, la investigación se encuentra enfocada a la realidad brasileña, siendo seleccionado como objeto de estudio el Programa Monumenta. Este Programa formó parte de la política pública cultural del Ministerio de Cultura con una importante implicación del Banco Interamericano de Desarrollo. Implementado a partir de 1999, procuró promover un proceso de recuperación urbana sostenible y de preservación del patrimonio de 26 Sitios Históricos Urbanos o Conjuntos de Monumentos Urbanos protegidos por el Instituto del Patrimonio Histórico y Artístico Nacional (Iphan). El Programa contó con el apoyo de la Unesco y del Iphan, así como con la participación de las Administraciones Municipales y/o Estatales, sectores privados y la sociedad civil. Las hipótesis planteadas en esta Tesis Doctoral fueron: (a) el análisis de los resultados en la fase de implementación de un programa de preservación del patrimonio es imprescindible, porque permite extraer conclusiones preliminares y orientar sus reformas; (b) los objetivos a corto plazo establecidos por el Programa Monumenta fueron alcanzados de modo diferenciado en las distintas ciudades beneficiadas; (c) a pesar de las diferencias, el Programa Monumenta presentó resultados preliminares positivos y significativos en la preservación del patrimonio histórico urbano brasileño. Los procedimientos metodológicos se centraron en un análisis cuantitativo, cualitativo y comparativo de los resultados alcanzados por tres ciudades beneficiadas por el Programa Monumenta, seleccionadas según su tamaño poblacional: Pelotas, Porto Alegre (Estado de Rio Grande do Sul) y São Francisco do Sul (Estado de Santa Catarina). Estos procedimientos fueron aplicados en los siguientes indicadores: utilización de los equipamientos culturales, características de la población y de los domicilios, variación de las actividades económicas, financiación destinada al sector privado para la recuperación de inmuebles y el fomento de la seguridad urbana. La Tesis ha englobado discusiones y conceptos abordados en las disciplinas de la Sociología Urbana, Geografía Urbana, Historia, Economía y Estadística de modo que se atribuye al objeto de investigación una visión interdisciplinar que ayudará a la comprensión de la teoría y la práctica preservacionistas. El análisis de la varianza, la regresión lineal y el análisis factorial fueron las herramientas estadísticas aplicadas sobre los datos con el objetivo de constatar la significación de los resultados y la relación de correspondencia entre algunas variables. Esta Tesis contribuye a la elaboración de una metodología analítica que puede ser aplicada en el cálculo de la superficie ocupada por las actividades económicas, con base en el método estadístico del Diagrama de Caja y Bigotes, de John Wilder Tukey. Las conclusiones corroboran las hipótesis planteadas y pretenden contribuir al diseño de las nuevas políticas públicas de preservación de sitios históricos de carácter urbano, enfatizando, con ello, la necesidad de evaluaciones más profundas de los resultados durante su fase de implementación. ---------------------------------------------------------------------------------- RESUMO--------------------------------------------------------------------------- A presente Tese apresenta como objetivo principal demonstrar que os programas de preservação do patrimônio histórico, durante a sua fase de implementação, necessitam de uma análise multidisciplinar sobre a sua execução. Essa análise permite identificar resultados significativos, capazes de fundamentar a retificação das bases conceituais da política pública em questão. A correção poderá, portanto, ser realizada tanto durante a sua vigência como posteriormente, ao permitir a elaboração de novas estratégias a serem aplicadas nos futuros programas de intervenção. Por outro lado, indagou-se se cidades participantes de um mesmo programa nacional de preservação do patrimônio histórico, regidas por normas e metas comuns, poderiam alcançar resultados não similares. Para atender tais objetivos, a investigação enfoca a realidade brasileira, tendo sido selecionado o Programa Monumenta como objeto de estudo. Esse Programa fez parte de uma política pública cultural do Ministério da Cultura, que atuou em parceria com o Banco Interamericano de Desenvolvimento. Implantado em nível nacional, a partir de 1999, visava promover um processo de recuperação urbana sustentável, bem como a preservação do patrimônio de 26 Sítios Urbanos Históricos ou Conjuntos de Monumentos Urbanos, protegidos pelo Instituto do Patrimônio Histórico e Artístico Nacional (Iphan). O Programa contou com o apoio da Unesco e do Iphan, além da participação das Administrações Municipais e/ou Estaduais, setores privados e sociedade civil. As hipóteses estabelecidas nesta Tese Doutoral foram: (a) a análise dos resultados na fase de implementação de um programa de preservação do patrimônio é imprescindível, pois permite extrair conclusões preliminares e orientar as suas reformulações; (b) os objetivos em curto prazo, estabelecidos pelo Programa Monumenta, foram alcançados de modo diferente pelas cidades beneficiadas; (c) apesar das diferenças, o Programa Monumenta apresentou resultados preliminares positivos e significativos sobre a preservação do patrimônio histórico urbano brasileiro. Os procedimentos metodológicos se centraram em análises quantitativa, qualitativa e comparativa dos resultados alcançados em três cidades beneficiadas pelo Programa Monumenta, selecionadas de acordo com o tamanho populacional: Pelotas, Porto Alegre (Estado do Rio Grande do Sul) e São Francisco do Sul (Estado de Santa Catarina). Esses procedimentos foram aplicados nos seguintes indicadores: utilização dos equipamentos culturais, características da população e dos domicílios, atividades econômicas, financiamento destinado ao setor privado para a recuperação dos imóveis e, ainda, o fomento da segurança urbana. A Tese inclui discussões e conceitos abordados nas disciplinas de Sociologia Urbana, Geografia Urbana, História, Economia e Estatística, de modo a atribuir ao objeto de investigação uma visão interdisciplinar e uma compreensão entre a teoria e a prática preservacionista. A análise de variância, regressão linear e análise fatorial foram as técnicas estatísticas aplicadas sobre os dados, com o objetivo de constatar a significação dos resultados e a relação de correspondência entre algumas variáveis. Esta Tese contribui com a elaboração de uma metodologia aplicada no cálculo da superfície ocupada pelas atividades econômicas, utilizando como método estatístico o Diagrama de Caixa e Bigodes, de John Wilder Tukey. As conclusões corroboram com as hipóteses estabelecidas e pretendem contribuir para o desenho de novas políticas públicas de preservação de sítios históricos de caráter urbano, enfatizando a necessidade de avaliações mais profundas dos resultados durante a sua fase de implementação. ---------------------------------------------------------------------------------- ABSTRACT ---------------------------------------------------------------------------------- The main goal of this PhD. Thesis is to demonstrate that a multidisciplinary analysis is needed during the implementation phase of preservation of heritage programmes. Such analysis allows the identification of significant results, which in turn can serve as the foundation for the conceptual bases of the public policy at hand. Thus, any corrections can be made both during the programme and afterward, by introducing new strategies to be applied in future intervention programmes. On the other hand, this project also asks whether cities participating in the same national preservation of heritage programme with common rules and goals can achieve distinct results. In order to meet these objectives, the project chose Brazil as its focus and Monumenta Programme for its object of study. This Programme is part of the Ministry of Culture’s public cultural policy, and was developed with cooperation by the Inter-American Development Bank. Implemented at the national level in 1999, the Programme aimed at promoting a process of sustainable urban renewal and the preservation of 26 urban historic sites or urban monumental ensembles, protected by the National Historic and Artistic Heritage Institute (IPHAN). UNESCO and IPHAN supported the Programme, and participants included municipal and state offices, private businesses, and local residents. The hypotheses established in this Doctoral Thesis were: (a) the analysis of the results in the implementation phase of a cultural public policy is imperative, because it enables preliminary conclusions to be drawn and orientate reforms; (b) the short-term objectives set out in the Monumenta Programme were achieved differently in the benefitted cities; (c) despite the differences, the Monumenta Programme displayed significant positive preliminary results in the conservation of the urban historic heritage in Brazil. Methodology procedures centered around quantitative, qualitative, and comparative analyses of the results achieved in three benefiting cities, selected according to population size: Pelotas, Porto Alegre (Rio Grande do Sul State) and São Francisco do Sul (Santa Catarina State). These procedures were applied to the following indicators: the use of the cultural facilities, characteristics of the population and the residential housing, variation of the economic activities, financing destined for the recovery of real estate, and promoting urban safety. The Thesis includes discussions and concepts addressed in urban sociology, urban geography, history, economics, and statistics, in order to examine the object of study with an interdisciplinary eye and an understanding between preservation theory and practice. Variance analysis, linear regression, and factorial analysis were the statistical techniques applied to the data, with the goal of defining the significance of the results and the correspondence ratio between some of the variables. This Thesis attempted to elaborate an applied methodology for calculating the space occupied by economic activities, using John Wilder Tukey's statistical method of Box-and-Whisker Plot. The conclusions corroborated the hypotheses established and are meant to contribute to the design of new public policies of historical site preservation in urban settings, emphasizing the need for deeper evaluations of the results during the implementation phase.