Maximizing information exchange between complex networks

Abstract

Science is not merely the smooth progressive interaction of hypothesis, experiment and theory, although it sometimes has that form. More realistically the scientific study of any given complex phenomenon generates a number of explanations, from a variety of perspectives, that eventually requires synthesis to achieve a deep level of insight and understanding. One such synthesis has created the field of out-of-equilibrium statistical physics as applied to the understanding of complex dynamic networks. Over the past forty years the concept of complexity has undergone a metamorphosis. Complexity was originally seen as a consequence of memory in individual particle trajectories, in full agreement with a Hamiltonian picture of microscopic dynamics and, in principle, macroscopic dynamics could be derived from the microscopic Hamiltonian picture. The main difficulty in deriving macroscopic dynamics from microscopic dynamics is the need to take into account the actions of a very large number of components. The existence of events such as abrupt jumps, considered by the conventional continuous time random walk approach to describing complexity was never perceived as conflicting with the Hamiltonian view. Herein we review many of the reasons why this traditional Hamiltonian view of complexity is unsatisfactory. We show that as a result of technological advances, which make the observation of single elementary events possible, the definition of complexity has shifted from the conventional memory concept towards the action of non-Poisson renewal events. We show that the observation of crucial processes, such as the intermittent fluorescence of blinking quantum dots as well as the brain’s response to music, as monitored by a set of electrodes attached to the scalp, has forced investigators to go beyond the traditional concept of complexity and to establish closer contact with the nascent field of complex networks. Complex networks form one of the most challenging areas of modern research overarching all of the traditional scientific disciplines. The transportation networks of planes, highways and railroads; the economic networks of global finance and stock markets; the social networks of terrorism, governments, businesses and churches; the physical networks of telephones, the Internet, earthquakes and global warming and the biological networks of gene regulation, the human body, clusters of neurons and food webs, share a number of apparently universal properties as the networks become increasingly complex. Ubiquitous aspects of such complex networks are the appearance of non-stationary and non-ergodic statistical processes and inverse power-law statistical distributions. Herein we review the traditional dynamical and phase–space methods for modeling such networks as their complexity increases and focus on the limitations of these procedures in explaining complex networks. Of course we will not be able to review the entire nascent field of network science, so we limit ourselves to a review of how certain complexity barriers have been surmounted using newly applied theoretical concepts such as aging, renewal, non-ergodic statistics and the fractional calculus. One emphasis of this review is information transport between complex networks, which requires a fundamental change in perception that we express as a transition from the familiar stochastic resonance to the new concept of complexity matching.

Introduction

One of the perennial problems in the physics of communication is matching information flow to the physical structure of the channel supporting that flow in such a way as to maximize efficiency, that is, maximize the information transferred in the channel. Of course, in order to make the problem well defined requires a rigorous definition of information, as well as, a notion of channel capacity, that being, how much information transfer can a channel support under ideal conditions. Wiener (1948) and Shannon (1948) among others defined these things over half a century ago and science is now extending their ideas to the broader context of complex networks, in which, Shannon’s notion of a channel is stretched to include networks from the social and life sciences. For the perspective of this Report it is useful to replace the notion of channel with that of network in order to avoid unnecessary confusion.

Complex networks form one of the most challenging areas of modern research overarching all of the traditional scientific disciplines. The transportation networks of planes, highways and railroads; the economic networks of global finance and stock markets; the social networks of terrorism, governments, businesses and churches; the physical networks of telephones, the Internet, earthquakes and global warming as well as the biological networks of gene regulation, the human body, clusters of neurons and food webs, share a number of apparently universal properties as the networks become increasingly complex, see, e.g., Network Science (2005). Over the last century a substantial number of books have been written addressing the complexity of networks: books on biological networks, focusing on the macroscopic level as did Lotka (1924), or the explicit consideration of scaling in organisms by MacDonald (1983) and Calder (1984), or the broad study of the phenomenon of synchronization carried out by Strogatz (2003); tomes on social networks, focusing on the interaction among groups of people as did Scott (2000), and on the citations to scientific papers forming the invisible college studied by de Sola Price (1963); monographs on networks of natural phenomena, including Mandelbrot’s now classic book (1977) introducing the concept of fractals, the growth of river basins by Rodríguez-Iturbe and Rinaldo (1997) and the morphogenesis of physiologic organs by Weibel (2000); tracts on information networks, exploring the interface between man and machine as did Wiener (1948), initiating the modern theory of communication by Shannon and Weaver (1959), and quantifying complexity using information measures by Li and Vitányi (1997).

Each of these complex networks and others are generated by mechanisms specific to the phenomenon being considered, the psychology of human interaction in the social domain, the scaling across scale in the natural sciences and the explosive growth of information in nonlinear dynamical networks. On the other hand, there are properties common to all that enables us to identify them as networks. Here we focus on the fact that to understand the dynamics of these complex networks the traditional analysis of information flow and channel traffic, involving exponential distributions of messages and consequently Poisson statistics of traffic volume, must be abandoned and replaced with less familiar statistical techniques. The techniques reviewed have appeared in the diaspora of the physical sciences literature on networks and complexity.

There have been a significant number of excellent review articles on complex network published recently, each with its own philosophical slant. Albert and Barabási (2002) review complex networks from the perspective of nonequilibrium statistical physics, whereas Newman (2003) organized his review around the various applications that have been made, including social, information, technological and biological networks and the mathematical rendition of the common properties that are observed among them. The most recent survey by Costa et al. (2007) views complex network research as being at the intersection of graph theory and statistical physics and focuses on existing measurements that support the principal models found in the literature. Our approach is a hybrid of these views. We take nonequilibrium statistical physics and its techniques as our starting point, use recent experiments done on complex networks to highlight the inadequacies of the traditional approaches, but more importantly, we use these data to motivate the development of new mathematical modeling techniques necessary to understand the underlying network structure.

Apparently ubiquitous aspects of complex networks are the appearance of non-stationary, non-ergodic, non-Poisson, renewal, statistical processes. These properties are manifest through inverse power-law statistical distributions that not only challenge traditional understanding of complexity in physical networks, but require new strategies for understanding how information is exchanged between such networks. Our purpose herein is to review how the traditional methods of statistical physics used to characterize the dynamics of complex phenomena have been extended in the analysis of such physical phenomena as spin glasses and intermittent fluorescence, called blinking quantum dots (BQD); in such life phenomena as networks of neurons, biofeedback techniques and the brain’s response to music, and in such geophysical phenomena as global warming. Moreover, we review how these extensions apply to the problem of information exchange between complex networks independently of the specific interactions among the elements within a network.

Resonant phenomena have been among the most useful mechanisms for extracting weak signals from noisy backgrounds. A linear dynamic process responds strongly to a harmonic perturbation with matching frequency and this linear resonance has been used in a variety of detectors, such as magnetic resonance imaging (MRI), see, e.g., Weishaupt et al. (2003). Effective two-state stochastic phenomena respond strongly when the period of a harmonic perturbation matches the transition rate of the stochastic process. This resonance (SR), see, e.g. Benzi et al. (1981), is one strategy for modeling the transmission of information through random (Poisson statistics) media that can enhance the signal-to-noise ratio, see, e.g. Gammaitoni et al. (1998).

As we review herein, if the perturbed network is a Poisson process, using ordinary linear response theory (LRT), see Kubo (1957), it is straightforward to go beyond the aperiodic SR as discussed by Collins et al. (1995) and Collins et al., 1996a, Collins et al., 1996b, which is confined to the case of slow perturbation, and to derive the phenomenon of rate matching, which has been overlooked in the SR literature. Allegrini et al. (2007a) and Aquino et al. (2007) address the challenging situation where the network being perturbed is neither Poisson nor ergodic, so as to meet the conditions emerging from complex networks. Goychuck and Hänggi (2003) studied the case where the network to be perturbed is not Poisson but is still ergodic. The non-ergodic condition, studied by Bel and Barkai, 2006a, Bel and Barkai, 2006b and Margolin and Barkai, 2005, Margolin and Barkai, 2006, violates the conditions for the Kubo (1957) form of LRT, and has been studied by Barbi et al. (2005), who conclude that a complex network described by intermittent fluctuations with non-Poisson statistics does not respond asymptotically to external periodic perturbations. Sokolov and Metzler (2003) reached the same conclusion. Herein we show that this property of violating LRT can be explained by adopting a proper definition of complexity, which, more importantly, leads us to discover a method for information transport bypassing the limitations pointed out by Barbi et al. (2005) and Sokolov and Metzler (2003).

A number of complex phenomena have been shown to have non-Poisson statistical properties, including collections of BQDs, see, for example, Nirmal et al. (1996), Kuno et al., 2001, Kuno et al., 2003 and Shimizu et al. (2001), and aggregations of neurons in the human brain by Bianco et al. (2007a). The non-Poisson character of the distribution of sojourn times in the “on” and “off” states in BQDs is well known, see, for example, Nirmal et al. (1996), Kuno et al., 2001, Kuno et al., 2003 and Shimizu et al. (2001), however the renewal character of the statistics has only recently been established by Bianco et al. (2005) and Brokmann et al. (2003). Moreover, Bianco et al. (2007b) have shown using a network of coupled two-state stochastic clocks that with the onset of phase synchronization at a critical value of the coupling coefficient the dynamics of the network becomes that of a non-Poisson renewal process operating in the non-ergodic regime. The breakdown of the collective phase structures occur with no memory of previous state changes, consequently yielding a non-Poisson renewal process (NPR). NPRs are characterized by a waiting-time distribution density between events, indicated by $\psi \left(\tau \right)$. The regression to equilibrium of an ensemble of NPRs is given by the survival probability $\Psi \left(t\right)={\int }_0^{\tau }\psi \left(\tau \right)d\tau$. Herein we focus most of our attention on inverse power-law distributions $\Psi \left(t\right)\approx t^{-\alpha }$ with index $\alpha <1$, thereby corresponding to processes that violates the finite time-scale assumption so often made in statistical physics.

One way a non-exponential decay, such as the inverse power law, can be expressed is as the sum of infinitely many Poisson components, but if these components are independent, as are the single dynamic elements in the absence of cooperation, no NPR events are generated as shown by Allegrini et al. (2006). The production of NPR events is a sign of close cooperation among distinct dynamical elements, thereby offering a rationale as to why the NPR processes do not respond to harmonic perturbations, see, for example, Barbi et al. (2005) and Sokolov and Metzler (2003), as would single independent Poisson dynamical elements. NPR processes reflect a condition shared by the phenomenological models of glassy dynamics as shown by Bouchaud (1992), laser cooling as discussed by Bardou et al. (2002) and models of atomic transport in optical lattices given by Lutz (2004). Other NPR processes have been found at the core of the correlations in DNA sequences by Mohanty and Narayana Rao (2000), heart-beat variability by Allegrini et al. (2003a) and West (2006) and earthquake statistics by Mega et al. (2003).

Herein we review a new phenomenon of information transport, that is, the determination of how one complex network responds to an excitation by a second complex network as a function of the matching of the measures of complexity of the two networks. The complex network considered is NPR and the measure of complexity is the inverse power-law index. More precisely, we consider a NPR network, whose waiting time distribution density $\psi \left(\tau \right)$ has the power-law index $\mu \equiv \alpha +1<2$, and we review, in analogy with stochastic resonance (SR) theory reviewed by Gammaitoni et al. (1998), the case where the rate of production of jumps, a kind of renewal event, is modulated by an external excitation. This leads to the new concept of complexity matching, where the exchange of information between two complex networks is maximized when their complexity is the same. The complexity matching phenomenon is a special property of non-ergodic renewal (NER) processes, which are a special class of NPR processes. For this reason we subsequently replace the NPR acronym with the NER acronym.

In this report we briefly review the traditional dynamical and phase space methods for modeling dynamic networks as a strategy for understanding their increasing complexity and focus on the limitations of these procedures in explaining complex networks. In Section 2 we present the Hamiltonian basis for coupling microscopic dynamics to macroscopic phenomenology leading to the Generalized Langevin Equation (GLE), see, for example, Lindenberg and West (1990). In order to better understand how information is transferred among such complex networks we review the phenomenon of simple linear resonance and briefly examine the mechanism of stochastic resonance (SR), where adding noise to a nonlinear dynamic network increases rather than decreases our ability to detect a signal. The SR effect has been proposed as a way collections of neurons can effectively use biological noise to facilitate the exchange of information as explained by Moss et al. (2004). This perspective on resonance and noise suggests that we examine the influence of memory on stochastic processes, which we follow and indicate how random phenomena with memory require a description using a certain kind of GLE. We introduce the fractional Langevin equation (FLE) or more generally fractional stochastic differential equations (FSDE) in which the memory kernel of the GLE is interpreted as a fractional operator and establish a correspondence with an increasing literature on the application and interpretation of the fractional calculus, see, for example, West et al. (2003) to the description of complex dynamic phenomena. Note that the FSDE only arise when the microscopic time scales diverge, which is for $\mu <2$ in the present context, and consequently overlap with the macroscopic time scales.

In Section 3 we replace the dynamic equations for network variables discussed in Section 2 with phase–space equations of motion for the phase–space density function and the probability density. In this section, for completeness, we briefly go over the traditional statistical physics areas of the Fokker–Planck equation (FPE) developed in the context of Brownian motion; the Generalized Master Equation (GME) as another strategy for systematically describing the influence of complexity on the information dynamics of complex networks and finally, continuous time random walks (CTRW) as a third perspective for incorporating memory into network dynamics. This section is streamlined in its use of previously published material because the literature is so vast. Consequently, we emphasize only the most recent relations that have been determined among these formalisms, for example, GME and CTRW are only equivalent under certain very restricted conditions. Finally, we demonstrate that the recent interest in fractional diffusion equations (FDE) can be traced back to these more familiar formalisms when the complex phenomena being investigated are intermittent and have memory; the FDEs are not uniquely determined and can be independently derived from the GME, CTRW and FSDE formalisms.

The kinds of complexity introduced into network dynamics in Sections 2 Dynamic models of statistics, 3 Phase space models of statistics through the dynamic and phase space formalisms are discussed more fully in the context of what had previously appeared as the esoteric mathematical descriptions of non-ergodic, non-stationary, non-Poisson stochastic processes. In Section 4 we review these concepts in order to arrive at a general and useful definition of complexity and this involves the concept of renewal aging, as distinct from the notion of aging recently introduced in the study of glassy materials, which we also briefly discuss.

Of course we will not be able to review the entire budding field of Network Science here, so we limit ourselves to reviewing how certain complexity barriers have been surmounted using new theoretical concepts such as aging, the fractional calculus, and complexity matching. In Section 5 we illustrate an approach to understanding complexity, inspired by recent neurophysiological results, based on the modern theory of subordination. We interpret subordination theory as corresponding to the vision of complexity advocated herein. The complex processes are characterized by the occurrence of quakes, usually small, which can accumulate so as to generate large quakes, which may be experimentally detectable. The theory of subordination is based on the assumption that the time interval between two consecutive actions, or small quakes, is described by a distribution density, subordination function, having the inverse power-law form. However, if the success probability of these actions is small, the resulting survival probability is a Mittag–Leffler function (MLF), see, for example, Rabotnov (1980) for a physical discussion of this function. One exemplar of such a process, discussed in Section 5, is the electroencephalograph (EEG) of the human brain and how the parameters of the statistics of the EEG time series change while listening to music. This section also prepares the ground for the introduction of the complexity matching effect (CME), discussed fully in Section 6.

Section 6 presents heuristic arguments that the transport of information between complex networks attains maximum efficiency at the condition where the inverse power-law indices of the two networks are equal. The basis of the analysis is a recently developed generalization of the fluctuation–dissipation theorem (FDT) of the first kind, which is used to develop analytic expressions for the perturbation of one complex network by another. The probability density describing these complex networks is inverse power law. One exemplar of how a perturbed complex network inherits the statistics of the perturbing complex network, when the power-law index is greater than two, is the linking of the statistical fluctuations in the Earth’s average temperature to the variability in solar activity. When the power-law index is less than two the underlying process is non-ergodic, see Bel and Barkai (2005) and Margolin and Barkai (2005). The ergodic hypothesis in physics can be traced to Gibbs and his assertion that ensemble averages and long time averages should yield the same result. He was never able to prove this conjecture, but most of the statistical physics of the last century is based on this hypothesis being true. In the 21st century it has become clear that more and more of the complex phenomena of interest violate this assumption and so in Section 6 we review how sensitive some of the traditional relations of statistical physics are to the ergodic hypothesis.

In Section 7 we take up another fundamental mechanism of complex networks, that being synchronization, where the properties of the individual element are lost and replaced with those of the collective. However, we caution the reader that there are many subtle aspects to synchronization and so here also we remain fairly narrowly focused. In particular, we review those aspects of synchronization that relate to the NER stochastic processes of earlier sections. We use a master equation to describe the interaction of a large number of two-state clocks, how they undergo a phase transition from incoherent dynamics to dynamically synchronized, if random, collection of elements. The description has been used to show that the MLF and, consequently, the associated subordination function discussed in Section 5, is the result of cooperation among many elements. The phenomena this model has been used to describe, which we review, include BQDs and collections of neurons.

Finally, Section 8 summarizes the crucial issues highlighted in this report, specifically the new phenomenon of complexity matching in the information transport between complex networks. This is done through a discussion of the more familiar physical phenomena of $1/f$-noise. The classic review by Dutta and Horn (1981) lays out the remarkable variety of physical networks that fluctuate with approximately $1/f$-shaped spectral densities. In the subsequent quarter century $1/f$-variability has been discovered in almost every scientific domain. It has been experimentally observed in the brain and other physiologic networks, in music, in the visual arts, in linguistics, and in sociology. The CME is related to the interaction between two such networks characterized by $1/f$-noise. Finally, we tie up some loose ends and relate CME to a generalization of SR, emphasize that the discussion is now in terms of events rather than continuous processes, and close with a recapitulation of the different kinds of memory that occur in a trajectory and a probability and how this relates to renewal processes.