复杂网络可控性研究现状综述

控制复杂系统是人们对复杂系统模型结构及相关动力学进行研究的最终目标, 反映人们对复杂系统的认识能力. 近年来, 通过控制理论和复杂性科学相结合,复杂网络可控性的研究引起了人们的广泛关注. 在过去的几年内, 来自国内外不同领域的研究人员从不同的角度对复杂网络可控性进行了深入的分析研究, 取得了丰硕的成果. 本文重点讨论了复杂网络的结构可控性研究进展, 详细介绍了基于最大匹配方法的复杂网络结构可控性分析框架, 综述了自2011年以来复杂网络可控性的相关研究成果, 具体论述了不同类型的可控性、可控性与网络拓扑结构统计特征的关联、基于可控性的网络及节点度量、控制的鲁棒性和可控性的相关优化方法. 最后, 对网络可控性未来的研究动态进行了展望, 有助于国内同行开展网络可控性的相关研究.     

Counting spanning trees in a small-world Farey graph

The problem of spanning trees is closely related to various interesting problems in the area of statistical physics, but determining the number of spanning trees in general networks is computationally intractable. In this paper, we perform a study on the enumeration of spanning trees in a specific small-world network with an exponential distribution of vertex degrees, which is called a Farey graph since it is associated with the famous Farey sequence. According to the particular network structure, we provide some recursive relations governing the Laplacian characteristic polynomials of a Farey graph and its subgraphs. Then, making use of these relations obtained here, we derive the exact number of spanning trees in the Farey graph, as well as an approximate numerical solution for the asymptotic growth constant characterizing the network. Finally, we compare our results with those of different types of networks previously investigated.     

Investigation of Commuting Hamiltonian in Quantum Markov Network

Graphical Models have various applications in science and engineering which include physics, bioinformatics, telecommunication and etc. Usage of graphical models needs complex computations in order to evaluation of marginal functions, so there are some powerful methods including mean field approximation, belief propagation algorithm and etc. Quantum graphical models have been recently developed in context of quantum information and computation, and quantum statistical physics, which is possible by generalization of classical probability theory to quantum theory. The main goal of this paper is preparing a primary generalization of Markov network, as a type of graphical models, to quantum case and applying in quantum statistical physics. We have investigated the Markov network and the role of commuting Hamiltonian terms in conditional independence with simple examples of quantum statistical physics.     

Percolation on networks with dependence links

As a classical model of statistical physics, the percolation theory provides a powerful approach to analyze the network structure and dynamics. Recently, to model the relations among interacting agents beyond the connection of the networked system, the concept of dependence link is proposed to represent the dependence relationship of agents. These studies suggest that the percolation properties of these networks differ greatly from those of the ordinary networks. In particular,unlike the well known continuous transition on the ordinary networks, the percolation transitions on these networks are discontinuous. Moreover, these networks are more fragile for a broader degree distribution, which is opposite to the famous results for the ordinary networks. In this article, we give a summary of the theoretical approaches to study the percolation process on networks with inter- and inner-dependence links, and review the recent advances in this field, focusing on the topology and robustness of such networks.     

Statistical mechanics of the directed 2-distance minimal dominating set problem

The directed L-distance minimal dominating set (MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi (ER) random graph and regular random (RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation (BP) algorithm does not converge when the inverse temperature β exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds 3.3; there is no entropy transition point (or $\beta =\infty $) in other circumstances. Third, the results of the replica symmetry (RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm.     

A preliminary investigation on the topology of Chinese and climate networks

Complex networks have been studied across many fields of science in recent years. In this paper, we give a brief introduction of networks, then follow the original works by Tsonis et al (2004, 2006) starting with data of the surface temperature from 160 Chinese weather observations to investigate the topology of Chinese climate networks. Results show that the Chinese climate network exhibits a characteristic of regular, almost fully connected networks, which means that most nodes in this case have the same number of links, and so-called super nodes with a very large number of links do not exist there. In other words, though former results show that nodes in the extratropical region provide a property of scale-free networks, they still have other different local fine structures inside. We also detect the community of the Chinese climate network by using a Bayesian technique; the effective number of communities of the Chinese climate network is about four in this network. More importantly, this technique approaches results in divisions which have connections with physics and dynamics; the division into communities may highlight the aspects of the dynamics of climate variability.     

How Gibbs Distributions May Naturally Arise from Synaptic Adaptation Mechanisms. A Model-Based Argumentation

This paper addresses two questions in the context of neuronal networks dynamics, using methods from dynamical systems theory and statistical physics: (i) How to characterize the statistical properties of sequences of action potentials (“spike trains”) produced by neuronal networks? and; (ii) what are the effects of synaptic plasticity on these statistics? We introduce a framework in which spike trains are associated to a coding of membrane potential trajectories, and actually, constitute a symbolic coding in important explicit examples (the so-called gIF models). On this basis, we use the thermodynamic formalism from ergodic theory to show how Gibbs distributions are natural probability measures to describe the statistics of spike trains, given the empirical averages of prescribed quantities. As a second result, we show that Gibbs distributions naturally arise when considering “slow” synaptic plasticity rules where the characteristic time for synapse adaptation is quite longer than the characteristic time for neurons dynamics.     

Voter model on adaptive networks

Voter model is an important basic model in statistical physics. In recent years, it has been more and more used to describe the process of opinion formation in sociophysics. In real complex systems, the interactive network of individuals is dynamically adjusted, and the evolving network topology and individual behaviors affect each other. Therefore, we propose a linking dynamics to describe the coevolution of network topology and individual behaviors in this paper, and study the voter model on the adaptive network. We theoretically analyze the properties of the voter model, including consensus probability and time. The evolution of opinions on dynamic networks is further analyzed from the perspective of evolutionary game. Finally, a case study of real data is shown to verify the effectiveness of the theory.     

Synchronization of oscillators in complex networks

Theory of identical or complete synchronization of identical oscillators in arbitrary networks is introduced. In addition, several graph theory concepts and results that augment the synchronization theory and a tie in closely to random, semirandom, and regular networks are introduced. Combined theories are used to explore and compare three types of semirandom networks for their efficacy in synchronizing oscillators. It is shown that the simplest k-cycle augmented by a few random edges or links are the most efficient network that will guarantee good synchronization.      

Universal scaling for the dilemma strength in evolutionary games

Why would natural selection favor the prevalence of cooperation within the groups of selfish individuals? A fruitful framework to address this question is evolutionary game theory, the essence of which is captured in the so-called social dilemmas. Such dilemmas have sparked the development of a variety of mathematical approaches to assess the conditions under which cooperation evolves. Furthermore, borrowing from statistical physics and network science, the research of the evolutionary game dynamics has been enriched with phenomena such as pattern formation, equilibrium selection, and self-organization. Numerous advances in understanding the evolution of cooperative behavior over the last few decades have recently been distilled into five reciprocity mechanisms: direct reciprocity, indirect reciprocity, kin selection, group selection, and network reciprocity. However, when social viscosity is introduced into a population via any of the reciprocity mechanisms, the existing scaling parameters for the dilemma strength do not yield a unique answer as to how the evolutionary dynamics should unfold. Motivated by this problem, we review the developments that led to the present state of affairs, highlight the accompanying pitfalls, and propose new universal scaling parameters for the dilemma strength. We prove universality by showing that the conditions for an ESS and the expressions for the internal equilibriums in an infinite, well-mixed population subjected to any of the five reciprocity mechanisms depend only on the new scaling parameters. A similar result is shown to hold for the fixation probability of the different strategies in a finite, well-mixed population. Furthermore, by means of numerical simulations, the same scaling parameters are shown to be effective even if the evolution of cooperation is considered on the spatial networks (with the exception of highly heterogeneous setups). We close the discussion by suggesting promising directions for future research including (i) how to handle the dilemma strength in the context of co-evolution and (ii) where to seek opportunities for applying the game theoretical approach with meaningful impact.     

Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

The legacy of Joseph Fourier in science is vast, especially thanks to the essential tool that the Fourier transform is. The flexibility of this analysis, its computational efficiency and the physical interpretation it offers makes it a cornerstone in many scientific domains. With the explosion of digital data, both in quantity and diversity, the generalization of the tools based on Fourier transform is mandatory. In data science, new problems arose for the processing of irregular data such as social networks, biological networks or other data on networks. Graph signal processing is a promising approach to deal with those. The present text is an overview of the state of the art in graph signal processing, focusing on how to define a Fourier transform for data on graphs, how to interpret it and how to use it to process such data. It closes showing some examples of use. Along the way, the review reveals how Fourier's work remains modern and universal, and how his concepts, coming from physics and blended with mathematics, computer science, and signal processing, play a key role in answering the modern challenges in data science.     

Dependence of the average to-node distance on the node degree for random graphs and growing networks

In a connected graph, nodes can be characterised locally (with their degree k) or globally (e.g. with their average length path to other nodes). Here we investigate how depends on k. The numerical algorithm based on the construction of the distance matrix is applied to random graphs and the growing networks: the scale-free ones and the exponential ones. The results are relevant for search strategies in different networks.Received: 15 June 2004, Published online: 21 October 2004PACS: 02.10.Ox Combinatorics; graph theory - 05.10.-a Computational methods in statistical physics and nonlinear dynamics     

Complex networks

We briefly describe the toolkit used for studying complex systems: nonlinear dynamics, statistical physics, and network theory. We place particular emphasis on network theory--the topic of this special issue--and its importance in augmenting the framework for the quantitative study of complex systems. In order to illustrate the main issues, we briefly review several areas where network theory has led to significant developments in our understanding of complex systems. Specifically, we discuss changes, arising from network theory, in our understanding of (i) the Internet and other communication networks, (ii) the structure of natural ecosystems, (iii) the spread of diseases and information, (iv) the structure of cellular signalling networks, and (v) infrastructure robustness. Finally, we discuss how complexity requires both new tools and an augmentation of the conceptual framework--including an expanded definition of what is meant by a quantitative prediction.Received: 12 November 2003, Published online: 14 May 2004PACS: 89.75.Fb Structures and organization in complex systems - 89.75.Da Systems obeying scaling laws     

Discrete simulation of fluid dynamics

In this special issue, an overview of the Thematic Institute (TI) on Information and Material Flows in Complex Systems is given. The TI was carried out within EXYSTENCE, the first EU Network of Excellence in the area of complex systems. Its motivation, research approach and subjects are presented here. Among the various methods used are many-particle and statistical physics, nonlinear dynamics, as well as complex systems, network and control theory. The contributions are relevant for complex systems as diverse as vehicle and data traffic in networks, logistics, production, and material flows in biological systems. The key disciplines involved are socio-, econo-, traffic- and bio-physics, and a new research area that could be called “biologistics”.     

Stability and dynamical properties of material flow systems on random networks

The theory of complex networks and of disordered systems is used to study the stability and dynamical properties of a simple model of material flow networks defined on random graphs. In particular we address instabilities that are characteristic of flow networks in economic, ecological and biological systems. Based on results from random matrix theory, we work out the phase diagram of such systems defined on extensively connected random graphs, and study in detail how the choice of control policies and the network structure affects stability. We also present results for more complex topologies of the underlying graph, focussing on finitely connected Erdös-Réyni graphs, Small-World Networks and Barabási-Albert scale-free networks. Results indicate that variability of input-output matrix elements, and random structures of the underlying graph tend to make the system less stable, while fast price dynamics or strong responsiveness to stock accumulation promote stability.     

Potts model on complex networks

We consider the general p-state Potts model on random networks with a given degree distribution (random Bethe lattices). We find the effect of the suppression of a first order phase transition in this model when the degree distribution of the network is fat-tailed, that is, in more precise terms, when the second moment of the distribution diverges. In this situation the transition is continuous and of infinite order, and size effect is anomalously strong. In particular, in the case of p = 1, we arrive at the exact solution, which coincides with the known solution of the percolation problem on these networks.Received: 3 December 2003, Published online: 17 February 2004PACS: 05.10.-a Computational methods in statistical physics and nonlinear dynamics - 05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion - 05.50. + q Lattice theory and statistics (Ising, Potts, etc.) - 87.18.Sn Neural networks     

Components in time-varying graphs

Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, today it is possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of time-varying graphs, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the affine graph. It is, therefore, an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis.     

Coupled disease–behavior dynamics on complex networks: A review

It is increasingly recognized that a key component of successful infection control efforts is understanding the complex, two-way interaction between disease dynamics and human behavioral and social dynamics. Human behavior such as contact precautions and social distancing clearly influence disease prevalence, but disease prevalence can in turn alter human behavior, forming a coupled, nonlinear system. Moreover, in many cases, the spatial structure of the population cannot be ignored, such that social and behavioral processes and/or transmission of infection must be represented with complex networks. Research on studying coupled disease–behavior dynamics in complex networks in particular is growing rapidly, and frequently makes use of analysis methods and concepts from statistical physics. Here, we review some of the growing literature in this area. We contrast network-based approaches to homogeneous-mixing approaches, point out how their predictions differ, and describe the rich and often surprising behavior of disease–behavior dynamics on complex networks, and compare them to processes in statistical physics. We discuss how these models can capture the dynamics that characterize many real-world scenarios, thereby suggesting ways that policy makers can better design effective prevention strategies. We also describe the growing sources of digital data that are facilitating research in this area. Finally, we suggest pitfalls which might be faced by researchers in the field, and we suggest several ways in which the field could move forward in the coming years.