Modeling complex networks with accelerating growth and aging effect

Numerous empirical studies have revealed that a large number of real networks exhibit the property of accelerating growth, i.e. network size (nodes) increases superlinearly with time. Examples include the size of social networks, the output of scientists, the population of cities, and so on. In the literature, these real systems are widely represented by complex networks for analysis, and many network models have been proposed to explain the observed properties in these systems such as power-law degree distribution. However, most of these models (e.g. the well-known BA model) are based on linear growth of these systems. In this paper, we propose a network model with accelerating growth and aging effect, resulting in an emergence of super hubs which is consistent with the empirical observation in citation networks.     

A recursive method for calculating the total number of spanning trees and its applications in self-similar small-world scale-free network models

The problem of determining and calculating the number of spanning trees of any finite graph (model) is a great challenge, and has been studied in various fields, such as discrete applied mathematics, theoretical computer science, physics, chemistry and the like. In this paper, firstly, thank to lots of real-life systems and artificial networks built by all kinds of functions and combinations among some simpler and smaller elements (components), we discuss some helpful network-operation, including link-operation and merge-operation, to design more realistic and complicated network models. Secondly, we present a method for computing the total number of spanning trees. As an accessible example, we apply this method to space of trees and cycles respectively, and our results suggest that it is indeed a better one for such models. In order to reflect more widely practical applications and potentially theoretical significance, we study the enumerating method in some existing scale-free network models. On the other hand, we set up a class of new models displaying scale-free feature, that is to say, following P(k) ~ k^?γ, where γ is the degree exponent. Based on detailed calculation, the degree exponent γ of our deterministic scale-free models satisfies γ > 3. In the rest of our discussions, we not only calculate analytically the solutions of average path length, which indicates our models have small-world property being prevailing in amounts of complex systems, but also derive the number of spanning trees by means of the recursive method described in this paper, which clarifies our method is convenient to research these models.     

From mechanical to biological oscillator networks: The role of long range interactions

The study of one-dimensional particle networks of Classical Mechanics, through Hamiltonian models, has taught us a lot about oscillations of particles coupled to each other by nearest neighbor (short range) interactions. Recently, however, a careful analysis of the role of long range interactions (LRI) has shown that several widely accepted notions concerning chaos and the approach to thermal equilibrium need to be modified, since LRI strongly affects the statistics of certain very interesting, long lasting metastable states. On the other hand, when LRI (in the form of non-local or all-to-all coupling) was introduced in systems of biological oscillators, Kuramoto’s theory of synchronization was developed and soon thereafter researchers studied amplitude and phase oscillations in networks of FitzHugh Nagumo and Hindmarsh Rose (HR) neuron models. In these models certain fascinating phenomena called chimera states were discovered where populations of synchronous and asynchronous oscillators are seen to coexist in the same system. Currently, their synchronization properties are being widely investigated in HR mathematical models as well as realistic neural networks, similar to what one finds in simple living organisms like the C.elegans worm.     

非线性网络的动力学复杂性研究

综述了非线性网络的动力学复杂性研究在网络理论、实证和应用方面所取得的主要进展和重要成果;深刻揭示了复杂网络的若干复杂性特征与基本定量规律;提出和建立了网络科学的统一混合理论体系(三部曲)和网络金字塔,并引入一类广义Farey组织的网络家族,阐明网络的复杂性-简单性与多样性-普适性之间转变关系;揭示了网络的拓扑结构特征与网络的动态特性之间关系;建立具有长程连接的规则网络的部分同步理论并应用于随机耦合的时空非线性系统的同步;提出复杂网络的动力学同步与控制多种方法;提出若干提高同步能力的模型、方法和途径,如同步最优和同步优先模型、同步与网络特征量关系、权重作用、叶子节点影响等;提出复杂混沌网络的多目标控制及具有小世界和无标度拓扑的束流输运网络的束晕-混沌控制方法;提出集群系统的自适应同步模型及蜂拥控制方法;探讨网络上拥塞与路由控制、资源博弈及不同类型网络上传播的若干规律;揭示含权经济科学家合作网及其演化特点;实证研究并揭示了多层次的高科技企业网和若干社会网络的特点;提出一种复杂网络的非平衡统计方法,把宏观网络推进到微观量子网络。     

Stabilization of chaotic and non-permanent food-web dynamics

Several decades of dynamical analyses of food-web networks [1-6] have led to important insights into the effects of complexity, omnivory and interaction strength on food-web stability [6-8]. Several recent insights [7, 8] are based on nonlinear bioenergetic consumer-resource models [9] that display chaotic behavior in three species food chains [10, 11] which can be stabilized by omnivory [7] and weak interaction of a fourth species [8]. We slightly relax feeding on low-density prey in these models by modifying standard food-web interactions known as type II functional responses [12]. This change drastically alters the dynamics of realistic systems containing up to ten species. Our modification stabilizes chaotic dynamics in three species systems and reduces or eliminates extinctions and non-persistent chaos [11] in ten species systems. This increased stability allows analysis of systems with greater biodiversity than in earlier work and suggests that dynamic stability is not as severe a constraint on the structure of large food webs as previously thought. The sensitivity of dynamical models to small changes in the predator-prey functional response well within the range of what is empirically observed suggests that functional response is a crucial aspect of species interactions that must be more precisely addressed in empirical studies.Received: 7 December 2003, Published online: 14 May 2004PACS: 05.45.-a Nonlinear dynamics and nonlinear dynamical systems - 05.45.Jn High-dimensional chaos - 05.45.Pq Numerical simulations of chaotic systems - 87.23.-n Ecology and evolution     

Bose-Einstein condensation in complex networks.

The evolution of many complex systems, including the World Wide Web, business, and citation networks, is encoded in the dynamic web describing the interactions between the system's constituents. Despite their irreversible and nonequilibrium nature these networks follow Bose statistics and can undergo Bose-Einstein condensation. Addressing the dynamical properties of these nonequilibrium systems within the framework of equilibrium quantum gases predicts that the "first-mover-advantage," "fit-get-rich," and "winner-takes-all" phenomena observed in competitive systems are thermodynamically distinct phases of the underlying evolving networks.     

Elementary models of dynamic networks

Inspecting the dynamics of networks opens a new dimension in understanding the interactions among the components of complex systems. Our goal is to understand the baseline properties expected from elementary random changes over time, in order to be able to assess the various effects found in longitudinal data. We created elementary dynamic models from classic random and preferential networks. Focusing on edge dynamics, we defined several processes for changing networks of a fixed size. We applied simple rules, including random, preferential and assortative modifications of existing edges – or a combination of these. Starting from initial Erdos-Rényi networks, we examined various basic network properties (e.g., density, clustering, average path length, number of components, degree distribution, etc.) of both snapshot and cumulative networks (for various lengths of aggregation time windows). Our results provide a baseline for changes to be expected in dynamic networks. We found universalities in the dynamic behavior of most network statistics. Furthermore, our findings suggest that certain network properties have a strong, non-trivial dependence on the length of the sampling window.     

Cut-offs and finite size effects in scale-free networks

We analyze the degree distributions cut-off in finite size scale-free networks. We show that the cut-off behavior with the number of vertices N is ruled by the topological constraints induced by the connectivity structure of the network. Even in the simple case of uncorrelated networks, we obtain an expression of the structural cut-off that is smaller than the natural cut-off obtained by means of extremal theory arguments. The obtained results are explicitly applied in the case of the configuration model to recover the size scaling of tadpoles and multiple edges.Received: 18 November 2003, Published online: 24 February 2004PACS: 89.75.-k Complex systems - 87.23.Ge Dynamics of social systems - 05.70.Ln Nonequilibrium and irreversible thermodynamics     

Chaotic dynamics on large networks

Many systems in nature are governed by a large number of agents that interact nonlinearly through complex feedback loops. When the networks are sufficiently large and interconnected, they typically exhibit self-organization and chaos. This paper examines the prevalence and degree of chaos on large unweighted recurrent networks of ordinary differential equations with sigmoidal nonlinearities and unit coupling. The largest Lyapunov exponent is used as the signature and measure of the chaos, and the study includes the effects of damping, asymmetries in the distribution of coupling strengths, network symmetry, and sparseness of connections. Minimum conditions and optimal network architectures are determined for the existence of chaos. The results have implications for the design of social and other networks in the real world in which weak chaos is deemed desirable or as a way of understanding why certain networks might exist on "the edge of chaos."     

From topology to dynamics in biochemical networks

Abstract formulations of the regulation of gene expression as random Boolean switching networks have been studied extensively over the past three decades. These models have been developed to make statistical predictions of the types of dynamics observed in biological networks based on network topology and interaction bias, p. For values of mean connectivity chosen to correspond to real biological networks, these models predict disordered dynamics. However, chaotic dynamics seems to be absent from the functioning of a normal cell. While these models use a fixed number of inputs for each element in the network, recent experimental evidence suggests that several biological networks have distributions in connectivity. We therefore study randomly constructed Boolean networks with distributions in the number of inputs, K, to each element. We study three distributions: delta function, Poisson, and power law (scale free). We analytically show that the critical value of the interaction bias parameter, p, above which steady state behavior is observed, is independent of the distribution in the limit of the number of elements N--> infinity. We also study these networks numerically. Using three different measures (types of attractors, fraction of elements that are active, and length of period), we show that finite, scale-free networks are more ordered than either the Poisson or delta function networks below the critical point. Thus the topology of scale-free biochemical networks, characterized by a wide distribution in the number of inputs per element, may provide a source of order in living cells. (c) 2001 American Institute of Physics.     

Modeling the clustering in citation networks

For the study of citation networks, a challenging problem is modeling the high clustering. Existing studies indicate that the promising way to model the high clustering is a copying strategy, i.e., a paper copies the references of its neighbor as its own references. However, the line of models highly underestimates the number of abundant triangles observed in real citation networks and thus cannot well model the high clustering. In this paper, we point out that the failure of existing models lies in that they do not capture the connecting patterns among existing papers. By leveraging the knowledge indicated by such connecting patterns, we further propose a new model for the high clustering in citation networks. Experiments on two real world citation networks, respectively from a special research area and a multidisciplinary research area, demonstrate that our model can reproduce not only the power-law degree distribution as traditional models but also the number of triangles, the high clustering coefficient and the size distribution of co-citation clusters as observed in these real networks.     

A deterministic small-world network created by edge iterations

Small-world networks are ubiquitous in real-life systems. Most previous models of small-world networks are stochastic. The randomness makes it more difficult to gain a visual understanding on how do different nodes of networks interact with each other and is not appropriate for communication networks that have fixed interconnections. Here we present a model that generates a small-world network in a simple deterministic way. Our model has a discrete exponential degree distribution. We solve the main characteristics of the model.     

Learning by message passing in networks of discrete synapses

We show that a message-passing process allows us to store in binary "material" synapses a number of random patterns which almost saturate the information theoretic bounds. We apply the learning algorithm to networks characterized by a wide range of different connection topologies and of size comparable with that of biological systems (e.g., [EQUATION: SEE TEXT]). The algorithm can be turned into an online-fault tolerant-learning protocol of potential interest in modeling aspects of synaptic plasticity and in building neuromorphic devices.     

Minimal attractors in digraph system models of neuronal networks

We study a class of discrete dynamical systems models of neuronal networks. In these models, each neuron is represented by a finite number of states and there are rules for how a neuron transitions from one state to another. In particular, the rules determine when a neuron fires and how this affects the state of other neurons. In an earlier paper [D. Terman, S. Ahn, X. Wang, W. Just, Reducing neuronal networks to discrete dynamics, Physica D 237 (2008) 324-338], we demonstrate that a general class of excitatory-inhibitory networks can, in fact, be rigorously reduced to the discrete model. In the present paper, we analyze how the connectivity of the network influences the dynamics of the discrete model. For randomly connected networks, we find two major phase transitions. If the connection probability is above the second but below the first phase transition, then starting in a generic initial state, most but not all cells will fire at all times along the trajectory as soon as they reach the end of their refractory period. Above the first phase transition, this will be true for all cells in a typical initial state; thus most states will belong to a minimal attractor of oscillatory behavior (in a sense that is defined precisely in the paper). The exact positions of the phase transitions depend on intrinsic properties of the cells including the lengths of the cells’ refractory periods and the thresholds for firing. Existence of these phase transitions is both rigorously proved for sufficiently large networks and corroborated by numerical experiments on networks of moderate size.     

Boolean delay equations: A simple way of looking at complex systems

Boolean Delay Equations (BDEs) are semi-discrete dynamical models with Boolean-valued variables that evolve in continuous time. Systems of BDEs can be classified into conservative or dissipative, in a manner that parallels the classification of ordinary or partial differential equations. Solutions to certain conservative BDEs exhibit growth of complexity in time; such BDEs can be seen therefore as metaphors for biological evolution or human history. Dissipative BDEs are structurally stable and exhibit multiple equilibria and limit cycles, as well as more complex, fractal solution sets, such as Devil’s staircases and “fractal sunbursts.” All known solutions of dissipative BDEs have stationary variance. BDE systems of this type, both free and forced, have been used as highly idealized models of climate change on interannual, interdecadal and paleoclimatic time scales. BDEs are also being used as flexible, highly efficient models of colliding cascades of loading and failure in earthquake modeling and prediction, as well as in genetics. In this paper we review the theory of systems of BDEs and illustrate their applications to climatic and solid-earth problems. The former have used small systems of BDEs, while the latter have used large hierarchical networks of BDEs. We moreover introduce BDEs with an infinite number of variables distributed in space (“partial BDEs”) and discuss connections with other types of discrete dynamical systems, including cellular automata and Boolean networks. This research-and-review paper concludes with a set of open questions.     

Statistical Ensembles for Economic Networks

Economic networks share with other social networks the fundamental property of sparsity. It is well known that the maximum entropy techniques usually employed to estimate or simulate weighted networks produce unrealistic dense topologies. At the same time, strengths should not be neglected, since they are related to core economic variables like supply and demand. To overcome this limitation, the exponential Bosonic model has been previously extended in order to obtain ensembles where the average degree and strength sequences are simultaneously fixed (conditional geometric model). In this paper a new exponential model, which is the network equivalent of Boltzmann ideal systems, is introduced and then extended to the case of joint degree-strength constraints (conditional Poisson model). Finally, the fitness of these alternative models is tested against a number of networks. While the conditional geometric model generally provides a better goodness-of-fit in terms of log-likelihoods, the conditional Poisson model could nevertheless be preferred whenever it provides a higher similarity with original data. If we are interested instead only in topological properties, the simple Bernoulli model appears to be preferable to the correlated topologies of the two more complex models.     

从统计物理学看复杂网络研究

从统计物理学来看,网络是一个包含了大量个体及个体之间相互作用的系统。本文从统计物理学的角度整理与总结了复杂网络目前的主要研究结果,并对将来的研究工作做了一个展望。文章把网络分为三个层次———无向网络、有向网络与加权网络,对不同网络的静态几何量研究的现状分别做了综述,并结合网络机制模型设计与评价的需要,提出了新的有待研究的静态几何量;对网络机制模型做了总结与分析,提出了有待解决的关于双向幂律网络的机制模型的问题;部分地概括了网络演化性质,网络的结构稳定性以及网络上的动力学模型的研究。然后,以我们目前正在进行的两个方面的工作—科学家网络和产品生产关系网络—为例,粗略地介绍了网络研究在一些实际问题中的应用。最后,作为一个简单的补充和索引,我们整理了复杂网络研究中部分常用的解析与数值计算的方法。     

Vibrational resonance in excitable neuronal systems

In this paper, we investigate the effect of a high-frequency driving on the dynamical response of excitable neuronal systems to a subthreshold low-frequency signal by numerical simulation. We demonstrate the occurrence of vibrational resonance in spatially extended neuronal networks. Different network topologies from single small-world networks to modular networks of small-world subnetworks are considered. It is shown that an optimal amplitude of high-frequency driving enhances the response of neuron populations to a low-frequency signal. This effect of vibrational resonance of neuronal systems depends extensively on the network structure and parameters, such as the coupling strength between neurons, network size, and rewiring probability of single small-world networks, as well as the number of links between different subnetworks and the number of subnetworks in the modular networks. All these parameters play a key role in determining the ability of the network to enhance the outreach of the localized subthreshold low-frequency signal. Considering that two-frequency signals are ubiquity in brain dynamics, we expect the presented results could have important implications for the weak signal detection and information propagation across neuronal systems.     

从统计物理学看复杂网络研究

从统计物理学来看，网络是一个包含了大量个体及个体之间相互作用的系统。本文从统计物理学的角度整理与总结了复杂网络目前的主要研究结果，并对将来的研究工作做了一个展望。文章把网络分为三个层次——无向网络、有向网络与加权网络，对不同网络的静态几何量研究的现状分别做了综述，并结合网络机制模型设计与评价的需要，提出了新的有待研究的静态几何量；对网络机制模型做了总结与分析，提出了有待解决的关于双向幂律网络的机制模型的问题；部分地概括了网络演化性质，网络的结构稳定性以及网络上的动力学模型的研究。然后，以我们目前正在进行的两个方面的工作—科学家网络和产品生产关系网络一为例，粗略地介绍了网络研究在一些实际问题中的应用。最后，作为一个简单的补充和索引，我们整理了复杂网络研究中部分常用的解析与数值计算的方法。     

Efficiency and robustness in ant networks of galleries

Recent theoretical and empirical studies have focused on the topology of large networks of communication/interactions in biological, social and technological systems. Most of them have been studied in the scope of the small-world and scale-free networks theory. Here we analyze the characteristics of ant networks of galleries produced in a 2-D experimental setup. These networks are neither small-worlds nor scale-free networks and belong to a particular class of network, i.e. embedded planar graphs emerging from a distributed growth mechanism. We compare the networks of galleries with both minimal spanning trees and greedy triangulations. We show that the networks of galleries have a path system efficiency and robustness to disconnections closer to the one observed in triangulated networks though their cost is closer to the one of a tree. These networks may have been prevented to evolve toward the classes of small-world and scale-free networks because of the strong spatial constraints under which they grow, but they may share with many real networks a similar trend to result from a balance of constraints leading them to achieve both path system efficiency and robustness at low cost.Received: 16 July 2004, Published online: 26 November 2004PACS: 89.75.Fb Structures and organization in complex systems - 89.75.Hc Networks and genealogical trees - 87.23.Ge Dynamics of social systems