Particle competition for complex network community detection

In many real situations, randomness is considered to be uncertainty or even confusion which impedes human beings from making a correct decision. Here we study the combined role of randomness and determinism in particle dynamics for complex network community detection. In the proposed model, particles walk in the network and compete with each other in such a way that each of them tries to possess as many nodes as possible. Moreover, we introduce a rule to adjust the level of randomness of particle walking in the network, and we have found that a portion of randomness can largely improve the community detection rate. Computer simulations show that the model has good community detection performance and at the same time presents low computational complexity. (C) 2008 American Institute of Physics.

PARTIAL STABILITY FOR A CLASS OF NONLINEAR SYSTEMS

This paper studies a nonlinear, discrete-time matrix system arising in the stability analysis of Kalman filters. These systems present an internal coupling between the state components that gives rise to complex dynamic behavior. The problem of partial stability, which requires that a specific component of the state of the system converge exponentially, is studied and solved. The convergent state component is strongly linked with the behavior of Kalman filters, since it can be used to provide bounds for the error covariance matrix under uncertainties in the noise measurements. We exploit the special features of the system-mainly the connections with linear systems-to obtain an algebraic test for partial stability. Finally, motivated by applications in which polynomial divergence of the estimates is acceptable, we study and solve a partial semistability problem.

Transport properties in nontwist area-preserving maps

Nontwist systems, common in the dynamical descriptions of fluids and plasmas, possess a shearless curve with a concomitant transport barrier that eliminates or reduces chaotic transport, even after its breakdown. In order to investigate the transport properties of nontwist systems, we analyze the barrier escape time and barrier transmissivity for the standard nontwist map, a paradigm of such systems. We interpret the sensitive dependence of these quantities upon map parameters by investigating chaotic orbit stickiness and the associated role played by the dominant crossing of stable and unstable manifolds. (C) 2009 American Institute of Physics. [doi: 10.1063/1.3247349]

Reduction of chaotic particle transport driven by drift waves in sheared flows

Investigations of chaotic particle transport by drift waves propagating in the edge plasma of tokamaks with poloidal zonal flow are described. For large aspect ratio tokamaks, the influence of radial electric field profiles on convective cells and transport barriers, created by the nonlinear interaction between the poloidal flow and resonant waves, is investigated. For equilibria with edge shear flow, particle transport is seen to be reduced when the electric field shear is reversed. The transport reduction is attributed to the robust invariant tori that occur in nontwist Hamiltonian systems. This mechanism is proposed as an explanation for the transport reduction in Tokamak Chauffage Alfven Bresilien [R. M. O. Galvao , Plasma Phys. Controlled Fusion 43, 1181 (2001)] for discharges with a biased electrode at the plasma edge.

Dynamical estimates of chaotic systems from Poincare recurrences

We show a function that fits well the probability density of return times between two consecutive visits of a chaotic trajectory to finite size regions in phase space. It deviates from the exponential statistics by a small power-law term, a term that represents the deterministic manifestation of the dynamics. We also show how one can quickly and easily estimate the Kolmogorov-Sinai entropy and the short-term correlation function by realizing observations of high probable returns. Our analyses are performed numerically in the Henon map and experimentally in a Chua's circuit. Finally, we discuss how our approach can be used to treat the data coming from experimental complex systems and for technological applications. (C) 2009 American Institute of Physics. [doi: 10.1063/1.3263943]

Experimental observation of a complex periodic window

The existence of a special periodic window in the two-dimensional parameter space of an experimental Chua's circuit is reported. One of the main reasons that makes such a window special is that the observation of one implies that other similar periodic windows must exist for other parameter values. However, such a window has never been experimentally observed, since its size in parameter space decreases exponentially with the period of the periodic attractor. This property imposes clear limitations for its experimental detection.

Deformed Gaussian-orthogonal-ensemble description of small-world networks

The study of spectral behavior of networks has gained enthusiasm over the last few years. In particular, random matrix theory (RMT) concepts have proven to be useful. In discussing transition from regular behavior to fully chaotic behavior it has been found that an extrapolation formula of the Brody type can be used. In the present paper we analyze the regular to chaotic behavior of small world (SW) networks using an extension of the Gaussian orthogonal ensemble. This RMT ensemble, coined the deformed Gaussian orthogonal ensemble (DGOE), supplies a natural foundation of the Brody formula. SW networks follow GOE statistics until a certain range of eigenvalue correlations depending upon the strength of random connections. We show that for these regimes of SW networks where spectral correlations do not follow GOE beyond a certain range, DGOE statistics models the correlations very well. The analysis performed in this paper proves the utility of the DGOE in network physics, as much as it has been useful in other physical systems.

Dissipation as a mechanism of energy gain

Some properties of the annular billiard under the presence of weak dissipation are studied. We show, in a dissipative system, that the average energy of a particle acquires higher values than its average energy of the conservative case. The creation of attractors, associated with a chaotic dynamics in the conservative regime, both in appropriated regions of the phase space, constitute a generic mechanism to increase the average energy of dynamical systems.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

GLOBALIZATION OF TWISTED PARTIAL ACTIONS

Let A be a unital ring which is a product of possibly infinitely many indecomposable rings. We establish a criteria for the existence of a globalization for a given twisted partial action of a group on A. If the globalization exists, it is unique up to a certain equivalence relation and, moreover, the crossed product corresponding to the twisted partial action is Morita equivalent to that corresponding to its globalization. For arbitrary unital rings the globalization problem is reduced to an extendibility property of the multipliers involved in the twisted partial action.

Mechanism and model of the oscillatory electro-oxidation of methanol

A mechanism for the kinetic instabilities observed in the galvanostatic electro-oxidation of methanol is suggested and a model developed. The model is investigated using stoichiometric network analysis as well as concepts from algebraic geometry (polynomial rings and ideal theory) revealing the occurrence of a Hopf and a saddle-node bifurcation. These analytical solutions are confirmed by numerical integration of the system of differential equations. (C) 2010 American Institute of Physics

Multifractal regime transition in a modified minority game model

The search for more realistic modeling of financial time series reveals several stylized facts of real markets. In this work we focus on the multifractal properties found in price and index signals. Although the usual minority game (MG) models do not exhibit multifractality, we study here one of its variants that does. We show that the nonsynchronous MG models in the nonergodic phase is multifractal and in this sense, together with other stylized facts, constitute a better modeling tool. Using the structure function (SF) approach we detected the stationary and the scaling range of the time series generated by the MG model and, from the linear (non-linear) behavior of the SF we identified the fractal (multifractal) regimes. Finally, using the wavelet transform modulus maxima (WTMM) technique we obtained its multifractal spectrum width for different dynamical regimes. (C) 2009 Elsevier Ltd. All rights reserved.

Low dimensional behavior in three-dimensional coupled map lattices

The analysis of one-, two-, and three-dimensional coupled map lattices is here developed under a statistical and dynamical perspective. We show that the three-dimensional CML exhibits low dimensional behavior with long range correlation and the power spectrum follows 1/f noise. This approach leads to an integrated understanding of the most important properties of these universal models of spatiotemporal chaos. We perform a complete time series analysis of the model and investigate the dependence of the signal properties by change of dimension. (c) 2008 Elsevier Ltd. All rights reserved.

Stretching and folding mechanism in foams

We have described the stretching and folding of foams in a vertical Hele-Shaw cell containing air and a surfactant solution, from a sequence of upside-down flips. Besides the firactal dimension of the foam, we have observed the logistic growth for the soap film length. The stretching and folding mechanism is present during the foam formation, and this mechanism is observed even after the foam has reached its respective maximum fractal dimension. Observing the motion of bubbles inside the foam, large bubbles present power spectrum associated with random walk motion in both directions, while the small bubbles are scattered like balls in a Galton board. (C) 2008 Published by Elsevier B.V.