Reconstruction of noise-driven nonlinear dynamic networks with some hidden nodes

The problem of network reconstruction, particularly exploring unknown network structures by analyzing measurable output data from networks, has attracted significant interest in many interdisciplinary fields in recent times. In practice, networks may be very large, and data can often be measured for only some of the nodes in a network while data for other variables are hidden. It is thus crucial to be able to infer networks from partial data. In this article, we study the problem of noise-driven nonlinear networks with some hidden nodes. Various difficulties appear jointly: nonlinearity of network dynamics, the impact of strong noise, the complexity of interaction structures between network nodes, and missing data from certain hidden nodes. We propose using high-order correlation to treat nonlinearity and structural complexity, two-time correlation to decorrelate noise, and higherorder derivatives to overcome the difficulties of hidden nodes. A closed form of network reconstruction is derived, and numerical simulations confirm the theoretical predictions.     

A local-world heterogeneous model of wireless sensor networks with node and link diversity

In this paper, we present a novel local-world model of wireless sensor networks (WSN) with two kinds of nodes: sensor nodes and sink nodes, which is different from other models with identical nodes and links. The model balances energy consumption by limiting the connectivity of sink nodes to prolong the life of the network. How the proportion of sink nodes, different energy distribution and the local-world scale would affect the topological structure and network performance are investigated. We find that, using mean-field theory, the degree distribution is obtained as an integral with respect to the proportion of sink nodes and energy distribution. We also show that, the model exhibits a mixed connectivity correlation which is greatly distinct from general networks. Moreover, from the perspective of the efficiency and the average hops for data processing, we find some suitable range of the proportion p of sink nodes would make the network model have optimal performance for data processing.     

Studies on controllability of directed networks with extremal optimization

Almost all natural, social and man-made-engineered systems can be represented by a complex network to describe their dynamic behaviors. To make a real-world complex network controllable with its desired topology, the study on network controllability has been one of the most critical and attractive subjects for both network and control communities. In this paper, based on a given directed–weighted network with both state and control nodes, a novel optimization tool with extremal dynamics to generate an optimal network topology with minimum control nodes and complete controllability under Kalman’s rank condition has been developed. The experimental results on a number of popular benchmark networks show the proposed tool is effective to identify the minimum control nodes which are sufficient to guide the whole network’s dynamics and provide the evolution of network topology during the optimization process. We also find the conclusion: “the sparse networks need more control nodes than the dense, and the homogeneous networks need fewer control nodes compared to the heterogeneous” (Liu et al., 2011  [18]), is also applicable to network complete controllability. These findings help us to understand the network dynamics and make a real-world network under the desired control. Moreover, compared with the relevant research results on structural controllability with minimum driver nodes, the proposed solution methodology may also be applied to other constrained network optimization problems beyond complete controllability with minimum control nodes.     

Detecting community structure from coherent oscillation of excitable systems

Many networks are proved to have community structures. On the basis of the fact that the dynamics on networks are intensively affected by the related topology, in this paper the dynamics of excitable systems on networks and a corresponding approach for detecting communities are discussed. Dynamical networks are formed by interacting neurons; each neuron is described using the FHN model. For noisy disturbance and appropriate coupling strength, neurons may oscillate coherently and their behavior is tightly related to the community structure. Synchronization between nodes is measured in terms of a correlation coefficient based on long time series. The correlation coefficient matrix can be used to project network topology onto a vector space. Then by the K-means cluster method, the communities can be detected. Experiments demonstrate that our algorithm is effective at discovering community structure in artificial networks and real networks, especially for directed networks. The results also provide us with a deep understanding of the relationship of function and structure for dynamical networks.     

Synchronization criterion for Lur'e type complex dynamical networks with time-varying delay

In this Letter, the synchronization problem for a class of complex dynamical networks in which every identical node is a Lur'e system with time-varying delay is considered. A delay-dependent synchronization criterion is derived for the synchronization of complex dynamical network that represented by Lur'e system with sector restricted nonlinearities. The derived criterion is a sufficient condition for absolute stability of error dynamics between the each nodes and the isolated node. Using a convex representation of the nonlinearity for error dynamics, the stability condition based on the discretized Lyapunov-Krasovskii functional is obtained via LMI formulation. The proposed delay-dependent synchronization criterion is less conservative than the existing ones. The effectiveness of our work is verified through numerical examples.     

Assortative mixing in networks

A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numerically. Within this model we find that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.     

Accelerating networks: Effects of preferential connections

Networks are commonly observed structures in complex systems with interacting and interdependent parts that self-organize. For nonlinearly growing networks, when the total number of connections increases faster than the total number of nodes, the network is said to accelerate. We propose a systematic model for the dynamics of growing networks represented by distribution kinetics equations. We define the nodal-linkage distribution, construct a population dynamics equation based on the association-dissociation process, and perform the moment calculations to describe the dynamics of such networks. For nondirectional networks with finite numbers of nodes and connections, the moments are the total number of nodes, the total number of connections, and the degree (the average number of connections per node), represented by the average moment. Size independent rate coefficients yield an exponential network describing the network without preferential attachment, and size dependent rate coefficients produce a power law network with preferential attachment. The model quantitatively describes accelerating network growth data for a supercomputer (Earth Simulator), for regulatory gene networks, and for the Internet.     

Photonic quantum network transmission assisted by the weak cross-Kerr nonlinearity

Classical network coding permits all internal nodes to encode or decode the incoming messages over proper fields in order to complete a network multicast. Similar quantum encoding scheme cannot be easily followed because of various quantum no-go theorems. In this paper, to avoid these theorems in quantum multiple-source networks, we present a photonic strategy by exploring quantum transferring approaches assisted by the weak cross-Kerr nonlinearity. The internal node may nearly deterministically fuse all incoming photons into a single photon with multiple modes. The fused single photon may be transmitted using two- photonic hyperentanglement as a quantum resource. The quantum splitting as the inverse operation of the quantum fusion allows forwarding quantum states under the quantum no-cloning theorem. Furthermore, quantum addressing schemes are presented to complete the quantum transmissions on multiple-source networks going beyond the classical network broadcasts or quantum n-pair transmissions in terms of their reduced forms.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

Synchronization in uncertain complex networks

We consider the problem of synchronization in uncertain generic complex networks. For generic complex networks with unknown dynamics of nodes and unknown coupling functions including uniform and nonuniform inner couplings, some simple linear feedback controllers with updated strengths are designed using the well-known LaSalle invariance principle. The state of an uncertain generic complex network can synchronize an arbitrary assigned state of an isolated node of the network. The famous Lorenz system is stimulated as the nodes of the complex networks with different topologies. We found that the star coupled and scale-free networks with nonuniform inner couplings can be in the state of synchronization if only a fraction of nodes are controlled.     

Motif structure and cooperation in real-world complex networks

Networks of dynamical nodes serve as generic models for real-world systems in many branches of science ranging from mathematics to physics, technology, sociology and biology. Collective behavior of agents interacting over complex networks is important in many applications. The cooperation between selfish individuals is one of the most interesting collective phenomena. In this paper we address the interplay between the motifs’ cooperation properties and their abundance in a number of real-world networks including yeast protein-protein interaction, human brain, protein structure, email communication, dolphins’ social interaction, Zachary karate club and Net-science coauthorship networks. First, the amount of cooperativity for all possible undirected subgraphs with three to six nodes is calculated. To this end, the evolutionary dynamics of the Prisoner’s Dilemma game is considered and the cooperativity of each subgraph is calculated as the percentage of cooperating agents at the end of the simulation time. Then, the three- to six-node motifs are extracted for each network. The significance of the abundance of a motif, represented by a Z-value, is obtained by comparing them with some properly randomized versions of the original network. We found that there is always a group of motifs showing a significant inverse correlation between their cooperativity amount and Z-value, i.e. the more the Z-value the less the amount of cooperativity. This suggests that networks composed of well-structured units do not have good cooperativity properties.     

Information theoretic description of networks

We present a new information theoretic approach for network characterizations. It is developed to describe the general type of networks with n nodes and L directed and weighted links, i.e., it also works for the simpler undirected and unweighted networks. The new information theoretic measures for network characterizations are based on a transmitter-receiver analogy of effluxes and influxes. Based on these measures, we classify networks as either complex or non-complex and as either democracy or dictatorship networks. Directed networks, in particular, are furthermore classified as either information spreading and information collecting networks.The complexity classification is based on the information theoretic network complexity measure medium articulation (MA). It is proven that special networks with a medium number of links (L∼n^1.5) show the theoretical maximum complexity . A network is complex if its MA is larger than the average MA of appropriately randomized networks: MA>MA_r. A network is of the democracy type if its redundancy R<R_r, otherwise it is a dictatorship network. In democracy networks all nodes are, on average, of similar importance, whereas in dictatorship networks some nodes play distinguished roles in network functioning. In other words, democracy networks are characterized by cycling of information (or mass, or energy), while in dictatorship networks there is a straight through-flow from sources to sinks. The classification of directed networks into information spreading and information collecting networks is based on the conditional entropies of the considered networks (H(A/B)=uncertainty of sender node if receiver node is known, H(B/A)=uncertainty of receiver node if sender node is known): if H(A/B)>H(B/A), it is an information collecting network, otherwise an information spreading network.Finally, different real networks (directed and undirected, weighted and unweighted) are classified according to our general scheme.     

Spectral coarse graining and synchronization in oscillator networks

Coarse graining techniques offer a promising alternative to large-scale simulations of complex dynamical systems, as long as the coarse-grained system is truly representative of the initial one. Here, we investigate how the dynamical properties of oscillator networks are affected when some nodes are merged together to form a coarse-grained network. Moreover, we show that there exists a way of grouping nodes preserving as much as possible some crucial aspects of the network dynamics. This coarse graining approach provides a useful method to simplify complex oscillator networks, and more generally, networks whose dynamics involves a Laplacian matrix.     

花簇分形无标度网络中节点影响力的区分度

大量研究表明分形尺度特性广泛存在于真实复杂系统中, 且分形结构显著影响网络上的传播动力学行为. 虽然复杂网络的节点传播影响力吸引了越来越多学者的关注, 但依旧缺乏针对分形网络结构的节点影响力的系统研究. 鉴于此, 本文基于花簇分形网络模型, 研究了分形无标度结构上的节点传播影响力. 首先, 对比了不同分形维数下的节点影响力, 结果表明, 当分形维数很小时, 节点影响力的区分度几乎不随节点度变化, 很难区分不同节点的传播影响力, 而随着分形维数的增大, 从全局和局域角度都能很容易识别网络中的超级传播源. 其次, 通过对原分形网络进行不同程度的随机重连来分析网络噪声对节点影响力区分度的影响, 发现在低维分形网络上, 加入网络噪声之后能够容易区分不同节点的影响力, 而在无穷维超分形网络中, 加入网络噪声之后能够区分中间度节点的影响力, 但从全局和局域角度都很难识别中心节点的影响力. 所得结论进一步补充、深化了基于花簇分形网络的节点影响力研究, 研究结果对实际病毒传播的预警控制提供了一定的理论借鉴.     

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.     

Ranking spreaders by decomposing complex networks

Ranking the nodes? ability of spreading in networks is crucial for designing efficient strategies to hinder spreading in the case of diseases or accelerate spreading in the case of information dissemination. In the well-known k-shell method, nodes are ranked only according to the links between the remaining nodes (residual links) while the links connecting to the removed nodes (exhausted links) are entirely ignored. In this Letter, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic spreading process on real networks, we show that the MDD method can outperform the k-shell and degree methods in ranking spreaders.     

Modelling of weighted evolving networks with community structures

Many social and biological networks consist of communities–groups of nodes within which links are dense but among which links are sparse. It turns out that most of these networks are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the link weights among their nodes. Recently, there are considerable interests in the study of properties as well as modelling of such networks with community structures. To our knowledge, however, no study of any weighted network model with such a community structure has been presented in the literature to date. In this paper, we propose a weighted evolving network model with a community structure. The new network model is based on the inner-community and inter-community preferential attachments and preferential strengthening mechanism. Simulation results indicate that this network model indeed reflect the intrinsic community structure, with various power-law distributions of the node degrees, link weights, and node strengths.     

PageRank centrality for temporal networks

In this paper, we propose a new centrality measure for ranking the nodes and time layers of temporal networks simultaneously, referred to as the f-PageRank centrality. The f-PageRank values of nodes and time layers in temporal networks are obtained by solving the eigenvector of a multi-homogeneous map. The existence and uniqueness of the proposed centrality measure are also guaranteed by existing results, under some reasonable conditions. The numerical experiments on a synthetic temporal network and two real-world temporal networks (i.e., Email-Eu-core and CollegeMsg temporal networks) show that the proposed centrality outperforms some existing centrality measures.     

Choosing effective controlled nodes for scale-free network synchronization

Previous studies concerning pinning control of complex-network synchronization have very often demonstrated that in an unweighted symmetrical scale-free network, controlling the high-degree nodes is more efficient than controlling randomly chosen ones; due to the heterogeneity of the node-degree or edge-connection distribution of the scale-free network, small-degree nodes have relatively high probabilities of being chosen at random but their control has less influence on the other nodes through the network. This raises the question of whether or not controlling the high-degree nodes is always better than controlling the small ones in scale-free networks. Our answer to this is yes and no. In this study, we carry out extensive numerical simulations to show that in an unweighted symmetrical Barabasi-Albert scale-free network, when the portion of controlled nodes is relatively large, controlling the small nodes becomes better than controlling the big nodes and controlling randomly chosen nodes has approximately the same effect as controlling the big ones. However, we also show that for normalized weighted scale-free networks, controlling the big nodes is in fact always better than controlling the small ones.     

微博双向“关注”网络节点中心性及传播 影响力的分析

根据新浪微博的实际数据, 建立了两个基于双向“关注”的用户关系网络, 通过分析网络拓扑统计特征, 发现二者均具有小世界、无标度特征. 通过对节点度、紧密度、介数和k-core 四个网络中心性指标进行实证分析, 发现节点度服从分段幂率分布; 介数相比其他中心性指标差异性最为显著; 两个网络均具有明显的层次性, 但不是所有度值大的节点核数也大; 全局范围内各中心性指标之间存在着较强的相关性, 但在度值较大的节点群这种相关性明显减弱. 此外, 借助基于传染病动力学的SIR信息传播模型来分析四种指标在刻画节点传播能力方面的差异性, 仿真结果表明, 选择具有不同中心性指标的初始传播节点, 对信息传播速度和范围均具有不同影响; 紧密度和k-core较其他指标可以更加准确地描述节点在信息传播中所处的网络核心位置, 这有助于识别信息传播拓扑网络中的关键节点.