Reading Abstracts

Phys. Rev. E 83, 031913 (2011): Complex and transitive synchronization in a frustrated system of calling frogs

2011-04-22T05:51:00.000-07:00

Phys. Rev. E 83, 031913 (2011): Complex and transitive synchronization in a frustrated system of calling frogs: "Complex and transitive synchronization in a frustrated system of calling frogs"

This letter reports synchronization phenomena and mathematical modeling on a frustrated system of living beings, or Japanese tree frogs (Hyla japonica). While an isolated male Japanese tree frog calls nearly periodically, he can hear sounds including calls of other males. Therefore, the spontaneous calling behavior of interacting males can be understood as a system of coupled oscillators. We construct a simple but biologically reasonable model based on the experimental results of two frogs, extend the model to a system of three frogs, and theoretically predict the occurrence of rich synchronization phenomena, such as triphase synchronization and 1:2 antiphase synchronization. In addition, we experimentally verify the theoretical prediction by ethological experiments on the calling behavior of three frogs and time series analysis on recorded sound data. Note that the calling behavior of three male Japanese tree frogs is frustrated because almost perfect antiphase synchronization is robustly observed in a system of two male frogs. Thus, nonlinear dynamics of the three-frogs system should be far from trivial.

Physical Review E - Synchronization patterns in transient spiral wave dynamics

2011-04-22T05:50:00.000-07:00

Physical Review E - Synchronization patterns in transient spiral wave dynamics: "Synchronization patterns in transient spiral wave dynamics"

Ulrich Parlitz, Alexander Schlemmer, and Stefan Luther

Transient dynamics of spiral waves in a two-dimensional Barkley model is shown to be governed by pattern formation processes resulting in regions of synchronized activity separated by moving interfaces. During the transient the number of internally synchronized regions decreases as synchronization fronts move to the boundary of the simulated area. This spatio-temporal transient dynamics in an excitable medium is detected and visualized by means of an analysis of the local periodicity and by evaluation of prediction errors across the spatial domain. During the (long) transient both analyses show patterns that must not be misinterpreted as any information about (spatial) structure of the underlying (completely homogeneous) system.

Physical Review E - Mismatch and synchronization: Influence of asymmetries in systems of two delay-coupled lasers

2011-04-22T05:49:00.001-07:00

Physical Review E - Mismatch and synchronization: Influence of asymmetries in systems of two delay-coupled lasers: "Mismatch and synchronization: Influence of asymmetries in systems of two delay-coupled lasers"

Physical Review E - Speeding up simulation of diffusion in zeolites by a parallel synchronous kinetic Monte Carlo algorithm

2011-04-22T05:49:00.000-07:00

Physical Review E - Speeding up simulation of diffusion in zeolites by a parallel synchronous kinetic Monte Carlo algorithm: "Speeding up simulation of diffusion in zeolites by a parallel synchronous kinetic Monte Carlo algorithm"

Modularity maximization and tree clustering: Novel ways to determine effective geographic borders. (arXiv:1104.1200v1 [physics.soc-ph])

2011-04-09T09:17:00.000-07:00

Modularity maximization and tree clustering: Novel ways to determine effective geographic borders. (arXiv:1104.1200v1 [physics.soc-ph]): "

Territorial subdivisions and geographic borders are essential for
understanding phenomena in sociology, political science, history, and
economics. They influence the interregional flow of information and
cross-border trade and affect the diffusion of innovation and technology.
However, most existing administrative borders were determined by a variety of
historic and political circumstances along with some degree of arbitrariness.
Societies have changed drastically, and it is doubtful that currently existing
borders reflect the most logical divisions. Fortunately, at this point in
history we are in a position to actually measure some aspects of the geographic
structure of society through human mobility. Large-scale transportation systems
such as trains and airlines provide data about the number of people traveling
between geographic locations, and many promising human mobility proxies are
being discovered, such as cell phones, bank notes, and various online social
networks. In this chapter we apply two optimization techniques to a human
mobility proxy (bank note circulation) to investigate the effective geographic
borders that emerge from a direct analysis of human mobility.

Detecting evolving patterns of self-organizing networks by flow hierarchy measurement

2011-02-18T04:49:00.000-08:00

Detecting evolving patterns of self-organizing networks by flow hierarchy measurement: "

Abstract

Hierarchies occur widely in evolving self-organizing ecological, biological, technological, and social networks, but detecting and comparing hierarchies is difficult. Here we present a metric and technique to quantitatively assess the extent to which self-organizing directed networks exhibit a flow hierarchy. Flow hierarchy is a commonly observed but theoretically overlooked form of hierarchy in networks. We show that the ecological, neurobiological, economic, and information processing networks are generally more hierarchical than their comparable random networks. We further discovered that hierarchy degree has increased over the course of the evolution of Linux kernels. Taken together, our results suggest that hierarchy is a central organizing feature of real-world evolving networks, and the measurement of hierarchy opens the way to understand the structural regimes and evolutionary patterns of self-organizing networks. Our measurement technique makes it possible to objectively compare hierarchies of different networks and of different evolutionary stages of a single network, and compare evolving patterns of different networks. It can be applied to various complex systems, which can be represented as directed networks. © 2011 Wiley Periodicals, Inc. Complexity, 2011

The interplay of microscopic and mesoscopic structure in complex networks. (arXiv:1012.4524v1 [cond-mat.stat-mech])

2010-12-27T07:13:00.000-08:00

The interplay of microscopic and mesoscopic structure in complex networks. (arXiv:1012.4524v1 [cond-mat.stat-mech]): "

Not all nodes in a network are created equal. Differences and similarities
exist at both individual node and group levels. Disentangling single node from
group properties is crucial for network modeling and structural inference.
Based on unbiased generative probabilistic exponential random graph models and
employing distributive message passing techniques, we present an efficient
algorithm that allows one to separate the contributions of individual nodes and
groups of nodes to the network structure. This leads to improved detection
accuracy of latent class structure in real world data sets compared to models
that focus on group structure alone. Furthermore, the inclusion of hitherto
neglected group specific effects in models used to assess the statistical
significance of small subgraph (motif) distributions in networks may be
sufficient to explain most of the observed statistics. We show the predictive
power of such generative models in forecasting putative gene-disease
associations in the Online Mendelian Inheritance in Man (OMIM) database. The
approach is suitable for both directed and undirected uni-partite as well as
for bipartite networks."

Quasirandom Rumor Spreading. (arXiv:1012.5351v1 [cs.DS])

2010-12-27T07:04:00.000-08:00

Quasirandom Rumor Spreading. (arXiv:1012.5351v1 [cs.DS]): "

We propose and analyse a quasirandom analogue of the classical push model for
disseminating information in networks ('randomized rumor spreading').

In the classical model, in each round each informed vertex chooses a neighbor
at random and informs it, if it was not before. It is known that this simple
protocol succeeds in spreading a rumor from one vertex to all others within
O(log n) rounds on complete graphs, hypercubes, random regular graphs,
Erdos-Renyi random graph and Ramanujan graphs with high probability.

In the quasirandom model, we assume that each vertex has a (cyclic) list of
its neighbors. Once informed, it starts at a random position of the list, but
from then on informs its neighbors in the order of the list. Surprisingly,
irrespective of the orders of the lists, the above mentioned bounds still hold.
In some cases even better bounds than for the classical model can be shown."

Dynamical quorum-sensing and synchronization of nonlinear oscillators coupled through an external medium. (arXiv:1012.4863v1 [q-bio.CB])

2010-12-23T16:23:00.000-08:00

Dynamical quorum-sensing and synchronization of nonlinear oscillators coupled through an external medium. (arXiv:1012.4863v1 [q-bio.CB]): "

Many biological and physical systems exhibit population-density dependent
transitions to synchronized oscillations in a process often termed 'dynamical
quorum sensing'. Synchronization frequently arises through chemical
communication via signaling molecules distributed through an external media. We
study a simple theoretical model for dynamical quorum sensing: a heterogenous
population of limit-cycle oscillators diffusively coupled through a common
media. We show that this model exhibits a rich phase diagram with four
qualitatively distinct mechanisms fueling population-dependent transitions to
global oscillations, including a new type of transition we term 'dynamic
death'. We derive a single pair of analytic equations that allows us to
calculate all phase boundaries as a function of population density and show
that the model reproduces many of the qualitative features of recent
experiments of BZ catalytic particles as well as synthetically engineered
bacteria."

A framework for proving the self-organization of dynamic systems. (arXiv:1011.2312v1 [cs.DC])

2010-11-13T14:47:00.000-08:00

A framework for proving the self-organization of dynamic systems. (arXiv:1011.2312v1 [cs.DC]): "

This paper aims at providing a rigorous definition of self- organization, one
of the most desired properties for dynamic systems (e.g., peer-to-peer systems,
sensor networks, cooperative robotics, or ad-hoc networks). We characterize
different classes of self-organization through liveness and safety properties
that both capture information re- garding the system entropy. We illustrate
these classes through study cases. The first ones are two representative P2P
overlays (CAN and Pas- try) and the others are specific implementations of
\Omega (the leader oracle) and one-shot query abstractions for dynamic
settings. Our study aims at understanding the limits and respective power of
existing self-organized protocols and lays the basis of designing robust
algorithm for dynamic systems.

Contact processes and moment closure on adaptive networks. (arXiv:1011.2689v1 [physics.soc-ph])

2010-11-13T14:34:00.000-08:00

Contact processes and moment closure on adaptive networks. (arXiv:1011.2689v1 [physics.soc-ph]): "

Contact processes describe the transmission of distinct properties of nodes
via the links of a network. They provide a simple framework for many phenomena,
such as epidemic spreading and opinion formation. Combining contact processes
with rules for topological evolution yields an adaptive network in which the
states of the nodes can interact dynamically with the topological degrees of
freedom. By moment-closure approximation it is possible to derive
low-dimensional systems of ordinary differential equations that describe the
dynamics of the adaptive network on a coarse-grained level. In this chapter we
discuss the approximation technique itself as well as its applications to
adaptive networks. Thus, it can serve both as a tutorial as well as a review of
recent results.

Clustering using Unsupervised Binary Trees: CUBT. (arXiv:1011.2624v1 [stat.ME])

2010-11-13T14:33:00.000-08:00

Clustering using Unsupervised Binary Trees: CUBT. (arXiv:1011.2624v1 [stat.ME]): "

We introduce a new clustering method based on unsupervised binary trees. It
is a three stages procedure, which performs on a first stage recursive binary
splits reducing the heterogeneity of the data within the new subsamples. On the
second stage (pruning) adjacent nodes are considered to be aggregated. Finally,
on the third stage (joining) similar clusters are joined even if they do not
descend from the same node. Consistency results are obtained and the procedure
is tested on simulated and real data sets

Effect of time delay on the onset of synchronization of the stochastic Kuramoto model. (arXiv:1008.1198v1 [cond-mat.stat-mech])

2010-08-21T06:51:00.000-07:00

Effect of time delay on the onset of synchronization of the stochastic Kuramoto model. (arXiv:1008.1198v1 [cond-mat.stat-mech]): "

We consider the Kuramoto model of globally coupled phase oscillators with
time-delayed interactions, that is subject to the Ornstein-Uhlenbeck (Gaussian)
colored or the non-Gaussian colored noise. We investigate numerically the
interplay between the influences of the finite correlation time of noise $\tau$
and the time delay $\tau_{d}$ on the onset of the synchronization process. Both
cases for identical and nonidentical oscillators had been considered. Among the
obtained results for identical oscillators is a large increase of the
synchronization threshold as a function of time delay for the colored
non-Gaussian noise compared to the case of the colored Gaussian noise at low
noise correlation time $\tau$. However, the difference reduces remarkably for
large noise correlation times. For the case of nonidentical oscillators, the
incoherent state may become unstable around the maximum value of the threshold
(as a function of time delay) even at lower coupling strength values in the
presence of colored noise as compared to the noiseless case. We had studied the
dependence of the critical value of the coupling strength (the threshold of
synchronization) on given parameters of the stochastic Kuramoto model in great
details and presented results for possible cases of colored Gaussian and
non-Gaussian noises.

Synchronization of Phase-coupled Oscillators with Distance-dependent Delay. (arXiv:1008.0494v1 [nlin.CD])

2010-08-05T09:18:00.000-07:00

Synchronization of Phase-coupled Oscillators with Distance-dependent Delay. (arXiv:1008.0494v1 [nlin.CD]): "

By means of numerical integration we investigate the coherent and incoherent
phases in a generalized Kuramoto model of phase-coupled oscillators with
distance-dependent delay. Preserving the topology of a complete graph, we
arrange the nodes on a square lattice while introducing finite interaction
velocity, which gives rise to non-uniform delay. It is found that such delay
facilitates incoherence and removes reentrant behavior found in models with
uniform delay. A coupling-delay phase diagram is obtained and compared with
previous results for uniform delay.

Impact of network structure on competitive evolutionary processes. (arXiv:1006.4257v1 [physics.soc-ph])

2010-07-02T04:02:00.000-07:00

Impact of network structure on competitive evolutionary processes. (arXiv:1006.4257v1 [physics.soc-ph]): "

We consider an evolutionary model in which the individuals of different
species move over a complex network and are subject to reproduction and
selection. The complementary roles of selection and diffusion produce a variety
of fixed points, whose stability depends mostly on the structure of the
underlying complex network. The proposed model can be useful to simulate
different diffusion processes which usually take place on complex topologies
and are characterized by strong competition among orthogonal species, such as
diffusion of consumer products, competition of biotypes, and selections of
languages."

Synchronization of time delay systems using variable delay with reset for enhanced security in communication. (arXiv:1007.0102v1 [nlin.CD])

2010-07-02T03:55:00.000-07:00

Synchronization of time delay systems using variable delay with reset for enhanced security in communication. (arXiv:1007.0102v1 [nlin.CD]): "

We have introduced a mechanism for synchronizing chaotic systems by one way
coupling with a variable delay that is reset at finite intervals. Here we
extend this method to time delay systems and suggest a new cryptosystem based
on this. We present the stability analysis as applied to time delay systems and
supplement this by numerical simulations in a standard time delay system like
Mackey Glass system. We extend the theory to multi- delay systems and propose a
bi channel scheme for the implementation of the scheme for communication with
enhanced security. We show that since the synchronizing channel carries
information from transmitter only at intervals of reset time, it is not
susceptible to reconstruction. The message channel being separate can be made
complex by linear combination of transmitter variable at different delay times
using mutiple delay systems. This method has the additional advantage that it
can be adjusted to be delay or anticipatory in synchronization and these
provide two additional basic keys that are independent of system delay."

Synchronization of oscillators with long range power law interactions

2010-06-22T09:10:00.000-07:00

Synchronization of oscillators with long range power law interactions: "We present analytical calculations and numerical simulations for the synchronization of oscillators interacting via a long range power law interaction on a one dimensional lattice. We have identified the critical value of the power law exponent ac across which a transition from a synchronized to an ..."

Synchronization transition in the Kuramoto model with colored noise

2010-05-20T06:20:00.000-07:00

Synchronization transition in the Kuramoto model with colored noise: "We present a linear stability analysis of the incoherent state in a system of globally coupled, identical phase oscillators subject to colored noise. In that we succeed to bridge the extreme time scales between the formerly studied and analytically solvable cases of white noise and quenched random f..."

Dynamical organization towards consensus in the Axelrod model on complex networks

2010-05-20T06:18:00.000-07:00

Dynamical organization towards consensus in the Axelrod model on complex networks: "Author(s): Beniamino Guerra, Julia Poncela, Jesús Gómez-Gardeñes, Vito Latora, and Yamir Moreno
We analyze the dynamics toward cultural consensus in the Axelrod model on scale-free networks. By looking at the microscopic dynamics of the model, we are able to show how culture traits spread across different cultural features. We compare the diffusion at the level of cultural features to the grow...
[Phys. Rev. E 81, 056105] Published Tue May 18, 2010"

Outer synchronization of coupled networks using arbitrary coupling strength

2010-05-03T02:18:00.000-07:00

Outer synchronization of coupled networks using arbitrary coupling strength: "Zhuchun Li and Xiaoping Xue
This paper mainly studies synchronization between two coupled networks, which is called outer synchronization. On the basis of Lyapunov function approach, we prove that for networks with balanced structure topology, outer synchronization can be asymptotically reached by using arbitrary coupling stre ... [Chaos 20, 023106 (2010)] published Thu Apr 22, 2010."

Synchronous solutions and their stability in nonlocally coupled phase oscillators with propagation delays. (arXiv:1003.5079v1 [nlin.AO])

2010-03-29T07:29:00.000-07:00

Synchronous solutions and their stability in nonlocally coupled phase oscillators with propagation delays. (arXiv:1003.5079v1 [nlin.AO]): "

We study the existence and stability of synchronous solutions in a continuum
field of non-locally coupled identical phase oscillators with
distance-dependent propagation delays. We present a comprehensive stability
diagram in the parameter space of the system. From the numerical results a
heuristic synchronization condition is suggested, and an analytic relation for
the marginal stability curve is obtained. We also provide an expression in the
form of a scaling relation that closely follows the marginal stability curve
over the complete range of the non-locality parameter."

EPIDEMIC SELF-SYNCHRONIZATION IN COMPLEX NETWORKS OF KURAMOTO OSCILLATORS

2010-03-27T12:44:00.000-07:00

EPIDEMIC SELF-SYNCHRONIZATION IN COMPLEX NETWORKS OF KURAMOTO OSCILLATORS

Performance of modularity maximization in practical contexts

2010-03-26T10:26:00.000-07:00

Performance of modularity maximization in practical contexts: "Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood in practical contexts. Here, we present a broad characterization of its performance in such situations. First, we revisit and clarify the r..."

Cellular Automata Networks. (arXiv:1003.4958v1 [nlin.CG])

2010-03-26T10:22:00.000-07:00

Cellular Automata Networks. (arXiv:1003.4958v1 [nlin.CG]): "

A small-world cellular automaton network has been formulated to simulate the
long-range interactions of complex networks using unconventional computing
methods in this paper. Conventional cellular automata use local updating rules.
The new type of cellular automata networks uses local rules with a fraction of
long-range shortcuts derived from the properties of small-world networks.
Simulations show that the self-organized criticality emerges naturally in the
system for a given probability of shortcuts and transition occurs as the
probability increases to some critical value indicating the small-world
behaviour of the complex automata networks. Pattern formation of cellular
automata networks and the comparison with equation-based reaction-diffusion
systems are also discussed"

Logical complexity of graphs: a survey. (arXiv:1003.4865v1 [math.CO])

2010-03-26T10:16:00.000-07:00

Logical complexity of graphs: a survey. (arXiv:1003.4865v1 [math.CO]): "

We discuss the definability of finite graphs in first-order logic with two
relation symbols for adjacency and equality of vertices. The logical depth
$D(G)$ of a graph $G$ is equal to the minimum quantifier depth of a sentence
defining $G$ up to isomorphism. The logical width $W(G)$ is the minimum number
of variables occurring in such a sentence. The logical length $L(G)$ is the
length of a shortest defining sentence. We survey known estimates for these
graph parameters and discuss their relations to other topics (such as the
efficiency of the Weisfeiler-Lehman algorithm in isomorphism testing, the
evolution of a random graph, or the contribution of Frank Ramsey to the
research on Hilbert's Entscheidungsproblem). Also, we trace the behavior of the
descriptive complexity of a graph as the logic becomes more restrictive (for
example, only definitions with a bounded number of variables or quantifier
alternations are allowed) or more expressible (after powering with counting
quantifiers)."

Fractals in Small-World Networks With Time Delay. (arXiv:1003.4949v1 [cond-mat.dis-nn])

2010-03-26T10:14:00.001-07:00

Fractals in Small-World Networks With Time Delay. (arXiv:1003.4949v1 [cond-mat.dis-nn]): "

The small-world networks recently introduced by Watts and Strogatz [Nature
393, 440 (1998)] has attracted much interests in studying the interesting
properties of the networks without time-delay. However, a signal or influence
travelling on the small-world networks often associated with time-delay
features which are very common in biological and physical networks. We develop
an analytical approach as well as numerical simulations to try to characterize
the effect of time-delay on the properties of small-world networks. An
analytical expression of the fractal dimension of the small-world networks is
given and thus compared with the results from numerical simulations. Analysis
shows that small-world networks with time-delay generally have the
multifractals property."

Chaos in Small-World Networks. (arXiv:1003.4940v1 [cond-mat.dis-nn])

2010-03-26T10:14:00.000-07:00

Chaos in Small-World Networks. (arXiv:1003.4940v1 [cond-mat.dis-nn]): "

A nonlinear small-world network model has been presented to investigate the
effect of nonlinear interaction and time delay on the dynamic properties of
small-world networks. Both numerical simulations and analytical analysis for
networks with time delay and nonlinear interaction show chaotic features in the
system response when nonlinear interaction is strong enough or the length scale
is large enough. In addition, the small-world system may behave very
differently on different scales. Time-delay parameter also has a very strong
effect on properties such as the critical length and response time of
small-world networks."

A Novel Clustering Algorithm Based Upon Games on Evolving Network. (arXiv:0812.5064v2 [cs.LG] UPDATED)

2010-03-23T03:26:00.000-07:00

A Novel Clustering Algorithm Based Upon Games on Evolving Network. (arXiv:0812.5064v2 [cs.LG] UPDATED): "

This paper introduces a model based upon games on an evolving network, and
develops three clustering algorithms according to it. In the clustering
algorithms, data points for clustering are regarded as players who can make
decisions in games. On the network describing relationships among data points,
an edge-removing-and-rewiring (ERR) function is employed to explore in a
neighborhood of a data point, which removes edges connecting to neighbors with
small payoffs, and creates new edges to neighbors with larger payoffs. As such,
the connections among data points vary over time. During the evolution of
network, some strategies are spread in the network. As a consequence, clusters
are formed automatically, in which data points with the same evolutionarily
stable strategy are collected as a cluster, so the number of evolutionarily
stable strategies indicates the number of clusters. Moreover, the experimental
results have demonstrated that data points in datasets are clustered reasonably
and efficiently, and the comparison with other algorithms also provides an
indication of the effectiveness of the proposed algorithms."

Phase Synchronization in Railway Timetables. (arXiv:1003.4012v1 [cs.DS])

2010-03-23T03:13:00.000-07:00

Phase Synchronization in Railway Timetables. (arXiv:1003.4012v1 [cs.DS]): "

Timetable construction belongs to the most important optimization problems in
public transport. Finding optimal or near-optimal timetables under the
subsidiary conditions of minimizing travel times and other criteria is a
targeted contribution to the functioning of public transport. In addition to
efficiency (given, e.g., by minimal average travel times), a significant
feature of a timetable is its robustness against delay propagation. Here we
study the balance of efficiency and robustness in long-distance railway
timetables (in particular the current long-distance railway timetable in
Germany) from the perspective of synchronization, exploiting the fact that a
major part of the trains run nearly periodically. We find that synchronization
is highest at intermediate-sized stations. We argue that this synchronization
perspective opens a new avenue towards an understanding of railway timetables
by representing them as spatio-temporal phase patterns. Robustness and
efficiency can then be viewed as properties of this phase pattern."

Indicators of the Interdisciplinarity of Journals: Diversity, Centrality, and Citations. (arXiv:1003.3613v1 [cs.DL])

2010-03-21T03:35:00.000-07:00

Indicators of the Interdisciplinarity of Journals: Diversity, Centrality, and Citations. (arXiv:1003.3613v1 [cs.DL]): "

A citation-based indicator for interdisciplinarity has been missing hitherto
among the set of available journal indicators. In this study, we investigate
betweenness centrality, entropy, the Gini coefficient, and more recently
proposed measures for diversity that combine the statistics of vectors and
distances in networks, in terms of their potential to fill this gap. The
effects of various normalizations are specified and measured using the matrix
of 8,207 journals contained in the Journal Citation Reports of the (Social)
Science Citation Index. Betweenness centrality in (1-mode) affiliations
networks provides an indicator outperforming betweenness in the (2-mode)
citation network. Entropy as a vector-based indicator performs better than the
Gini coefficient, but is sensitive to size. Science and Nature, for example,
are indicated at the top of the list. The new diversity measure provides
reasonable results when (1 - cosine) is assumed as a measure for the distance,
but results using Euclidean distances are difficult to interpret."

How opinion dynamics generates group hierarchies. (arXiv:1003.3586v1 [physics.soc-ph])

2010-03-21T03:34:00.000-07:00

How opinion dynamics generates group hierarchies. (arXiv:1003.3586v1 [physics.soc-ph]): "

We recently proposed a model coupling the evolution of the opinions of the
individual with the local network topology. The opinion dynamics is based on
the Bounded Confidence model. The social networks is based on a group concept
where each individual is totally connected to the members of its group and is
linked to the individuals of the other groups with a given probability. During
a time step, the individual has to decide between discussing with a member of
its own network and applying the opinion dynamics, or moving groups because it
has an opinion far from the average opinion of its own group. One of the main
results we obtained is that the group sizes, starting from an homogeneous
situation can be strongly heterogeneous at the equilibrium state. This kind of
heterogeneity can be identified in many real networks. In this paper we present
the complete set of behaviours that this complex model can exhibit, at group
level. In particular we will focus on the mechanisms that lead to the stability
of the groups and the appearance of heterogeneity in sizes."

Cluster synchronization in networks of coupled nonidentical dynamical systems

2010-03-18T03:36:00.000-07:00

Cluster synchronization in networks of coupled nonidentical dynamical systems: "Wenlian Lu, Bo Liu, and Tianping Chen
In this paper, we study cluster synchronization in networks of coupled nonidentical dynamical systems. The vertices in the same cluster have the same dynamics of uncoupled node system but the uncoupled node systems in different clusters are different. We present conditions guaranteeing cluster synch ... [Chaos 20, 013120 (2010)] published Wed Mar 17, 2010."

Identification of Starting Points in Sampling of Complex Networks. (arXiv:1003.3256v1 [physics.comp-ph])

2010-03-18T03:32:00.000-07:00

Identification of Starting Points in Sampling of Complex Networks. (arXiv:1003.3256v1 [physics.comp-ph]): "

Because of their large size, several real-world complex networks can only be
represented and computationally handled in a sampled version. One of the most
common sampling schemes is breadth-first where, after starting from a given
node, its neighbors are taken, and then the neighbors of neighbors, and so on.
Therefore, it becomes an important issue, given a specific network sampled by
the breadth-first method, to try to identify the original node. In addition to
providing a clue about how the sampling was performed, the identification of
the original node also paves the way for the reconstruction of the sampling
dynamics provided the original networks is available. In the current article,
we propose and validate a new and effective methodology for the identification
of the original nodes. The method is based on the calculation of the
accessibility of the nodes in the sampled network. We show that the original
node tends to have the highest values of accessibility. The potential of the
methodology is illustrated with respect to three theoretical complex networks
model as well as a real-world network, namely the United States patent network."

Emergence from Symmetry: A New Type of Cellular Automata. (arXiv:1003.3394v1 [nlin.CG])

2010-03-18T03:31:00.000-07:00

Emergence from Symmetry: A New Type of Cellular Automata. (arXiv:1003.3394v1 [nlin.CG]): "

In this paper, a different perspective of constructing the CA models is
proposed. The kernel, Local Symmetric Distribution Principle, relates some
fundamental concepts in physics, which maybe raise a wide interest. With a rich
palette of configurations, this model also hints its capability of universal
computation."

Random graph states, maximal flow and Fuss-Catalan distributions. (arXiv:1003.3075v1 [quant-ph])

2010-03-17T02:56:00.000-07:00

Random graph states, maximal flow and Fuss-Catalan distributions. (arXiv:1003.3075v1 [quant-ph]): "

For any graph consisting of $k$ vertices and $m$ edges we construct an
ensemble of random pure quantum states which describe a system composed of $2m$
subsystems. Each edge of the graph represents a bi-partite, maximally entangled
state. Each vertex represents a random unitary matrix generated according to
the Haar measure, which describes the coupling between subsystems. Dividing all
subsystems into two parts, one may study entanglement with respect to this
partition. A general technique to derive an expression for the average
entanglement entropy of random pure states associated to a given graph is
presented. Our technique relies on Weingarten calculus and flow problems. We
analyze statistical properties of spectra of such random density matrices and
show for which cases they are described by the free Poissonian
(Marchenko-Pastur) distribution. We derive a discrete family of generalized,
Fuss-Catalan distributions and explicitly construct graphs which lead to
ensembles of random states characterized by these novel distributions of
eigenvalues."

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks. (arXiv:1003.3085v1 [math.CO])

2010-03-17T02:54:00.000-07:00

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks. (arXiv:1003.3085v1 [math.CO]): "

Consider an undirected graph $G = (VG, EG)$ and a set of six \emph{terminals}
$T = \set{s_1, s_2, s_3, t_1, t_2, t_3} \subseteq VG$. The goal is to find a
collection $\calP$ of three edge-disjoint paths $P_1$, $P_2$, and $P_3$, where
$P_i$ connects nodes $s_i$ and $t_i$ ($i = 1, 2, 3$). Results obtained by
Robertson and Seymour by graph minor techniques imply a polynomial time
solvability of this problem. The time bound of their algorithm is $O(m^3)$
(hereinafter we assume $n := \abs{VG}$, $m := \abs{EG}$, $n = O(m)$). In this
paper we consider a special, \emph{Eulerian} case of $G$ and $T$. Namely,
construct the \emph{demand graph} $H = (VG, \set{s_1t_1, s_2t_2, s_3t_3})$. The
edges of $H$ correspond to the desired paths in $\calP$. In the Eulerian case
the degrees of all nodes in the (multi-) graph $G + H$ ($ = (VG, EG \cup EH)$)
are even. Schrijver showed that, under the assumption of Eulerianess, cut
conditions provide a criterion for the existence of $\calP$. This, in
particular, implies that checking for existence of $\calP$ can be done in
$O(m)$ time. Our result is a combinatorial $O(m)$-time algorithm that
constructs $\calP$ (if the latter exists).

Synchronization of oscillators with long range power law interactions. (arXiv:1003.1447v1 [cond-mat.stat-mech] CROSS LISTED)

2010-03-16T10:13:00.000-07:00

Synchronization of oscillators with long range power law interactions. (arXiv:1003.1447v1 [cond-mat.stat-mech] CROSS LISTED): "

We present analytical calculations and numerical simulations for the
synchronization of oscillators interacting via a long range power law
interaction on a one dimensional lattice. We have identified the critical value
of the power law exponent $\alpha_c$ across which a transition from a
synchronized to an unsynchronized state takes place for a sufficiently strong
but finite coupling strength in the large system limit. We find $\alpha_c=3/2$.
Frequency entrainment and phase ordering are discussed as a function of $\alpha
\geq 1$. The calculations are performed using an expansion about the aligned
phase state (spin-wave approximation) and a coarse graining approach. We also
generalize the spin-wave results to the {\it d}-dimensional problem."

Chimeras in a Network of Three Oscillator Populations with Varying Network Topology. (arXiv:1003.2916v1 [nlin.AO])

2010-03-16T10:12:00.000-07:00

Chimeras in a Network of Three Oscillator Populations with Varying Network Topology. (arXiv:1003.2916v1 [nlin.AO]): "

We study a network of three populations of coupled phase oscillators with
identical frequencies. The populations interact nonlocally, in the sense that
all oscillators are coupled to one another, but more weakly to those in
neighboring populations than to those in their own population. Using this
system as a model system, we discuss the influence of network topology on the
existence of so called chimera states for the first time. In this context, the
network with three populations represents an interesting case because the
populations may either be connected as a triangle, or as a chain, thereby
representing the simplest discrete network of either a ring or a line segment
of oscillator populations. We introduce a special parameter that allows us to
study the effect of breaking the triangular network structure, and to vary the
network symmetry continuously such that it becomes more and more chain-like. By
showing that chimera states only exist for a bounded set of parameter values we
demonstrate that their existence depends strongly on the underlying network
structures. We conclude that chimeras exist on networks with a chain-like
character, which indicates that it might be possible to observe chimeras on a
continuous line segment of oscillators."

Bistable Chimera Attractors on a Triangular Network of Oscillator Populations. (arXiv:1003.2827v1 [nlin.AO])

2010-03-16T10:08:00.000-07:00

Bistable Chimera Attractors on a Triangular Network of Oscillator Populations. (arXiv:1003.2827v1 [nlin.AO]): "

We study a triangular network of three populations of coupled phase
oscillators with identical frequencies. The populations interact nonlocally, in
the sense that all oscillators are coupled to one another, but more weakly to
those in neighboring populations than to those in their own population. This
triangular network is the simplest discretization of a continuous ring of
oscillators. Yet it displays an unexpectedly different behavior: in contrast to
the lone stable chimera observed in continuous rings of oscillators, we find
that this system exhibits \emph{two coexisting stable chimeras}. Both chimeras
are, as usual, born through a saddle node bifurcation. As the coupling becomes
increasingly local in nature they lose stability through a Hopf bifurcation,
giving rise to breathing chimeras, which in turn get destroyed through a
homoclinic bifurcation. Remarkably, one of the chimeras reemerges by a reversal
of this scenario as we further increase the locality of the coupling, until it
is annihilated through another saddle node bifurcation."

Predicting Positive and Negative Links in Online Social Networks. (arXiv:1003.2429v1 [physics.soc-ph])

2010-03-15T07:09:00.000-07:00

Predicting Positive and Negative Links in Online Social Networks. (arXiv:1003.2429v1 [physics.soc-ph]): "

We study online social networks in which relationships can be either positive
(indicating relations such as friendship) or negative (indicating relations
such as opposition or antagonism). Such a mix of positive and negative links
arise in a variety of online settings; we study datasets from Epinions,
Slashdot and Wikipedia. We find that the signs of links in the underlying
social networks can be predicted with high accuracy, using models that
generalize across this diverse range of sites. These models provide insight
into some of the fundamental principles that drive the formation of signed
links in networks, shedding light on theories of balance and status from social
psychology; they also suggest social computing applications by which the
attitude of one user toward another can be estimated from evidence provided by
their relationships with other members of the surrounding social network."

Signed Networks in Social Media. (arXiv:1003.2424v1 [physics.soc-ph])

2010-03-15T07:08:00.000-07:00

Signed Networks in Social Media. (arXiv:1003.2424v1 [physics.soc-ph]): "

Relations between users on social media sites often reflect a mixture of
positive (friendly) and negative (antagonistic) interactions. In contrast to
the bulk of research on social networks that has focused almost exclusively on
positive interpretations of links between people, we study how the interplay
between positive and negative relationships affects the structure of on-line
social networks. We connect our analyses to theories of signed networks from
social psychology. We find that the classical theory of structural balance
tends to capture certain common patterns of interaction, but that it is also at
odds with some of the fundamental phenomena we observe --- particularly related
to the evolving, directed nature of these on-line networks. We then develop an
alternate theory of status that better explains the observed edge signs and
provides insights into the underlying social mechanisms. Our work provides one
of the first large-scale evaluations of theories of signed networks using
on-line datasets, as well as providing a perspective for reasoning about social
media sites."

Spontaneous Synchrony Breaking. (arXiv:1003.2465v1 [nlin.CD])

2010-03-15T07:06:00.000-07:00

Spontaneous Synchrony Breaking. (arXiv:1003.2465v1 [nlin.CD]): "

Research on synchronization of coupled oscillators has helped explain how
uniform behavior emerges in populations of non-uniform systems. But explaining
how uniform populations engage in sustainable non-uniform synchronization may
prove to be just as fascinating."

Modeling the basin of attraction as a two-dimensional manifold from experimental data: Applications to balance in humans | Issue 1 - Chaos

2010-03-13T02:35:00.000-08:00

Modeling the basin of attraction as a two-dimensional manifold from experimental data: Applications to balance in humans | Issue 1 - Chaos: "We present a method of modeling the basin of attraction as a three-dimensional function describing a two-dimensional manifold on which the dynamics of the system evolves from experimental time series data. Our method is based on the density of the data set and uses numerical optimization and data modeling tools. We also show how to obtain analytic curves that describe both the contours and the boundary of the basin. Our method is applied to the problem of regaining balance after perturbation from quiet vertical stance using data of an elite athlete. Our method goes beyond the statistical description of the experimental data, providing a function that describes the shape of the basin of attraction. To test its robustness, our method has also been applied to two different data sets of a second subject and no significant differences were found between the contours of the calculated basin of attraction for the different data sets. The proposed method has many uses in a wide variety of areas, not just human balance for which there are many applications in medicine, rehabilitation, and sport."

Physical Review E - Loops and multiple edges in modularity maximization of networks

2010-03-13T02:34:00.000-08:00

Physical Review E -
Loops and multiple edges in modularity maximization of networks: "The modularity maximization model proposed by Newman and Girvan for the identification of communities in networks works for general graphs possibly with loops and multiple edges. However, the applications usually correspond to simple graphs. These graphs are compared to a null model where the degree distribution is maintained but edges are placed at random. Therefore, in this null model there will be loops and possibly multiple edges. Sharp bounds on the expected number of loops, and their impact on the modularity, are derived. Then, building upon the work of Massen and Doye, but using algebra rather than simulation, we propose modified null models associated with graphs without loops but with multiple edges, graphs with loops but without multiple edges and graphs without loops nor multiple edges. We validate our models by using the exact algorithm for clique partitioning of Grötschel and Wakabayashi."

Spontaneous mode switching in coupled oscillators competing for constant amounts of resources

2010-03-11T02:53:00.000-08:00

Spontaneous mode switching in coupled oscillators competing for constant amounts of resources: "Yoshito Hirata, Masashi Aono, Masahiko Hara, and Kazuyuki Aihara
We propose a widely applicable scheme of coupling that models competitions among dynamical systems for fixed amounts of resources. Two oscillators coupled in this way synchronize in antiphase. Three oscillators coupled circularly show a number of oscillation modes such as rotation and partially in-p ... [Chaos 20, 013117 (2010)] published Wed Mar 10, 2010."

Cellular Automata, PDEs, and Pattern Formation. (arXiv:1003.1983v1 [nlin.CG])

2010-03-11T02:19:00.000-08:00

Cellular Automata, PDEs, and Pattern Formation. (arXiv:1003.1983v1 [nlin.CG]): "

State-of-the-art review of cellular automata, cellular automata for partial
differential equations, differential equations for cellular automata and
pattern formation in biology and engineering."

More than two equally probable variants of signal in Kauffman networks as an important overlooked case, negative feedbacks allow life in chaos. (arXiv

2010-03-11T02:18:00.001-08:00

More than two equally probable variants of signal in Kauffman networks as an important overlooked case, negative feedbacks allow life in chaos. (arXiv:1003.1988v1 [cond-mat.dis-nn]): "

There are three main aims of this paper. 1- I explain reasons why I await
life to lie significantly deeper in chaos than Kauffman approach does, however
still in boundary area near `the edge of chaos and order'. The role of negative
feedbacks in stability of living objects is main of those reasons. In
Kauffman's approach regulation using negative feedbacks is not considered
sufficiently, e.g. in gene regulatory model based on Boolean networks, which
indicates therefore not proper source of stability. Large damage avalanche is
available only in chaotic phase. It models death in all living objects
necessary for Darwinian elimination. It is the first step of my approach
leading to structural tendencies which are effects of adaptive evolution of
dynamic complex (maturely chaotic) networks. 2- Introduction of s>=2 equally
probable variants of signal (state of node in Kauffman network) as
interpretively based new statistical mechanism (RSN) instead of the bias p -
probability of one of signal variants used in RBN family and RNS. It is also
different than RWN model. For this mechanism which can be treated as very
frequent, ordered phase occurs only in exceptional cases but for this approach
the chaotic phase is investigated. Annealed approximation expectations and
simulations of damage spreading for different network types (similar to CRBN,
FSRBN and EFRBN but with s>=2) are described. Degree of order in chaotic phase
in dependency of network parameters and type is discussed. By using such order
life evolve. 3- A simplified algorithm called `reversed-annealed' for
statistical simulation of damage spreading is described. It is used for
simulations presented in this and next papers describing my approach."

Synchronization Transition of Identical Phase Oscillators in a Directed Small-World Network. (arXiv:1003.2020v1 [cond-mat.dis-nn])

2010-03-11T02:18:00.000-08:00

Synchronization Transition of Identical Phase Oscillators in a Directed Small-World Network. (arXiv:1003.2020v1 [cond-mat.dis-nn]): "

We numerically study a directed small-world network consisting of
attractively coupled, identical phase oscillators. While complete
synchronization is always stable, it is not always reachable from random
initial conditions. Depending on the shortcut density and on the asymmetry of
the phase coupling function, there exists a regime of persistent chaotic
dynamics. By increasing the density of shortcuts or decreasing the asymmetry of
the phase coupling function, we observe a discontinuous transition in the
ability of the system to synchronize. Using a control technique, we identify
the bifurcation scenario of the order parameter. We also discuss the relation
between dynamics and topology and remark on the similarity of the
synchronization transition to directed percolation."

Optimizing transport efficiency on scale-free networks through assortative or dissortative topology

2010-03-10T13:36:00.000-08:00

Optimizing transport efficiency on scale-free networks through assortative or dissortative topology: "Author(s): Yu-hua Xue, Jian Wang, Liang Li, Daren He, and Bambi Hu
We find that transport on scale-free random networks depends strongly on degree-correlated network topologies whereas transport on Erdös-Rényi networks is insensitive to the degree correlation. An approach for the tuning of scale-free network transport efficiency through assortative or dissortativ...
[Phys. Rev. E 81, 037101] Published Wed Mar 10, 2010"

Random Texts Do Not Exhibit the Real Zipf's Law-Like Rank Distribution

2010-03-09T07:28:00.000-08:00

Random Texts Do Not Exhibit the Real Zipf's Law-Like Rank Distribution: "Background
Zipf's law states that the relationship between the frequency of a word in a text and its rank (the most frequent word has rank , the 2nd most frequent word has rank ,…) is approximately linear when plotted on a double logarithmic scale. It has been argued that the law is not a relevant or useful property of language because simple random texts - constructed by concatenating random characters including blanks behaving as word delimiters - exhibit a Zipf's law-like word rank distribution.
Methodology/Principal Findings
In this article, we examine the flaws of such putative good fits of random texts. We demonstrate - by means of three different statistical tests - that ranks derived from random texts and ranks derived from real texts are statistically inconsistent with the parameters employed to argue for such a good fit, even when the parameters are inferred from the target real text. Our findings are valid for both the simplest random texts composed of equally likely characters as well as more elaborate and realistic versions where character probabilities are borrowed from a real text.

Conclusions/Significance
The good fit of random texts to real Zipf's law-like rank distributions has not yet been established. Therefore, we suggest that Zipf's law might in fact be a fundamental law in natural languages."

Noise-induced synchronization in bidirectionally coupled type-I neurons

2010-03-09T07:27:00.000-08:00

Noise-induced synchronization in bidirectionally coupled type-I neurons: "Authors: N. Malik, B. Ashok and J. Balakrishnan.
The European Physical Journal B
Published online: 9/3/2010"

Synchronization Transition in the Kuramoto Model with Colored Noise. (arXiv:1003.1549v1 [cond-mat.dis-nn])

2010-03-09T06:07:00.000-08:00

Synchronization Transition in the Kuramoto Model with Colored Noise. (arXiv:1003.1549v1 [cond-mat.dis-nn]): "

We present a linear stability analysis of the incoherent state in a system of
globally coupled, identical phase oscillators subject to colored noise. In that
we succeed to bridge the extreme time scales between the formerly studied and
analytically solvable cases of white noise and quenched random frequencies."

A New Clustering Approach based on Page's Path Similarity for Navigation Patterns Mining. (arXiv:1003.1450v1 [cs.OH])

2010-03-09T06:04:00.000-08:00

A New Clustering Approach based on Page's Path Similarity for Navigation Patterns Mining. (arXiv:1003.1450v1 [cs.OH]): "

In recent years, predicting the user's next request in web navigation has
received much attention. An information source to be used for dealing with such
problem is the left information by the previous web users stored at the web
access log on the web servers. Purposed systems for this problem work based on
this idea that if a large number of web users request specific pages of a
website on a given session, it can be concluded that these pages are satisfying
similar information needs, and therefore they are conceptually related. In this
study, a new clustering approach is introduced that employs logical path
storing of a website pages as another parameter which is regarded as a
similarity parameter and conceptual relation between web pages. The results of
simulation have shown that the proposed approach is more than others precise in
determining the clusters."

Evolution of Feedback Loops in Oscillatory Systems. (arXiv:1003.1231v1 [q-bio.QM])

2010-03-08T01:47:00.000-08:00

Evolution of Feedback Loops in Oscillatory Systems. (arXiv:1003.1231v1 [q-bio.QM]): "

Feedback loops are major components of biochemical systems. Many systems show
multiple such (positive or negative) feedback loops. Nevertheless, very few
quantitative analyses address the question how such multiple feedback loops
evolved. Based on published models from the mitotic cycle in embryogenesis, we
build a few case studies. Using a simple core architecture (transcription,
phosphorylation and degradation), we define oscillatory models having either
one positive feedback or one negative feedback, or both loops. With these
models, we address the following questions about evolvability: could a system
evolve from a simple model to a more complex one with a continuous transition
in the parameter space? How do new feedback loops emerge without disrupting the
proper function of the system? Our results show that progressive formation of a
second feedback loop is possible without disturbing existing oscillatory
behavior. For this process, the parameters of the system have to change during
evolution to maintain predefined properties of oscillations like period and
amplitude."

From Frequency to Meaning: Vector Space Models of Semantics. (arXiv:1003.1141v1 [cs.CL])

2010-03-08T01:45:00.000-08:00

From Frequency to Meaning: Vector Space Models of Semantics. (arXiv:1003.1141v1 [cs.CL]): "

Computers understand very little of the meaning of human language. This
profoundly limits our ability to give instructions to computers, the ability of
computers to explain their actions to us, and the ability of computers to
analyse and process text. Vector space models (VSMs) of semantics are beginning
to address these limits. This paper surveys the use of VSMs for semantic
processing of text. We organize the literature on VSMs according to the
structure of the matrix in a VSM. There are currently three broad classes of
VSMs, based on term-document, word-context, and pair-pattern matrices, yielding
three classes of applications. We survey a broad range of applications in these
three categories and we take a detailed look at a specific open source project
in each category. Our goal in this survey is to show the breadth of
applications of VSMs for semantics, to provide a new perspective on VSMs for
those who are already familiar with the area, and to provide pointers into the
literature for those who are less familiar with the field."

Minimum Spanning Tree on Spatio-Temporal Networks. (arXiv:1003.1251v1 [cs.DS])

2010-03-08T01:40:00.000-08:00

Minimum Spanning Tree on Spatio-Temporal Networks. (arXiv:1003.1251v1 [cs.DS]): "

Given a spatio-temporal network (ST network) whose edge properties vary with
time, a time-sub-interval minimum spanning tree (TSMST) is a collection of
distinct minimum spanning trees of the ST network. The TSMST computation
problem aims to identify a collection of distinct minimum spanning trees and
their respective time-sub-intervals under the constraint that the edge weight
functions are piecewise linear. This is an important problem in ST network
application domains such as wireless sensor networks (e.g., energy efficient
routing). Computing TSMST is challenging because the ranking of candidate
spanning trees is non-stationary over a given time interval. Existing methods
such as dynamic graph algorithms and kinetic data structures assume separable
edge weight functions. In contrast, this paper proposes novel algorithms to
find TSMST for large ST networks by accounting for both separable and
non-separable piecewise linear edge weight functions. The algorithms are based
on the ordering of edges in edge-order-intervals and intersection points of
edge weight functions."

Modeling discrete combinatorial systems as alphabetic bipartite networks: Theory and applications

2010-03-06T06:10:00.000-08:00

Modeling discrete combinatorial systems as alphabetic bipartite networks: Theory and applications: "Author(s): Monojit Choudhury, Niloy Ganguly, Abyayananda Maiti, Animesh Mukherjee, Lutz Brusch, Andreas Deutsch, and Fernando Peruani
Genes and human languages are discrete combinatorial systems (DCSs), in which the basic building blocks are finite sets of elementary units: nucleotides or codons in a DNA sequence, and letters or words in a language. Different combinations of these finite units give rise to potentially infinite num...
[Phys. Rev. E 81, 036103] Published Fri Mar 05, 2010"

Detecting couplings between interacting oscillators with time-varying basic frequencies: Instantaneous wavelet bispectrum and information theoretic ap

2010-03-06T06:09:00.000-08:00

Detecting couplings between interacting oscillators with time-varying basic frequencies: Instantaneous wavelet bispectrum and information theoretic approach: "Author(s): Janez Jamšek, Milan Paluš, and Aneta Stefanovska
In the natural world, the properties of interacting oscillatory systems are not constant, but evolve or fluctuating continuously in time. Thus, the basic frequencies of the interacting oscillators are time varying, which makes the system analysis complex. For studying their interactions we propose a...
[Phys. Rev. E 81, 036207] Published Fri Mar 05, 2010"

A Rapid Method for Characterization of Protein Relatedness Using Feature Vectors

2010-03-05T03:24:00.000-08:00

A Rapid Method for Characterization of Protein Relatedness Using Feature Vectors: "

We propose a feature vector approach to characterize the variation in large data sets of biological sequences. Each candidate sequence produces a single feature vector constructed with the number and location of amino acids or nucleic acids in the sequence. The feature vector characterizes the distance between the actual sequence and a model of a theoretical sequence based on the binomial and uniform distributions. This method is distinctive in that it does not rely on sequence alignment for determining protein relatedness, allowing the user to visualize the relationships within a set of proteins without making a priori assumptions about those proteins. We apply our method to two large families of proteins: protein kinase C, and globins, including hemoglobins and myoglobins. We interpret the high-dimensional feature vectors using principal components analysis and agglomerative hierarchical clustering. We find that the feature vector retains much of the information about the original sequence. By using principal component analysis to extract information from collections of feature vectors, we are able to quickly identify the nature of variation in a collection of proteins. Where collections are phylogenetically or functionally related, this is easily detected. Hierarchical agglomerative clustering provides a means of constructing cladograms from the feature vector output."

Syntactic Topic Models. (arXiv:1002.4665v1 [cs.CL] CROSS LISTED)

2010-03-05T03:21:00.000-08:00

Syntactic Topic Models. (arXiv:1002.4665v1 [cs.CL] CROSS LISTED): "

The syntactic topic model (STM) is a Bayesian nonparametric model of language
that discovers latent distributions of words (topics) that are both
semantically and syntactically coherent. The STM models dependency parsed
corpora where sentences are grouped into documents. It assumes that each word
is drawn from a latent topic chosen by combining document-level features and
the local syntactic context. Each document has a distribution over latent
topics, as in topic models, which provides the semantic consistency. Each
element in the dependency parse tree also has a distribution over the topics of
its children, as in latent-state syntax models, which provides the syntactic
consistency. These distributions are convolved so that the topic of each word
is likely under both its document and syntactic context. We derive a fast
posterior inference algorithm based on variational methods. We report
qualitative and quantitative studies on both synthetic data and hand-parsed
documents. We show that the STM is a more predictive model of language than
current models based only on syntax or only on topics."

Supervised Topic Models. (arXiv:1003.0783v1 [stat.ML])

2010-03-04T02:32:00.000-08:00

Supervised Topic Models. (arXiv:1003.0783v1 [stat.ML]): "

We introduce supervised latent Dirichlet allocation (sLDA), a statistical
model of labelled documents. The model accommodates a variety of response
types. We derive an approximate maximum-likelihood procedure for parameter
estimation, which relies on variational methods to handle intractable posterior
expectations. Prediction problems motivate this research: we use the fitted
model to predict response values for new documents. We test sLDA on two
real-world problems: movie ratings predicted from reviews, and the political
tone of amendments in the U.S. Senate based on the amendment text. We
illustrate the benefits of sLDA versus modern regularized regression, as well
as versus an unsupervised LDA analysis followed by a separate regression."

Information-Sharing and Privacy in Social Networks. (arXiv:1003.0469v1 [cs.GT] CROSS LISTED)

2010-03-04T02:29:00.001-08:00

Information-Sharing and Privacy in Social Networks. (arXiv:1003.0469v1 [cs.GT] CROSS LISTED): "

We present a new model for reasoning about the way information is shared
among friends in a social network, and the resulting ways in which it spreads.
Our model formalizes the intuition that revealing personal information in
social settings involves a trade-off between the benefits of sharing
information with friends, and the risks that additional gossiping will
propagate it to people with whom one is not on friendly terms. We study the
behavior of rational agents in such a situation, and we characterize the
existence and computability of stable information-sharing networks, in which
agents do not have an incentive to change the partners with whom they share
information. We analyze the implications of these stable networks for social
welfare, and the resulting fragmentation of the social network."

Centrality scaling in large networks. (arXiv:1003.0692v1 [physics.soc-ph])

2010-03-04T02:29:00.000-08:00

Centrality scaling in large networks. (arXiv:1003.0692v1 [physics.soc-ph]): "

Betweenness centrality lies at the core of both transport and structural
vulnerability properties of complex networks, however, it is computationally
costly, and its measurement for networks with millions of nodes is near
impossible. By introducing a multiscale decomposition of shortest paths, we
show that the contributions to betweenness coming from geodesics not longer
than L obey a characteristic scaling vs L, which can be used to predict the
distribution of the full centralities. The method is also illustrated on a
real-world social network of 5.5*10^6 nodes and 2.7*10^7 links."

Phase transition in non-linear random networks. (arXiv:1003.0871v1 [nlin.AO])

2010-03-04T02:28:00.001-08:00

Phase transition in non-linear random networks. (arXiv:1003.0871v1 [nlin.AO]): "

We discuss the complex dynamics of a non-linear random networks model, as a
function of the connectivity k between the elements of the network. We show
that this class of networks exhibit an order-chaos phase transition for a
critical connectivity k = 2. Also, we show that both, pairwise correlation and
complexity measures are maximized in dynamically critical networks. These
results are in good agreement with the previously reported studies on random
Boolean networks and random threshold networks, and show once again that
critical networks provide an optimal coordination of diverse behavior."

Boolean delay equations on networks: An application to economic damage propagation. (arXiv:1003.0793v1 [nlin.CG])

2010-03-04T02:28:00.000-08:00

Boolean delay equations on networks: An application to economic damage propagation. (arXiv:1003.0793v1 [nlin.CG]): "

We introduce economic models based on Boolean Delay Equations: this formalism
makes easier to take into account the complexity of the interactions between
firms and is particularly appropriate for studying the propagation of an
initial damage due to a catastrophe. Here we concentrate on simple cases, which
allow to understand the effects of multiple concurrent production paths as well
as the presence of stochasticity in the path time lengths or in the network
structure.

In absence of flexibility, the shortening of production of a single firm in
an isolated network with multiple connections usually ends up by attaining a
finite fraction of the firms or the whole economy, whereas the interactions
with the outside allow a partial recovering of the activity, giving rise to
periodic solutions with waves of damage which propagate across the structure.
The damage propagation speed is strongly dependent upon the topology. The
existence of multiple concurrent production paths does not necessarily imply a
slowing down of the propagation, which can be as fast as the shortest path."

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems. (arXiv:1003.0722v1 [cs.DS])

2010-03-04T02:26:00.000-08:00

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems. (arXiv:1003.0722v1 [cs.DS]): "

We consider the problem of constructing optimal decision trees: given a
collection of tests which can disambiguate between a set of $m$ possible
diseases, each test having a cost, and the a-priori likelihood of the patient
having any particular disease, what is a good adaptive strategy to perform
these tests to minimize the expected cost to identify the disease? We settle
the approximability of this problem by giving a tight $O(\log m)$-approximation
algorithm. We also consider a more substantial generalization, the Adaptive TSP
problem. Given an underlying metric space, a random subset $S$ of cities is
drawn from a known distribution, but $S$ is initially unknown to us--we get
information about whether any city is in $S$ only when we visit the city in
question. What is a good adaptive way of visiting all the cities in the random
subset $S$ while minimizing the expected distance traveled? For this problem,
we give the first poly-logarithmic approximation, and show that this algorithm
is best possible unless we can improve the approximation guarantees for the
well-known group Steiner tree problem."

Route to noise-induced synchronization in an ensemble of uncoupled chaotic systems

2010-03-03T15:31:00.000-08:00

Route to noise-induced synchronization in an ensemble of uncoupled chaotic systems: "Author(s): Yan Wang, Ying-Cheng Lai, and Zhigang Zheng
We investigate the route to synchronization in an ensemble of uncoupled chaotic oscillators under common noise. Previous works have demonstrated that, as the common-noise amplitude is increased, both chaotic phase synchronization and complete synchronization can occur. Our study reveals an intermedi...
[Phys. Rev. E 81, 036201] Published Wed Mar 03, 2010"

Linguistic Geometries for Unsupervised Dimensionality Reduction. (arXiv:1003.0628v1 [cs.CL])

2010-03-03T02:18:00.000-08:00

Linguistic Geometries for Unsupervised Dimensionality Reduction. (arXiv:1003.0628v1 [cs.CL]): "

Text documents are complex high dimensional objects. To effectively visualize
such data it is important to reduce its dimensionality and visualize the low
dimensional embedding as a 2-D or 3-D scatter plot. In this paper we explore
dimensionality reduction methods that draw upon domain knowledge in order to
achieve a better low dimensional embedding and visualization of documents. We
consider the use of geometries specified manually by an expert, geometries
derived automatically from corpus statistics, and geometries computed from
linguistic resources."

Measurement Invariance, Entropy, and Probability. (arXiv:1003.0031v1 [q-bio.QM])

2010-03-02T02:05:00.001-08:00

Measurement Invariance, Entropy, and Probability. (arXiv:1003.0031v1 [q-bio.QM]): "

We show that the natural scaling of measurement for a particular problem
defines the most likely probability distribution of observations taken from
that measurement scale. Our approach extends the method of maximum entropy to
use measurement scale as a type of information constraint. We argue that a very
common measurement scale is linear at small magnitudes grading into logarithmic
at large magnitudes, leading to observations that often follow Student's
probability distribution which has a Gaussian shape for small fluctuations from
the mean and a power law shape for large fluctuations from the mean. An inverse
scaling often arises in which measures naturally grade from logarithmic to
linear as one moves from small to large magnitudes, leading to observations
that often follow a gamma probability distribution. A gamma distribution has a
power law shape for small magnitudes and an exponential shape for large
magnitudes. The two measurement scales are natural inverses connected by the
Laplace integral transform. This inversion connects the two major scaling
patterns commonly found in nature. We also show that superstatistics is a
special case of an integral transform, and thus can be understood as a
particular way in which to change the scale of measurement. Incorporating
information about measurement scale into maximum entropy provides a general
approach to the relations between measurement, information and probability."

A Condition for Cooperation in a Game on Complex Networks. (arXiv:1003.0088v1 [physics.soc-ph])

2010-03-02T02:05:00.000-08:00

A Condition for Cooperation in a Game on Complex Networks. (arXiv:1003.0088v1 [physics.soc-ph]): "

We study a condition of favoring cooperation in a prisoner's dilemma game on
complex networks. There are two kinds of players: cooperators and defectors.
Cooperators pay a benefit b to their neighbors at a cost c, while defectors
only receive benefit. The game is done under weak selection and death-birth
update. Although it has been well recognized that b/c> <k> is the condition of
favoring cooperation, we find that b/c> <knn> is a much better approximate
condition. We also show that among the representative networks-regular, random,
and scale free-a regular network favors cooperation the most, while a
scale-free network favors it the least. In an ideal scale-free network,
cooperation is unfeasible. Whether a scale-free network favors cooperation
depends on the details of the games."

Opinion dynamics with confidence threshold: an alternative to the Axelrod model. (arXiv:1003.0115v1 [math.PR])

2010-03-02T02:04:00.001-08:00

Opinion dynamics with confidence threshold: an alternative to the Axelrod model. (arXiv:1003.0115v1 [math.PR]): "

The voter model and the Axelrod model are two of the main stochastic
processes that describe the spread of opinions on networks. The former includes
social influence, the tendency of individuals to become more similar when they
interact, while the latter also accounts for homophily, the tendency to
interact more frequently with individuals which are more similar. The Axelrod
model has been extensively studied during the past ten years based on numerical
simulations. In contrast, we give rigorous analytical results for a
generalization of the voter model that is closely related to the Axelrod model
as it combines social influence and confidence threshold, which is modeled
somewhat similarly to homophily. Each vertex of the network, represented by a
finite connected graph, is characterized by an opinion and may interact with
its adjacent vertices. Like the voter model, an interaction results in an
agreement between both interacting vertices -- social influence -- but unlike
the voter model, an interaction takes place if and only if the vertices'
opinions are within a certain distance -- confidence threshold. In a
deterministic static approach, we first give lower and upper bounds for the
maximum number of opinions that can be supported by the network as a function
of the confidence threshold and various characteristics of the graph. The
number of opinions coexisting at equilibrium is then investigated in a
probabilistic dynamic approach for the stochastic process starting from a
random configuration ..."

Judging Model Reduction of Chaotic Systems via Optimal Shadowing Criteria. (arXiv:1003.0254v1 [nlin.CD])

2010-03-02T02:04:00.000-08:00

Judging Model Reduction of Chaotic Systems via Optimal Shadowing Criteria. (arXiv:1003.0254v1 [nlin.CD]): "

A common goal in the study of high dimensional and complex system is to model
the system by a low order representation. In this letter we propose a general
approach for assessing the quality of a reduced order model for high
dimensional chaotic systems. The key of this approach is the use of optimal
shadowing, combined with dimensionality reduction techniques. Rather than
quantify the quality of a model based on the quality of predictions, which can
be irrelevant for chaotic systems since even excellent models can do poorly, we
suggest that a good model should allow shadowing by modeled data for long
times; this principle leads directly to an optimal shadowing criterion of model
reduction. This approach overcomes the usual difficulties encountered by
traditional methods which either compare systems of the same size by
normed-distance in the functional space, or measure how close an orbit
generated by a model is to the observed data. Examples include interval
arithmetic computations to validate the optimal shadowing."

A Contextual-Bandit Approach to Personalized News Article Recommendation. (arXiv:1003.0146v1 [cs.LG])

2010-03-02T02:01:00.001-08:00

A Contextual-Bandit Approach to Personalized News Article Recommendation. (arXiv:1003.0146v1 [cs.LG]): "

Personalized web services strive to adapt their services (advertisements,
news articles, etc) to individual users by making use of both content and user
information. Despite a few recent advances, this problem remains challenging
for at least two reasons. First, web service is featured with dynamically
changing pools of content, rendering traditional collaborative filtering
methods inapplicable. Second, the scale of most web services of practical
interest calls for solutions that are both fast in learning and computation.

In this work, we model personalized recommendation of news articles as a
contextual bandit problem, a principled approach in which a learning algorithm
sequentially selects articles to serve users based on contextual information
about the users and articles, while simultaneously adapting its
article-selection strategy based on user-click feedback to maximize total user
clicks.

The contributions of this work are three-fold. First, we propose a new,
general contextual bandit algorithm that is computationally efficient and well
motivated from learning theory. Second, we argue that any bandit algorithm can
be reliably evaluated offline using previously recorded random traffic.
Finally, using this offline evaluation method, we successfully applied our new
algorithm to a Yahoo! Front Page Today Module dataset containing over 33
million events. Results showed a 12.5% click lift compared to a standard
context-free bandit algorithm, and the advantage becomes even greater when data
gets more scarce."

Detecting Weak but Hierarchically-Structured Patterns in Networks. (arXiv:1003.0205v1 [cs.IT])

2010-03-02T02:01:00.000-08:00

Detecting Weak but Hierarchically-Structured Patterns in Networks. (arXiv:1003.0205v1 [cs.IT]): "

The ability to detect weak distributed activation patterns in networks is
critical to several applications, such as identifying the onset of anomalous
activity or incipient congestion in the Internet, or faint traces of a
biochemical spread by a sensor network. This is a challenging problem since
weak distributed patterns can be invisible in per node statistics as well as a
global network-wide aggregate. Most prior work considers situations in which
the activation/non-activation of each node is statistically independent, but
this is unrealistic in many problems. In this paper, we consider structured
patterns arising from statistical dependencies in the activation process. Our
contributions are three-fold. First, we propose a sparsifying transform that
succinctly represents structured activation patterns that conform to a
hierarchical dependency graph. Second, we establish that the proposed transform
facilitates detection of very weak activation patterns that cannot be detected
with existing methods. Third, we show that the structure of the hierarchical
dependency graph governing the activation process, and hence the network
transform, can be learnt from very few (logarithmic in network size)
independent snapshots of network activity."

Basins of attraction for species extinction and coexistence in spatial rock-paper-scissors games

2010-03-01T13:31:00.000-08:00

Basins of attraction for species extinction and coexistence in spatial rock-paper-scissors games: "Author(s): Hongjing Shi, Wen-Xu Wang, Rui Yang, and Ying-Cheng Lai
We study the collective dynamics of mobile species under cyclic competition by breaking the symmetry in the initial populations and examining the basins of the two distinct asymptotic states: extinction and coexistence, the latter maintaining biodiversity. We find a rich dependence of dynamical prop...

[Phys. Rev. E 81, 030901] Published Mon Mar 01, 2010"

Percolation Hamiltonians. (arXiv:1002.5000v1 [math-ph])

2010-03-01T04:02:00.000-08:00

Percolation Hamiltonians. (arXiv:1002.5000v1 [math-ph]): "

There has been quite some activity and progress concerning spectral
asymptotics of random operators that are defined on percolation subgraphs of
different types of graphs. In this short survey we record some of these results
and explain the necessary background coming from different areas in
mathematics: graph theory, group theory, probability theory and random
operators."

Optimal properties of centroid-based classifiers for very high-dimensional data. (arXiv:1002.4781v1 [math.ST])

2010-02-26T02:46:00.000-08:00

Optimal properties of centroid-based classifiers for very high-dimensional data. (arXiv:1002.4781v1 [math.ST]): "

We show that scale-adjusted versions of the centroid-based classifier enjoys
optimal properties when used to discriminate between two very high-dimensional
populations where the principal differences are in location. The scale
adjustment removes the tendency of scale differences to confound differences in
means. Certain other distance-based methods, for example, those founded on
nearest-neighbor distance, do not have optimal performance in the sense that we
propose. Our results permit varying degrees of sparsity and signal strength to
be treated, and require only mild conditions on dependence of vector
components. Additionally, we permit the marginal distributions of vector
components to vary extensively. In addition to providing theory we explore
numerical properties of a centroid-based classifier, and show that these
features reflect theoretical accounts of performance."

From modular to centralized organization of synchronization in functional areas of the cat cerebral cortex. (arXiv:1002.4835v1 [q-bio.NC])

2010-02-26T02:44:00.001-08:00

From modular to centralized organization of synchronization in functional areas of the cat cerebral cortex. (arXiv:1002.4835v1 [q-bio.NC]): "

Recent studies have pointed out the importance of transient synchronization
between widely distributed neural assemblies to understand conscious
perception. These neural assemblies form intricate networks of neurons and
synapses whose detailed map for mammals is still unknown and far from our
experimental capabilities. Only in a few cases, for example the C. elegans, we
know the complete mapping of the neuronal tissue or its mesoscopic level of
description provided by cortical areas. Here we study the process of transient
and global synchronization using a simple model of phase-coupled oscillators
assigned to cortical areas in the cerebral cat cortex. Our results highlight
the impact of the topological connectivity in the developing of
synchronization, revealing a transition in the synchronization organization
that goes from a modular decentralized coherence to a centralized synchronized
regime controlled by a few cortical areas forming a Rich-Club connectivity
pattern."

Network science: a review focused on tourism. (arXiv:1002.4766v1 [physics.soc-ph])

2010-02-26T02:44:00.000-08:00

Network science: a review focused on tourism. (arXiv:1002.4766v1 [physics.soc-ph]): "

This paper presents a review of the methods of the science of networks with
an application to the field of tourism studies. The basic definitions and
computational techniques are described and a case study (Elba, Italy) used to
illustrate the effect of network typology on information diffusion. A static
structural characterization of the network formed by destination stakeholders
is derived from stakeholder interviews and website link analysis. This is
followed by a dynamic analysis of the information diffusion process within the
destination demonstrating that stakeholder cohesion and adaptive capacity have
a positive effect on information diffusion. The outcomes and the implications
of this analysis for improving destination management are discussed."

Complementary approaches to understanding the plant circadian clock. (arXiv:1002.4661v1 [cs.CE])

2010-02-26T02:42:00.000-08:00

Complementary approaches to understanding the plant circadian clock. (arXiv:1002.4661v1 [cs.CE]): "

Circadian clocks are oscillatory genetic networks that help organisms adapt
to the 24-hour day/night cycle. The clock of the green alga Ostreococcus tauri
is the simplest plant clock discovered so far. Its many advantages as an
experimental system facilitate the testing of computational predictions.

We present a model of the Ostreococcus clock in the stochastic process
algebra Bio-PEPA and exploit its mapping to different analysis techniques, such
as ordinary differential equations, stochastic simulation algorithms and
model-checking. The small number of molecules reported for this system tests
the limits of the continuous approximation underlying differential equations.
We investigate the difference between continuous-deterministic and
discrete-stochastic approaches. Stochastic simulation and model-checking allow
us to formulate new hypotheses on the system behaviour, such as the presence of
self-sustained oscillations in single cells under constant light conditions.

We investigate how to model the timing of dawn and dusk in the context of
model-checking, which we use to compute how the probability distributions of
key biochemical species change over time. These show that the relative
variation in expression level is smallest at the time of peak expression,
making peak time an optimal experimental phase marker. Building on these
analyses, we use approaches from evolutionary systems biology to investigate
how changes in the rate of mRNA degradation impacts the phase of a key protein
likely to affect fitness. We explore how robust this circadian clock is towards
such potential mutational changes in its underlying biochemistry. Our work
shows that multiple approaches lead to a more complete understanding of the
clock."

Theory of minimum spanning trees. I. Mean-field theory and strongly disordered spin-glass model

2010-02-25T14:26:00.001-08:00

Theory of minimum spanning trees. I. Mean-field theory and strongly disordered spin-glass model: "Author(s): T. S. Jackson and N. Read
The minimum spanning tree (MST) is a combinatorial optimization problem: given a connected graph with a real weight (“cost”) on each edge, find the spanning tree that minimizes the sum of the total cost of the occupied edges. We consider the random MST, in which the edge costs are (quenched) ind...
[Phys. Rev. E 81, 021130] Published Thu Feb 25, 2010"

Theory of minimum spanning trees. II. Exact graphical methods and perturbation expansion at the percolation threshold

2010-02-25T14:26:00.000-08:00

Theory of minimum spanning trees. II. Exact graphical methods and perturbation expansion at the percolation threshold: "Author(s): T. S. Jackson and N. Read
Continuing the program begun by the authors in a previous paper, we develop an exact low-density expansion for the random minimum spanning tree (MST) on a finite graph and use it to develop a continuum perturbation expansion for the MST on critical percolation clusters in space dimension d . The per...
[Phys. Rev. E 81, 021131] Published Thu Feb 25, 2010"

Controlling synchrony by delay coupling in networks: From in-phase to splay and cluster states

2010-02-25T14:25:00.000-08:00

Controlling synchrony by delay coupling in networks: From in-phase to splay and cluster states: "Author(s): Chol-Ung Choe, Thomas Dahms, Philipp Hövel, and Eckehard Schöll
We study synchronization in delay-coupled oscillator networks using a master stability function approach. Within a generic model of Stuart-Landau oscillators (normal form of supercritical or subcritical Hopf bifurcation), we derive analytical stability conditions and demonstrate that by tuning the c...
[Phys. Rev. E 81, 025205] Published Thu Feb 25, 2010"

Optimizing transport efficiency on scale free networks through assortative or dissortative topology

2010-02-25T06:54:00.000-08:00

Optimizing transport efficiency on scale free networks through assortative or dissortative topology: "We find that transport on scale-free random networks depends strongly on degree-correlated network topologies whereas transport on Erd[o\ddot]s-Rényi networks is insensitive to the degree correlation. An approach for the tuning of scale-free network transport efficiency through assortative or d..."

Annealed formulation of the dynamics on static and of adaptive complex networks. (arXiv:1002.4410v1 [physics.soc-ph])

2010-02-25T00:43:00.000-08:00

Annealed formulation of the dynamics on static and of adaptive complex networks. (arXiv:1002.4410v1 [physics.soc-ph]): "

We propose an annealed formulation of complex networks to study the dynamical
behavior of both static and adaptive networked systems. The formulation relies
on an annealed adjacency matrix, representing one network ensemble, and allows
to solve the dynamical evolution of the network all at once. We particularize
on the disease spreading dynamics on top of static and growing adaptive
networks. Our results accurately reproduce those obtained by extensive
numerical simulations showing a large improvement with respect to the usual
heterogeneous mean-field formulation. Apart from fast and reliable, the
annealed dynamics constitutes an unifying framework for the study of dynamical
processes on networks and complex adaptive systems."

Effects of Mass Media action on the Axelrod Model with Social Influence. (arXiv:1002.4615v1 [physics.soc-ph])

2010-02-25T00:42:00.000-08:00

Effects of Mass Media action on the Axelrod Model with Social Influence. (arXiv:1002.4615v1 [physics.soc-ph]): "

The use of {\it dyadic interaction} between agents, in combination with {\it
homophily} (the principle that ``likes attract'') in the Axelrod model for the
study of cultural dissemination has two important problems: the prediction of
monoculture in large societies and an extremely narrow window of noise levels
in which diversity with local convergence is obtained. Recently, the inclusion
of {\it social influence} has proven to overcome them (A. Flache and M. W.
Macey, arXiv:0808.2710). Here we extend the Axelrod model with social influence
interaction for the study of Mass Media effects through the inclusion of a
super-agent which acts over the whole system and has nonnull overlap with each
agent of the society. The dependence with different parameters as the initial
social diversity, size effects, Mass Media strength and noise is outlined. Our
results might be relevant in several socio-economic contexts and for the study
of the emergence of collective behavior in complex social systems."

Horizontal visibility graphs: exact results for random time series. (arXiv:1002.4526v1 [physics.data-an])

2010-02-25T00:41:00.000-08:00

Horizontal visibility graphs: exact results for random time series. (arXiv:1002.4526v1 [physics.data-an]): "

The visibility algorithm has been recently introduced as a mapping between
time series and complex networks. This procedure allows to apply methods of
complex network theory for characterizing time series. In this work we present
the horizontal visibility algorithm, a geometrically simpler and analytically
solvable version of our former algorithm, focusing on the mapping of random
series (series of independent identically distributed random variables). After
presenting some properties of the algorithm, we present exact results on the
topological properties of graphs associated to random series, namely the degree
distribution, clustering coefficient, and mean path length. We show that the
horizontal visibility algorithm stands as a simple method to discriminate
randomness in time series, since any random series maps to a graph with an
exponential degree distribution of the shape P(k) = (1/3)(2/3)**(k-2),
independently of the probability distribution from which the series was
generated. Accordingly, visibility graphs with other P(k) are related to
non-random series. Numerical simulations confirm the accuracy of the theorems
for finite series. In a second part, we show that the method is able to
distinguish chaotic series from i.i.d. theory, studying the following
situations: (i) noise-free low-dimensional chaotic series, (ii) low-dimensional
noisy chaotic series, even in the presence of large amounts of noise, and (iii)
high-dimensional chaotic series (coupled map lattice), without needs for
additional techniques such as surrogate data or noise reduction methods.
Finally, heuristic arguments are given to explain the topological properties of
chaotic series and several sequences which are conjectured to be random are
analyzed."

Structural Analysis of Biodiversity

2010-02-24T01:45:00.000-08:00

Structural Analysis of Biodiversity: "

Large, recently-available genomic databases cover a wide range of life forms, suggesting opportunity for insights into genetic structure of biodiversity. In this study we refine our recently-described technique using indicator vectors to analyze and visualize nucleotide sequences. The indicator vector approach generates correlation matrices, dubbed Klee diagrams, which represent a novel way of assembling and viewing large genomic datasets. To explore its potential utility, here we apply the improved algorithm to a collection of almost 17000 DNA barcode sequences covering 12 widely-separated animal taxa, demonstrating that indicator vectors for classification gave correct assignment in all 11000 test cases. Indicator vector analysis revealed discontinuities corresponding to species- and higher-level taxonomic divisions, suggesting an efficient approach to classification of organisms from poorly-studied groups. As compared to standard distance metrics, indicator vectors preserve diagnostic character probabilities, enable automated classification of test sequences, and generate high-information density single-page displays. These results support application of indicator vectors for comparative analysis of large nucleotide data sets and raise prospect of gaining insight into broad-scale patterns in the genetic structure of biodiversity."

Mutual information in time-varying biochemical systems. (arXiv:1002.4273v1 [q-bio.MN])

2010-02-24T01:44:00.000-08:00

Mutual information in time-varying biochemical systems. (arXiv:1002.4273v1 [q-bio.MN]): "

Cells must continuously sense and respond to time-varying environmental
stimuli. These signals are transmitted and processed by biochemical signalling
networks. However, the biochemical reactions making up these networks are
intrinsically noisy, which limits the reliability of intracellular signalling.
Here we use information theory to characterise the reliability of transmission
of time-varying signals through elementary biochemical reactions in the
presence of noise. We calculate the mutual information for both instantaneous
measurements and trajectories of biochemical systems for a Gaussian model. Our
results indicate that the same network can have radically different
characteristics for the transmission of instantaneous signals and trajectories.
For trajectories, the ability of a network to respond to changes in the input
signal is determined by the timing of reaction events, and is independent of
the correlation time of the output of the network. We also study how reliably
signals on different time-scales can be transmitted by considering the
frequency-dependent coherence and gain-to-noise ratio. We find that a detector
that does not consume the ligand molecule upon detection can more reliably
transmit slowly varying signals, while an absorbing detector can more reliably
transmit rapidly varying signals. Furthermore, we find that while one reaction
may more reliably transmit information than another when considered in
isolation, when placed within a signalling cascade the relative performance of
the two reactions can be reversed. This means that optimising signal
transmission at a single level of a signalling cascade can reduce signalling
performance for the cascade as a whole."

A weakly universal cellular automaton in the hyperbolic 3D space with three states. (arXiv:1002.4290v1 [cs.DS])

2010-02-24T01:41:00.000-08:00

A weakly universal cellular automaton in the hyperbolic 3D space with three states. (arXiv:1002.4290v1 [cs.DS]): "

In this paper, we significantly improve a previous result by the same author
showing the existence of a weakly universal cellular automaton with five states
living in the hyperbolic 3D-space. Here, we get such a cellular automaton with
three states only."

Sampling from scale-free networks and the matchmaking paradox

2010-02-23T12:14:00.001-08:00

Sampling from scale-free networks and the matchmaking paradox: "Author(s): I. M. Sokolov and I. I. Eliazar
Consider a large finite scale-free network consisting of M⪢1 nodes and N⪢1 links, in which the degree distribution of links per bond is governed by a power-law P(n)≃n^{−1−α} with exponent 0[Phys. Rev. E 81, 026107] Published Tue Feb 23, 2010"

Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs

2010-02-23T12:14:00.000-08:00

Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs: "We consider random walks on random graphs, focusing on return probabilities and hitting times for sparse Erdös-Rényi graphs. Using the tree approach which is expected to be exact in the large graph limit, we show how to solve for the distribution of these quantities and we find that these ..."

Population dynamics on random networks: simulations and analytical models

2010-02-23T01:35:00.000-08:00

The European Physical Journal B (EPJ B):

Population dynamics on random networks: simulations and analytical models

G. Rozhnova and A. Nunes

"We study the phase diagram of the standard pair approximation equations for two different models in population dynamics, the susceptible-infective-recovered-susceptible model of infection spread and a predator-prey interaction model, on a network of homogeneous degree k. These models have similar phase diagrams and represent two classes of systems for which noisy oscillations, still largely unexplained, are observed in nature. We show that for a certain range of the parameter k both models exhibit an oscillatory phase in a region of parameter space that corresponds to weak driving. This oscillatory phase, however, disappears when k is large. For k = 3, 4, we compare the phase diagram of the standard pair approximation equations of both models with the results of simulations on regular random graphs of the same degree. We show that for parameter values in the oscillatory phase, and even for large system sizes, the simulations either die out or exhibit damped oscillations, depending on the initial conditions. We discuss this failure of the standard pair approximation model to capture even the qualitative behavior of the simulations on large regular random graphs and the relevance of the oscillatory phase in the pair approximation diagrams to explain the cycling behavior found in real populations."

Improving Term Extraction Using Particle Swarm Optimization Techniques. (arXiv:1002.4041v1 [cs.IR])

2010-02-23T01:27:00.000-08:00

Improving Term Extraction Using Particle Swarm Optimization Techniques. (arXiv:1002.4041v1 [cs.IR]): "

Term extraction is one of the layers in the ontology development process
which has the task to extract all the terms contained in the input document
automatically. The purpose of this process is to generate list of terms that
are relevant to the domain of the input document. In the literature there are
many approaches, techniques and algorithms used for term extraction. In this
paper we propose a new approach using particle swarm optimization techniques in
order to improve the accuracy of term extraction results. We choose five
features to represent the term score. The approach has been applied to the
domain of religious document. We compare our term extraction method precision
with TFIDF, Weirdness, GlossaryExtraction and TermExtractor. The experimental
results show that our propose approach achieve better precision than those four
algorithm."

Rumor Spreading on Random Regular Graphs and Expanders. (arXiv:1002.3518v1 [math.CO] CROSS LISTED)

2010-02-22T02:13:00.000-08:00

Rumor Spreading on Random Regular Graphs and Expanders. (arXiv:1002.3518v1 [math.CO] CROSS LISTED): "

Broadcasting algorithms are important building blocks of distributed systems.
In this work we investigate the typical performance of the classical and
well-studied push model. Assume that initially one node in a given network
holds some piece of information. In each round, every one of the informed nodes
chooses independently a neighbor uniformly at random and transmits the message
to it.

In this paper we consider random networks where each vertex has degree d,
which is at least 3, i.e., the underlying graph is drawn uniformly at random
from the set of all d-regular graphs with n vertices. We show that with
probability 1 - o(1) the push model broadcasts the message to all nodes within
(1 + o(1))C_d ln n rounds, where C_d = 1/ ln(2(1-1/d)) - 1/(d ln(1 - 1/d)). In
particular, we can characterize precisely the effect of the node degree to the
typical broadcast time of the push model. Moreover, we consider pseudo-random
regular networks, where we assume that the degree of each node is very large.
There we show that the broadcast time is (1+o(1))C ln n with probability 1 -
o(1), where C= 1/ ln 2 + 1, is the limit of C_d as d grows."

Characterization of two dimensional cellular automata over ternary fields

2010-02-20T11:16:00.001-08:00

"The set of papers [3, 4, 6, 7] deals with the behavior of the uniform 2-dimensional cellular automata over binary fields (Z2). Some structural properties and precise mathematical models using matrix algebra over the field Z2 are reported for characterizing the behavior of two-dimensional nearest neighborhood linear cellular automata with null and periodic boundary conditions [3, 4, 6, 7]. In this paper, we characterize 2-dimensional linear cellular automata transformations by using matrix algebra built on Z3. We analyze some results for two dimensional CA with rule numbers 2460N and 2460P. Finally, we investigate the dimension of the kernel of 2-dimensional cellular automata defined by the rule number 2460N."

Unmasking Chaotic Attributes in Time Series of Living Cell Populations

2010-02-20T04:16:00.000-08:00

Unmasking Chaotic Attributes in Time Series of Living Cell Populations:

"Background

Long-range oscillations of the mammalian cell proliferation rate are commonly observed both in vivo and in vitro. Such complicated dynamics are generally the result of a combination of stochastic events and deterministic regulation. Assessing the role, if any, of chaotic regulation is difficult. However, unmasking chaotic dynamics is essential for analysis of cellular processes related to proliferation rate, including metabolic activity, telomere homeostasis, gene expression, and tumor growth.

Methodology/Principal Findings

Using a simple, original, nonlinear method based on return maps, we previously found a geometrical deterministic structure coordinating such fluctuations in populations of various cell types. However, nonlinearity and determinism are only necessary conditions for chaos; they do not by themselves constitute a proof of chaotic dynamics. Therefore, we used the same analytical method to analyze the oscillations of four well-known, low-dimensional, chaotic oscillators, originally designed in diverse settings and all possibly well-adapted to model the fluctuations of cell populations: the Lorenz, Rössler, Verhulst and Duffing oscillators. All four systems also display this geometrical structure, coordinating the oscillations of one or two variables of the oscillator. No such structure could be observed in periodic or stochastic fluctuations.

Conclusion/Significance

Theoretical models predict various cell population dynamics, from stable through periodically oscillating to a chaotic regime. Periodic and stochastic fluctuations were first described long ago in various mammalian cells, but by contrast, chaotic regulation had not previously been evidenced. The findings with our nonlinear geometrical approach are entirely consistent with the notion that fluctuations of cell populations can be chaotically controlled."

Entropy analyses of spatiotemporal synchronizations in brain signals from patients with focal epilepsies. (arXiv:1002.3552v1 [physics.bio-ph])

2010-02-19T06:28:00.000-08:00

Entropy analyses of spatiotemporal synchronizations in brain signals from patients with focal epilepsies. (arXiv:1002.3552v1 [physics.bio-ph]): "

The electroencephalographic (EEG) data intracerebrally recorded from 20
epileptic humans with different brain origins of focal epilepsies or types of
seizures, ages and sexes are investigated (nearly 700 million data). Multi
channel univariate amplitude analyses are performed and it is shown that time
dependent Shannon entropies can be used to predict focal epileptic seizure
onsets in different epileptogenic brain zones of different patients. Formations
or time evolutions of the synchronizations in the brain signals from
epileptogenic or non epileptogenic areas of the patients in ictal interval or
inter-ictal interval are further investigated employing spatial or temporal
differences of the entropies."

Excitation regeneration in delay coupled oscillators

2010-02-18T11:07:00.000-08:00

Excitation regeneration in delay coupled oscillators: "A network of phase-coupled oscillators constitutes a system in which excitable 2p phase-slips can be induced by noise. We show that such an excitation in one of the oscillators can be regenerated by subsequent oscillators and become self-sustained for certain topologies. We focus on the simplest suc..."

Systematic Analysis of Circadian Genes in a Population-Based Sample Reveals Association of TIMELESS with Depression and Sleep Disturbance

2010-02-18T03:26:00.000-08:00

Systematic Analysis of Circadian Genes in a Population-Based Sample Reveals Association of TIMELESS with Depression and Sleep Disturbance: "

Disturbances in the circadian pacemaker system are commonly found in individuals with depression and sleep-related problems. We hypothesized that some of the canonical circadian clock genes would be associated with depression accompanied by signs of disturbed sleep, early morning awakening, or daytime fatigue. We tested this hypothesis in a population-based sample of the Health 2000 dataset from Finland, including 384 depressed individuals and 1270 controls, all with detailed information on sleep and daytime vigilance, and analyzed this set of individuals with regard to 113 single-nucleotide polymorphisms of 18 genes of the circadian system. We found significant association between TIMELESS variants and depression with fatigue (D+FAT+) (rs7486220: pointwise P = 0.000099, OR = 1.66; corrected empirical P for the model of D+FAT+ = 0.0056; haplotype ‘C-A-A-C’ of rs2291739-rs2291738-rs7486220-rs1082214: P = 0.0000075, OR = 1.72) in females, and association to depression with early morning awakening (D+EMA+) (rs1082214: pointwise P = 0.0009, OR = 2.70; corrected empirical P = 0.0374 for the model D+EMA+; haplotype ‘G-T’ of rs7486220 and rs1082214: P = 0.0001, OR = 3.01) in males. There was significant interaction of gender and TIMELESS (for example with rs1082214, P = 0.000023 to D+EMA+ and P = 0.005 to D+FAT+). We obtained supported evidence for involvement of TIMELESS in sleeping problems in an independent set of control individuals with seasonal changes in mood, sleep duration, energy level and social activity in females (P = 0.036, ® = 0.123 for rs1082214) and with early morning awakening or fatigue in males (P = 0.038 and P = 0.0016, respectively, for rs1082214). There was also some evidence of interaction between TIMELESS and PER1 in females to D+FAT+ as well as between TIMELESS and ARNTL, RORA or NR1D1 in males to D+EMA+. These findings support a connection between circadian genes and gender-dependent depression and defective sleep regulation."