A fully parallel version of the contact dynamics (CD) method is presented in this paper. For large enough systems, 100% efficiency has been demonstrated for up to 256 processors using a hierarchical domain decomposition with dynamic load balancing. The iterative scheme to calculate the contact forces is left domain-wise sequential, with data exchange after each iteration step, which ensures its stability. The number of additional iterations required for convergence by the partially parallel updates at the domain boundaries becomes negligible with increasing number of particles, which allows for an effective parallelization. Compared to the sequential implementation, we found no influence of the parallelization on simulation results.

"This work is devoted to communication approaches, which spread information in robot swarms. These mechanisms are useful for large-scale systems and also for such cases when a limited communication equipment does not allow routing of information packages. We focus on two approaches such as virtual fields and epidemic algorithms, discuss several aspects of hardware implementation and demonstrate experiments performed with microrobots "Jasmine"."

"Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction.

In a previous paper, a complexity measure of networks was proposed based on the {em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object.

The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resulting bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical.
In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure."

"Efficient collaborative decision making is an important challenge for multiagent systems. Finding optimal joint actions is especially challenging when each agent has only imperfect information about the state of its environment. Such problems can be modeled as collaborative Bayesian games in which each agent receives private information in the form of its type. However, representing and solving such games requires space and computation time exponential in the number of agents. This article introduces collaborative graphical Bayesian games (CGBGs), which facilitate more efficient collaborative decision making by decomposing the global payoff function as the sum of local payoff functions that depend on only a few agents. We propose a framework for the efficient solution of CGBGs based on the insight that they posses two different types of independence, which we call agent independence and type independence. In particular, we present a factor graph representation that captures both forms of independence and thus enables efficient solutions. In addition, we show how this representation can provide leverage in sequential tasks by using it to construct a novel method for decentralized partially observable Markov decision processes. Experimental results in both random and benchmark tasks demonstrate the improved scalability of our methods compared to several existing alternatives."

"We survey and show our earlier results about three different ways of fluctuation-enhanced sensing of bio agent, the phage-based method for bacterium detection published earlier; sensing and evaluating the odors of microbes; and spectral and amplitude distribution analysis of noise in light scattering to identify spores based on their diffusion coefficient."

"Developing large-scale distributed applications can be a daunting task. object-based environments have attempted to alleviate problems by providing distributed objects that look like local objects. We advocate that this approach has actually only made matters worse, as the developer needs to be aware of many intricate internal details in order to adequately handle partial failures. The result is an increase of application complexity. We present an alternative in which distribution transparency is lessened in favor of clearer semantics. In particular, we argue that a developer should always be offered the unambiguous semantics of local objects, and that distribution comes from copying those objects to where they are needed. We claim that it is often sufficient to provide only small, immutable objects, along with facilities to group objects into clusters."

"While analyzing HFT (High Frequency Trading) quote counts, we were shocked to find cases where one exchange was sending an extremely high number of quotes for one stock in a single second: as high as 5,000 quotes in 1 second! During May 6, there were hundreds of times that a single stock had over 1,000 quotes from one exchange in a single second. Even more disturbing, there doesn't seem to be any economic justification for this. In many of the cases, the bid/offer is well outside the National Best Bid/Offer (NBBO). We decided to analyze a handful of these cases in detail and graphed the sequential bid/offers to better understand them. What we discovered was a manipulative device with destabilizing effect."

can I have some of these particles, please?

"This paper presents a new numerical approach to the study of non-periodicity in signals, which can complement the maximal Lyapunov exponent method for determining chaos transitions of a given dynamical system. The proposed technique is based on the continuous wavelet transform and the wavelet multiresolution analysis. A new parameter, the \textit{scale index}, is introduced and interpreted as a measure of the degree of the signal's non-periodicity. This methodology is successfully applied to three classical dynamical systems: the Bonhoeffer-van der Pol oscillator, the logistic map, and the Henon map."

Sometimes physics is just pretty.

"The inverse Ising problem is a difficult combinatorial optimization problem in the class known as “NP-hard”. In theory, only approximate schemes, or methods that take more than polynomial time to find the answer are possible. Boltzmann Learning [1] is an iterative method where in one step the correlation functions are computed given an Ising model, and in another step the Ising model couplings are modified to adjust to data. In principle, Boltzmann learning can be employed to find the couplings with arbi- trary accuracy given accurate data and sufficient time, but the slow convergence of the Boltzmann learning makes it a very inefficient algorithm for most practical purposes."

"Small world networks interpolate between fully regular and fully random topologies and simultaneously exhibit large local clustering as well as short average path length. Small world topology has therefore been suggested to support network synchronization. Here we study the asymptotic speed of synchronization of coupled oscillators in dependence on the degree of randomness of their interaction topology in generalized Watts-Strogatz ensembles. We find that networks with fixed in-degree synchronize faster the more random they are, with small worlds just appearing as an intermediate case. For any generic network ensemble, if synchronization speed is at all extremal at intermediate randomness, it is slowest in the small world regime. This phenomenon occurs for various types of oscillators, intrinsic dynamics and coupling schemes."

"A recent study by researchers in Yale and published in PNAS shows that there are significant differences between the network topologies of living systems like E. coli and complex pieces of software such as the Linux Operating System."

"Might there be more to last week's crash than a "fat fingered" trade, or someone mistakenly entering a "billion" instead of a "million?" An online stock trader has a video showing an unusual spike in trading volume, followed by a very quick sell-off, by funds at large investment firms BlackRock and Vanguard and some other funds 30 to 15 minutes before the big crash. Prescience? Watch the video, check the logs, and decide for yourself."

"We report on experiments of many small motors -- cell phone vibrators -- glued to and interacting through a resonant plate. We find that individual motors interacting with the plate demonstrate hysteresis in their steady-state frequency due to interactions with plate resonances. For multiple motors running simultaneously, the degree of synchronization between motors increases when the motors' frequencies are near a resonance of the plate, and the frequency at which the motors synchronize shows a history dependence."

"The High Throughput Humanities satellite event at ECCS'10 establishes a forum for high throughput approaches in the humanities and social sciences, within the framework of complex systems science. The symposium aims to go beyond massive data aquisition and to present results beyond what can be manually achieved by a single person or a small group. Bringing together scientists, researchers, and practitioners from relevant fields, the event will stimulate and facilitate discussion, spark collaboration, as well as connect approaches, methods, and ideas.

The main goal of the event is to present novel results based on analyses of Big Data (see NATURE special issue 2009), focusing on emergent complex properties and dynamics, which allow for new insights, applications, and services."

"It is at the three or four times in a 24 hour period that forex traders are well advised to switch tack and reverse near-term directional thinking. The European and NYMEX close are the U.S. based things to get under our belts, because then, maybe, the equity markets can reveal where they really want to go. Traders looking for moves outside of 06:00 and 11:00 EDT, and maybe 14:30 EDT may just find themselves sitting and waiting, wondering why they just bought the high of the day that then reversed.
As the global economy travels through the contraction phase of its business cycle the leaning is towards looking at S&P futures trade to confirm sentiment. The speculators are never too far away from the S&P in times of fear; either selling into the fear of loss, or buying into the fear of missing profits. That is the reason for so much near-term volatility, and that is how things will stay until signs of GDP expansion are seen globally."

"This seems a reversal of some things I have said in the past about the need for change control. I said that "shit happens" is not an excuse any more. I still believe that. Just because some incidents will remain unpreventable doesn't mean that many others can't be prevented. Just because fixing a problem in one place means higher risks will be taken elsewhere doesn't mean we shouldn't fix the problems. And just because complex systems are impossible to stop breaking doesn't mean that there isn't negligence behind some breakages."

"It seems most people on that flight were aware of the $20 charge; overhead compartments were filled up completely, mostly with “carry-on” bags significantly larger than the one piece of luggage we had checked. As a result, a number of people had to check bags at the gate. Now here is the interesting thing… because so many people had to check bags at the gate, and those bags had to be available upon deplaning, none of us were allowed to exit the aircraft until after the bags that had been gate checked were brought up. Because so many people were trying to avoid a) waiting at the baggage carousel and b) paying twenty bucks for a piece of luggage, everyone had to wait longer. Perverse incentives lead to undesirable outcomes."

"Causal state reconstruction has an important advan- tage over VLMM methods. Each state in a VLMM is represented by a single suffix, and consists of all and only the histories ending in that suffix. For many pro- cesses, the causal states contain multiple suffixes. In these cases, multiple “contexts” are needed to repre- sent a single causal state, so VLMMs are generally more complicated than the HMMs we build. The causal state model is the same as the minimal VLMM if and only if every causal state contains a single suffix. This is the case for the process in Fig. 3, where CSSR and VLMM methods will give the same results."

"Sornette goes on to identify a number of data sets showing power laws with outliers that he says are the result of positive feedback mechanisms that make them much larger than their peers. He calls these events dragon kings. What's interesting about them is that they are entirely unaccounted for by a current understanding of power laws, from which Nassim Nicholas Taleb built the idea of black swans.

The special characteristic of dragon kings is that a positive feedback mechanism creates faster-than-exponential growth making them larger than expected."

The Goldilocks Point becomes public knowledge. Another of my consulting secrets revealed. Drat you, Kevin Kelly! You think too loud!

"Simulations of these various belief formation models show that that this simple heuristic is quite effective against other more complex fictitious play models."

Wondering where Michael Gastner, Cosma Shalizi, and Mark Newman are provided attribution, since the image used in the poster and trailer for the film was lifted straight from their Creative Commons by-attribution paper.

I've blogged it, but it warrants bookmarking too.

Matthew Berryman is citing some of what we should see.

"We’ve heard it before, we’ll hear it again: a network of many simple parts trumps one big complex monolith. It’s a story that keeps on surprising us, but probably shouldn’t."

Very positive review of Sam Bowles's <i>Microeconomics</i>. Which I also thought was peachy.

Potentially useful way of discerning clumps and clusters in the Distributed Proofreaders workflow.