CiteULike: AbnerCYH's dynamics

Epidemic dynamics and endemic states in complex networks

Romualdo Pastor-Satorras — 2008-07-03T18:28:23-00:00

Physical Review E, Vol. 63, No. 6. (22 May 2001), 066117.

Epidemic Spreading in Scale-Free Networks

Romualdo Pastor-Satorras — 2007-10-22T19:13:25-00:00

Physical Review Letters, Vol. 86, No. 14. (2 April 2001), 3200.

The Internet has a very complex connectivity recently modeled by the class of scale-free networks. This feature; which appears to be very efficient for a communications network; favors at the same time the spreading of computer viruses. We analyze real data from computer virus infections and find the average lifetime and persistence of viral strains on the Internet. We define a dynamical model for the spreading of infections on scale-free networks; finding the absence of an epidemic threshold and its associated critical behavior. This new epidemiological framework rationalizes data of computer viruses and could help in the understanding of other spreading phenomena on communication and social networks.

Endomorphisms and automorphisms of the shift dynamical system

GA Hedlund — 2007-12-27T17:41:30-00:00

Theory of Computing Systems, Vol. 3, No. 4. (1 December 1969), pp. 320-375.

Symbolic dynamics and finite automata

Marie-Pierre Béal — 2007-12-27T17:27:48-00:00

(1997), pp. 463-505.

Symbolic dynamic analysis of complex systems for anomaly detection

Asok Ray — 2007-12-27T17:23:56-00:00

Signal Process., Vol. 84, No. 7. (July 2004), pp. 1115-1130.

Pattern identification in dynamical systems via symbolic time series analysis

Venkatesh Rajagopalan — 2007-12-27T17:23:53-00:00

Pattern Recogn., Vol. 40, No. 11. (November 2007), pp. 2897-2907.

Symbolic time series analysis for anomaly detection: a comparative evaluation

Shin Chin — 2007-03-12T13:21:05-00:00

Signal Process., Vol. 85, No. 9. (September 2005), pp. 1859-1868.

An Introduction to Symbolic Dynamics and Coding

Douglas Lind — 2006-05-01T13:34:20-00:00

(24 November 1995)

Symbolic dynamics is a rapidly growing area of dynamical systems. Although it originated as a method to study general dynamical systems, it has found significant uses in coding for data storage and transmission as well as in linear algebra. This book is the first general textbook on symbolic dynamics and its applications to coding. Mathematical prerequisites are relatively modest (mainly linear algebra at the undergraduate level) especially for the first half of the book. Topics are carefully developed and motivated with many examples, and there are over 500 exercises to test the reader's understanding. The last chapter contains a survey of more advanced topics, and a comprehensive bibliography is included. This book will serve as an introduction to symbolic dynamics for advanced undergraduate students in mathematics, engineering, and computer science.

Dynamical Systems: Stability, Symbolic Dynamics, and Chaos (Studies in Advanced Mathematics)

Clark Robinson — 2007-12-27T17:16:07-00:00

(17 November 1998)

Several distinctive aspects make Dynamical Systems unique, including: · treating the subject from a mathematical perspective with the proofs of most of the results included · providing a careful review of background materials · introducing ideas through examples and at a level accessible to a beginning graduate student · focusing on multidimensional systems of real variables The book treats the dynamics of both iteration of functions and solutions of ordinary differential equations. Many concepts are first introduced for iteration of functions where the geometry is simpler, but results are interpreted for differential equations. The dynamical systems approach of the book concentrates on properties of the whole system or subsets of the system rather than individual solutions. The more local theory discussed deals with characterizing types of solutions under various hypothesis, and later chapters address more global aspects.

Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts (Universitext)

Bruce Kitchens — 2007-12-27T17:08:57-00:00

(14 November 1997)

This is a thorough introduction to the dynamics of one-sided and two-sided Markov shifts on a finite alphabet and to the basic properties of Markov shifts on a countable alphabet. These are the symbolic dynamical systems defined by a finite transition rule. The basic properties of these systems are established using elementary methods. The connections to other types of dynamical systems, cellular automata and information theory are illustrated with numerous examples. The book is written for graduate students and others who use symbolic dynamics as a tool to study more general systems.

Discrete Chaos

Saber Elaydi — 2007-12-27T16:37:30-00:00

(22 December 1999)

Over the last 15 years chaos has virtually exploded over the landscape of mathematics and showered its effects on nearly every scientific discipline. However, despite the large number of texts published on the subject, a need has persisted for a book accessible to readers of varying backgrounds that includes discussion of stability theory and emphasizes real-world applications. Discrete Chaos fills that need. With only calculus and linear algebra as prerequisites, this book offers a broad range of topics with a depth not often found in texts written at this level. The author presents a thorough exposition of both stability and chaos theories in both one and two dimensions. He offers a highly readable account of fractals and the mathematics behind them, and demonstrates a number of applications from a variety of fields. This unique treatment of chaos encourages readers to make mathematical discoveries of their own through computer experimentation. The author incorporates the use of Mapleä software throughout the book to aid in the solution of problems. All of the programs used in the book can be easily downloaded from the Internet. You'll find even the most difficult material in an elementary framework, easily accessible regardless of your background and specialization. With a multitude of exercises to further enhance the learning experience, Discrete Chaos offers the perfect vehicle for beginning the journey into the rich world of chaos.

The Discrete Chaos

Norbert Wiener — 2007-12-27T16:37:04-00:00

American Journal of Mathematics, Vol. 65, No. 2. (1943), pp. 279-298.

Power-law distributions in empirical data

Aaron Clauset — 2007-06-13T16:25:35-00:00

(7 Jun 2007)

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

Characterization of complex networks: A survey of measurements

Luciano — 2005-10-17T16:49:02-00:00

(30 Jun 2005)

Each complex network (or class of networks) presents specific topological features which characterize its connectivity and highly influence the dynamics and function of processes executed on the network. The analysis, discrimination, and synthesis of complex networks therefore rely on the use of measurements capable of expressing the most relevant topological features. This article presents a survey of such measurements. It includes general considerations about complex network characterization, a brief review of the principal models, and the presentation of the main existing measurements organized into classes. Special attention is given to relating complex network analysis with the areas of pattern recognition and feature selection, as well as on surveying some concepts and measurements from traditional graph theory which are potentially useful for complex network research. Depending on the network and the analysis task one has in mind, a specific set of features may be chosen. It is hoped that the present survey will help the identification of suitable measurements.

Graph theoretical analysis of complex networks in the brain

2007-10-26T08:46:15-00:00

Nonlinear Biomedical Physics, Vol. 1 (5 July 2007)

Statistical mechanical systems on complete graphs, infinite exchangeability, finite extensions and a discrete finite moment problem

Thomas Liggett — 2007-07-31T10:09:20-00:00

(30 Jul 2007)

We show that a large collection of statistical mechanical systems with quadratically represented Hamiltonians on the complete graph can be extended to infinite exchangeable processes. This extends a known result for the ferromagnetic Curie--Weiss Ising model and includes as well all ferromagnetic Curie--Weiss Potts and Curie--Weiss Heisenberg models. By de Finetti's theorem, this is equivalent to showing that these probability measures can be expressed as averages of product measures. We provide examples showing that “ferromagnetism” is not however in itself sufficient and also study in some detail the Curie--Weiss Ising model with an additional 3-body interaction. Finally, we study the question of how much the antiferromagnetic Curie--Weiss Ising model can be extended. In this direction, we obtain sharp asymptotic results via a solution to a new moment problem. We also obtain a “formula” for the extension which is valid in many cases.

Quantifying social group evolution

Gergely Palla — 2007-04-04T18:39:56-00:00

Nature, Vol. 446, No. 7136. (5 April 2007), pp. 664-667.

he rich set of interactions between individuals in society1, 2, 3, 4, 5, 6, 7 results in complex community structure, capturing highly connected circles of friends, families or professional cliques in a social network3, 7, 8, 9, 10. Thanks to frequent changes in the activity and communication patterns of individuals, the associated social and communication network is subject to constant evolution7, 11, 12, 13, 14, 15, 16. Our knowledge of the mechanisms governing the underlying community dynamics is limited, but is essential for a deeper understanding of the development and self-optimization of society as a whole17, 18, 19, 20, 21, 22. We have developed an algorithm based on clique percolation23, 24 that allows us to investigate the time dependence of overlapping communities on a large scale, and thus uncover basic relationships characterizing community evolution. Our focus is on networks capturing the collaboration between scientists and the calls between mobile phone users. We find that large groups persist for longer if they are capable of dynamically altering their membership, suggesting that an ability to change the group composition results in better adaptability. The behaviour of small groups displays the opposite tendency—the condition for stability is that their composition remains unchanged. We also show that knowledge of the time commitment of members to a given community can be used for estimating the community's lifetime. These findings offer insight into the fundamental differences between the dynamics of small groups and large institutions.

Entropy of cellular automata

Tom Meyerovitch — 2007-03-07T15:59:07-00:00

(6 Mar 2007)

Let $X=S^G$ where $G$ is a countable group and $S$ is a finite set. A cellular automaton (CA) is an endomorphism $T : X \to X$ (continuous, commuting with the action of $G$). Shereshevsky (1993) proved that for $G=Z^d$ with $d>1$ no CA can be forward expansive, raising the following conjecture: For $G=Z^d$, $d>1$ the topological entropy of any CA is either zero or infinite. Morris and Ward (1998), proved this for linear CA's, leaving the original conjecture open. We show that this conjecture is false, proving that for any $d$ there exist a $d$-dimensional CA with finite, nonzero topological entropy. We also discuss a measure-theoretic counterpart of this question for measure-preserving CA's. Our main tool is a construction of a CA by Kari (1994).

On the Submodularity of Influence in Social Networks

Elchanan Mossel — 2006-12-05T09:18:42-00:00

(2 Dec 2006)

We prove and extend a conjecture of Kempe, Kleinberg, and Tardos (KKT) on the spread of influence in social networks. A social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or “word-of-mouth” effects on such a graph is to consider an increasing process of “infected” (or active) nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a certain threshold value. Such a model was introduced by KKT in \citeKeKlTa:03,KeKlTa:05 where the authors also impose several natural assumptions: the threshold values are (uniformly) random; and the activation functions are monotone and submodular. For an initial set of active nodes $S$, let $σ(S)$ denote the expected number of active nodes at termination. Here we prove a conjecture of KKT: we show that the function $σ(S)$ is submodular under the assumptions above. We prove the same result for the expected value of any monotone, submodular function of the set of active nodes at termination.

The structure and function of complex networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(25 March 2003)

Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.

Random matrix analysis of network Laplacians

Sarika Jalan — 2006-11-30T05:00:51-00:00

(29 Nov 2006)

We analyze eigenvalues fluctuations of the Laplacian of various networks under the random matrix theory (RMT) framework. We present our analysis for scale-free networks, small-world networks and random networks. We show that nearest neighbor spacing distribution (NNSD) of the Laplacian of these networks follow Gaussian orthogonal ensemble (GOE) statistics of RMT. Furthermore, we study NNSD as a function of the random connections and find that transition to GOE statistics occurs at the small-world transition.

Computational Dynamics

Ahmed Shabana — 2006-11-30T17:33:44-00:00

(2001)

Dynamics of Complex Systems (Studies in Nonlinearity)

Yaneer Bar-Yam — 2006-05-16T11:02:51-00:00

The study of complex systems in a unified framework has become recognized in recent years as a new scientific discipline, the ultimate in the interdisciplinary fields. Breaking down the barriers between physics, chemistry, and biology and the so-called soft sciences of psychology, sociology, economics and anthropology, this text explores the universal physical and mathematical principles that govern the emergence of complex systems from simple components. <I>Dynamics of Complex Systems</I> is the first text describing the modern unified study of complex systems. It is designed for upper-undergraduate/beginning graduate level students, and covers a broad range of applications in a broad array of disciplines. A central goal of this text is to develop models and modeling techniques that are useful when applied to all complex systems. This is done by adopting both analytic tools, including statistical mechanics and stochastic dynamics, and computer simulation techniques, such as cellular automata and Monte Carlo. In four sets of paired, self-contained chapters, Yaneer Bar-Yam discusses complex systems in the context of neural networks, protein folding, living organisms, and finally, human civilization itself. He explores fundamental questions about the structure, dynamics, evolution, development and quantitative complexity that apply to all complex systems. In the first chapter, mathematical foundations such as iterative maps and chaos, probability theory and random walks, thermodynamics, information and computation theory, fractals and scaling, are reviewed to enable the text to be read by students and researchers with a variety of backgrounds.

Model of Wealth and Goods Dynamics in a Closed Market

Marcel Ausloos — 2006-05-11T20:13:40-00:00

(10 May 2006)

A simple computer simulation model of a closed market on a fixed network with free flow of goods and money is introduced. The model contains only two variables : the amount of goods and money beside the size of the system. An initially flat distribution of both variables is presupposed. We show that under completely random rules, i.e. through the choice of interacting agent pairs on the network and of the exchange rules that the market stabilizes in time and shows diversification of money and goods. We also indicate that the difference between poor and rich agents increases for small markets, as well as for systems in which money is steadily deduced from the market through taxation.