Fractals and Scale-free Networks

Fractals and Scale-free Networks

In science, what we see is limited by what our mathematics allows us to see. The mathematical framework built since Newton’s time has been linear and our observations and ways of analysis are restricted by that linear framework. Around the middle of last century, Mandelbrot and others did extensive work to understand nonlinear contributions in dynamical systems and showed that nonlinearity gave rise to fractals and chaos.

A number of papers were published by Barabasi’s lab around 1999-2000. They showed that protein-protein interaction networks were ‘scale- free’, which is a strong signature of nonlinearity. Those observations should have profound implication in the analysis of biological systems, but the biologists responded with ‘so what’.

Barabasi’s papers inspired me to start working in biology, and in our first two papers, we tried to answer the ‘so what’ question. We showed that the scale-free networks were not only mathematical novelties, but the property could be utilized to predict protein functions with high accuracy. Biologists mostly ignored those methods, even though we went to the yeast genome database and annotated a number of unknown proteins using our method in 2002, and almost all predictions were experimentally verified.

The apathy toward fractal mathematics is not limited to the biologists however. This year, economists gave Nobel prize to Eugene Fama, whose equilibrium theory has been completely discredited using Mandelbrot’s discoveries as well as real-life observations. Warren Buffet made fun of Fama’s theory in a 1984 speech and said that his career would have been impossible, if Fama were correct. Also, Mandelbrot’s method was used successfully by Nassim Taleb’s to analyze financial market. Taleb was one of those few, who predicted 2008 financial collapse. We also predicted the financial crisis in two essays published in 2005, but using a different method.

Getting back to Barabasi’s work, a reader sent us the link to his recent paper that the readers may find interesting.

Controllability of complex networks

The ultimate proof of our understanding of natural or technological systems is reflected in our ability to control them. Although control theory offers mathematical tools for steering engineered and natural systems towards a desired state, a framework to control complex self-organized systems is lacking. Here we develop analytical tools to study the controllability of an arbitrary complex directed network, identifying the set of driver nodes with time-dependent control that can guide the systems entire dynamics. We apply these tools to several real networks, finding that the number of driver nodes is determined mainly by the networks degree distribution. We show that sparse inhomogeneous networks, which emerge in many real complex systems, are the most difficult to control, but that dense and homogeneous networks can be controlled using a few driver nodes. Counterintuitively, we find that in both model and real systems the driver nodes tend to avoid the high-degree nodes.

We did not follow the field closely since 2005, but would like to catch up sometime. Barabasi lab continues to be very active and posts volumes of information in their very active website. Another fascinating math we would like to ponder about is the implication of Rule 110 mentioned by Steven Wolfram. The mathematical completeness presented in Wolfram’s book seemed very helpful in describing nonlinear systems.

The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Game of Life. Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which Turing completeness has been proven, although proofs for several similar rules should follow as simple corollaries, for instance Rule 124, where the only directional (asymmetrical) transformation is reversed. Rule 110 is arguably the simplest known Turing complete system.[1][2]

Rule 110, like the Game of Life, exhibits what Wolfram calls “Class 4 behavior”, which is neither completely stable nor completely chaotic. Localized structures appear and interact in various complicated-looking ways.[3]

Matthew Cook proved Rule 110 capable of supporting universal computation. Rule 110 is a simple enough system to suggest that naturally occurring physical systems may also be capable of universality meaning that many of their properties will be undecidable, and not amenable to closed-form mathematical solutions.[4]

The sooner ENCODE-like projects bankrupt the medical funding system, it is the better. Progress in science needs fewer scientists, not more.

Written by M. //