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.

Guía para el desarrollo de software seguro

El presente Trabajo de Fin de Grado (TFG) es el resultado de la necesidad de la seguridad en la construcción del software ya que es uno de los mayores problemas con que se enfrenta hoy la industria debido a la baja calidad de la misma tanto en software de Sistema Operativo, como empotrado y de aplicaciones. La creciente dependencia de software para que se hagan trabajos críticos significa que el valor del software ya no reside únicamente en su capacidad para mejorar o mantener la productividad y la eficiencia. En lugar de ello, su valor también se deriva de su capacidad para continuar operando de forma fiable incluso de cara de los eventos que la amenazan. La capacidad de confiar en que el software seguirá siendo fiable en cualquier circunstancia, con un nivel de confianza justificada, es el objetivo de la seguridad del software. Seguridad del software es importante porque muchas funciones críticas son completamente dependientes del software. Esto hace que el software sea un objetivo de valor muy alto para los atacantes, cuyos motivos pueden ser maliciosos, penales, contenciosos, competitivos, o de naturaleza terrorista. Existen fuentes muy importantes de mejores prácticas, métodos y herramientas para mejorar desde los requisitos en sus aspectos no funcionales, ciclo de vida del software seguro, pasando por la dirección de proyectos hasta su desarrollo, pruebas y despliegue que debe ser tenido en cuenta por los desarrolladores. Este trabajo se centra fundamentalmente en elaborar una guía de mejores prácticas con la información existente CERT, CMMI, Mitre, Cigital, HP, y otras fuentes. También se plantea desarrollar un caso práctico sobre una aplicación dinámica o estática con el fin de explotar sus vulnerabilidades.---ABSTRACT---This Final Project Grade (TFG) is the result of the need for security in software construction as it is one of the biggest problems facing the industry today due to the low quality of it both OS software, embedded software and applications software. The increasing reliance on software for critical jobs means that the value of the software no longer resides solely in its capacity to improve or maintain productivity and efficiency. Instead, its value also stems from its ability to continue to operate reliably even when facing events that threaten it. The ability to trust that the software will remain reliable in all circumstances, with justified confidence level is the goal of software security. The security in software is important because many critical functions are completely dependent of the software. This makes the software to be a very high value target for attackers, whose motives may be by a malicious, by crime, for litigating, by competitiveness or by a terrorist nature. There are very important sources of best practices, methods and tools to improve the requirements in their non-functional aspects, the software life cycle with security in mind, from project management to its phases (development, testing and deployment) which should be taken into account by the developers. This paper focuses primarily on developing a best practice guide with existing information from CERT, CMMI, Mitre, Cigital, HP, and other organizations. It also aims to develop a case study on a dynamic or static application in order to exploit their vulnerabilities.