Pinning control of complex dynamical networks with general topology

Recently, the researches on pinning control of complex dynamical networks have mainly focused on such networks with very specific coupling schemes (e.g., symmetric coupling, uniform coupling and linear coupling). However, most real networks often consist of local units, which interact with each other via asymmetric and heterogeneous connections. In this paper, pinning control of a continuous-time complex dynamical network with general coupling topologies is studied. Some generic stability criteria based on master stability function (MSF) are derived for such a general controlled network, which guarantee that the whole network can be pinned to its equilibrium by placing feedback control only on a small fraction of nodes. Then, these results are extended to discrete-time case. Previous results about symmetric, uniform or linear coupled networks in this area are included as special cases of the present work. Numerical simulations of directed networks with weighted coupling pinned by specifically selective pinning scheme are given for illustration and verification.     

On coordination and continuous hawk-dove games on small-world networks

It is argued that small-world networks are more suitable than ordinary graphs in modelling the diffusion of a concept (e.g. a technology, a disease, a tradition, ...). The coordination game with two strategies is studied on small-world networks, and it is shown that the time needed for a concept to dominate almost all of the network is of order , where N is the number of vertices. This result is different from regular graphs and from a result obtained by Young. The reason for the difference is explained. Continuous hawk-dove game is defined and a corresponding dynamical system is derived. Its steady state and stability are studied. Replicator dynamics for continuous hawk-dove game is derived without the concept of population. The resulting finite difference equation is studied. Finally continuous hawk-dove is simulated on small-world networks using Nash updating rule. The system is 2-cyclic for all the studied range. Received 8 July 2000 and Received in final form 23 July 2000     

Critical behavior of blind spots in sensor networks

Blind spots in sensor networks, i.e., individual nodes or small groups of nodes isolated from the rest of the network, are of great concern as they may significantly degrade the network's ability to collect and process information. As the operations of many types of sensors in realistic applications rely on short-lifetime power supplies (e.g., batteries), once they are used up ("off"), replacements become necessary ("on"). This off-and-on process can lead to blind spots. An issue of both theoretical and practical interest concerns the dynamical process and the critical behavior associated with the occurrence of blind spots. In particular, there can be various network topologies, and the off-and-on process can be characterized by the probability that a node functions normally, or the occupying probability of a node in the network. The question to be addressed in this paper concerns how the dynamics of blind spots depend on the network topology and on the occupying probability. For regular, random, and mixed networks, we provide theoretical formulas relating the probability of blind spots to the occupying probability, from which the critical point for the occurrence of blind spots can be determined. For scale-free networks, we present a procedure to estimate the critical point. While our theoretical and numerical analyses are presented in the framework of sensor networks, we expect our results to be generally applicable to network partitioning issues in other networks, such as the wireless cellular network, the Internet, or transportation networks, where the issue of blind spots may be of concern.     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

动态复杂网络中节点影响力的研究进展

节点影响力的识别和预测具有重要的理论意义和应用价值,是复杂网络的热点研究领域.目前大多数研究方法都是针对静态网络或动态网络某一时刻的快照进行的,然而在实际应用场景中,社会、生物、信息、技术等复杂网络都是动态演化的.因此在动态复杂网络中评估节点影响力以及预测节点未来影响力,特别是在网络结构变化之前的预测更具意义.本文系统地总结了动态复杂网络中节点影响力算法面临的三类挑战,即在增长网络中,节点影响力算法的计算复杂性和时间偏见;网络实时动态演化时,节点影响力算法的适应性;网络结构微扰或突变时,节点影响力算法的鲁棒性,以及利用网络结构演变阐释经济复杂性涌现的问题.最后总结了这一研究方向几个待解决的问题并指出未来可能的发展方向.     

Cluster projective synchronization between community networks with nonidentical nodes

In this paper, cluster projective synchronization between community networks with nonidentical nodes is investigated. Outer synchronization between two identical or nonidentical complex networks has been extensively studied, in which all the nodes synchronized each other in a common manner. However, in real community networks, different communities in networks usually synchronize with each other in a different manner, i.e., achieving cluster projective synchronization. Based on Lyapunov stability theory, sufficient conditions for achieving cluster projective synchronization are derived through designing proper controllers. Numerical simulations are provided to verify the correctness and effectiveness of the derived theoretical results.     

An efficient approach of controlling traffic congestion in scale-free networks

We propose and study a model of traffic in communication networks. The underlying network has a structure that is tunable between a scale-free growing network with preferential attachments and a random growing network. To model realistic situations where different nodes in a network may have different capabilities, the message or packet creation and delivering rates at a node are assumed to depend on the degree of the node. Noting that congestions are more likely to take place at the nodes with high degrees in networks with scale-free character, an efficient approach of selectively enhancing the message-processing capability of a small fraction (e.g. 3%) of the nodes is shown to perform just as good as enhancing the capability of all nodes. The interplay between the creation rate and the delivering rate in determining non-congested or congested traffic in a network is studied more numerically and analytically.     

Optimization and scale-freeness for complex networks

Complex networks are mapped to a model of boxes and balls where the balls are distinguishable. It is shown that the scale-free size distribution of boxes maximizes the information associated with the boxes provided configurations including boxes containing a finite fraction of the total amount of balls are excluded. It is conjectured that for a connected network with only links between different nodes, the nodes with a finite fraction of links are effectively suppressed. It is hence suggested that for such networks the scale-free node-size distribution maximizes the information encoded on the nodes. The noise associated with the size distributions is also obtained from a maximum entropy principle. Finally, explicit predictions from our least bias approach are found to be borne out by metabolic networks.     

Concentric characterization and classification of complex network nodes: Application to an institutional collaboration network

Differently from theoretical scale-free networks, most real networks present multi-scale behavior, with nodes structured in different types of functional groups and communities. While the majority of approaches for classification of nodes in a complex network has relied on local measurements of the topology/connectivity around each node, valuable information about node functionality can be obtained by concentric (or hierarchical) measurements. This paper extends previous methodologies based on concentric measurements, by studying the possibility of using agglomerative clustering methods, in order to obtain a set of functional groups of nodes, considering particular institutional collaboration network nodes, including various known communities (departments of the University of São Paulo). Among the interesting obtained findings, we emphasize the scale-free nature of the network obtained, as well as identification of different patterns of authorship emerging from different areas (e.g. human and exact sciences). Another interesting result concerns the relatively uniform distribution of hubs along concentric levels, contrariwise to the non-uniform pattern found in theoretical scale-free networks such as the BA model.     

Regulatory networks and connected components of the neutral space

The functioning of a living cell is largely determined by the structure of its regulatory network, comprising non-linear interactions between regulatory genes. An important factor for the stability and evolvability of such regulatory systems is neutrality – typically a large number of alternative network structures give rise to the necessary dynamics. Here we study the discretized regulatory dynamics of the yeast cell cycle [Li et al., PNAS, 2004] and the set of networks capable of reproducing it, which we call functional. Among these, the empirical yeast wildtype network is close to optimal with respect to sparse wiring. Under point mutations, which establish or delete single interactions, the neutral space of functional networks is fragmented into ≈ 4.7 × 10⁸ components. One of the smaller ones contains the wildtype network. On average, functional networks reachable from the wildtype by mutations are sparser, have higher noise resilience and fewer fixed point attractors as compared with networks outside of this wildtype component.     

Preservation of network degree distributions from non-uniform failures

There has been a considerable amount of interest in recent years on the robustness of networks to failures. Many previous studies have concentrated on the effects of node and edge removals on the connectivity structure of a static network; the networks are considered to be static in the sense that no compensatory measures are allowed for recovery of the original structure. Real world networks such as the world wide web, however, are not static and experience a considerable amount of turnover, where nodes and edges are both added and deleted. Considering degree-based node removals, we examine the possibility of preserving networks from these types of disruptions. We recover the original degree distribution by allowing the network to react to the attack by introducing new nodes and attaching their edges via specially tailored schemes. We focus particularly on the case of non-uniform failures, a subject that has received little attention in the context of evolving networks. Using a combination of analytical techniques and numerical simulations, we demonstrate how to preserve the exact degree distribution of the studied networks from various forms of attack.     

Motifs in co-authorship networks and their relation to the impact of scientific publications

Co-authorship networks, where the nodes are authors and a link indicates joint publications, are very helpful representations for studying the processes that shape the scientific community. At the same time, they are social networks with a large amount of data available and can thus serve as vehicles for analyzing social phenomena in general. Previous work on co-authorship networks concentrates on statistical properties on the scale of individual authors and individual publications within the network (e.g., citation distribution, degree distribution), on properties of the network as a whole (e.g., modularity, connectedness), or on the topological function of single authors (e.g., distance, betweenness). Here we show that the success of individual authors or publications depends unexpectedly strongly on an intermediate scale in co-authorship networks. For two large-scale data sets, CiteSeerX and DBLP, we analyze the correlation of (three- and four-node) network motifs with citation frequencies. We find that the average citation frequency of a group of authors depends on the motifs these authors form. In particular, a box motif (four authors forming a closed chain) has the highest average citation frequency per link. This result is robust across the two databases, across different ways of mapping the citation frequencies of publications onto the (uni-partite) co-authorship graph, and over time. We also relate this topological observation to the underlying social and socio-scientific processes that have been shaping the networks. We argue that the box motif may be an interesting category in a broad range of social and technical networks.     

Enhancing network lifespan in wireless sensor networks using deep learning based Graph Neural Network

Inadequate energy of sensors is one of the most significant challenges in the development of a reliable wireless sensor network (WSN) that can withstand the demands of growing WSN applications. Implementing a sleep-wake scheduling scheme while assigning data collection and sensing chores to a dominant group of awake sensors while all other nodes are in a sleep state seems to be a potential way for preserving the energy of these sensor nodes. When the starting energy of the nodes changes from one node to another, this issue becomes more difficult to solve. The notion of a dominant set-in graph has been used in a variety of situations. The search for the smallest dominant set in a big graph might be time-consuming. Specifically, we address two issues: first, identifying the smallest possible dominant set, and second, extending the network lifespan by saving the energy of the sensors. To overcome the first problem, we design and develop a deep learning-based Graph Neural Network (DL-GNN). The GNN training method and back-propagation approach were used to train a GNN consisting of three networks such as transition network, bias network, and output network, to determine the minimal dominant set in the created graph. As a second step, we proposed a hybrid fixed-variant search (HFVS) method that considers minimal dominant sets as input and improves overall network lifespan by swapping nodes of minimal dominating sets. We prepared simulated networks with various network configurations and modeled different WSNs as undirected graphs. To get better convergence, the different values of state vector dimensions of the input vectors are investigated. When the state vector dimension is 3 or 4, minimum dominant set is recognized with high accuracy. The paper also presents comparative analyses between the proposed HFVS algorithm and other existing algorithms for extending network lifespan and discusses the trade-offs that exist between them. Lifespan of wireless sensor network, which is based on the dominant set method, is greatly increased by the techniques we have proposed.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

基于联合矩阵分解的节点多属性网络社团检测

发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义. 针对社交媒体网络的社团检测通常需要利用两种信息源: 网络拓扑结构特征和节点属性特征, 丰富的节点内容属性信息为社团检测的增加了灵活性和挑战. 传统方法是要么仅针对这两者信息之一进行单独挖掘, 或者将两者信息得到的社团结果进行线性叠加判决, 不能有效进行信息源的融合. 本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究, 将两者信息源进行融合分析, 提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF, 提高了社团检测的有效性和鲁棒性. 实验表明, 本文所提的方法能够有效利用节点的属性信息指导社团检测, 具备更高的社团划分质量.     

基于节点拓扑特征的中国基金公司共持网络持股行为波动相关性

选取2003—2012年期间半年度中国基金公司持上市公司股票份额面板数据为样本数据,以基金公司为节点,以同一时刻共持同一家上市公司股票关系为边,以同一时刻共持的上市公司数量为权重,构建中国基金公司共持关系结构等价加权网络(简称共持网络).结合统计物理学等方法,分析了共持网络的拓扑结构稳定性及具有不同拓扑特征值的节点随时间演变过程中与共持网络中三类节点集合持股行为波动相关性.三类节点集合分别为t-1时刻基于某一股票形成的共持关系完全连通子图节点集合(第一类节点集合)、t-1时刻共持网络中非完全连通子图的节点集合(第二类节点集合)、t时刻新进入共持网络的节点集合(第三类节点集合).分析结果显示:1)节点与第二类节点集合持股行为波动呈正相关,且相关系数随着节点集聚系数的增强而增大;2)只有当节点的度和点强度值较高时,节点与第一类和第二类节点集合的持股行为呈正相关;3)不同拓扑特征条件下的节点与第三类节点集合的持股行为均不存在波动相关性.本文提供了一个研究持股行为相关性的新思路,并为进一步研究股票市场结构等价网络及节点重要性差异提供了基础.     

S-curve networks and an approximate method for estimating degree distributions of complex networks

In the study of complex networks almost all theoretical models have the property of infinite growth,but the size of actual networks is finite.According to statistics from the China Internet IPv4(Internet Protocol version 4) addresses,this paper proposes a forecasting model by using S curve(logistic curve).The growing trend of IPv4 addresses in China is forecasted.There are some reference values for optimizing the distribution of IPv4 address resource and the development of IPv6.Based on the laws of IPv4 growth,that is,the bulk growth and the finitely growing limit,it proposes a finite network model with a bulk growth.The model is said to be an S-curve network.Analysis demonstrates that the analytic method based on uniform distributions(i.e.,Barab’asi-Albert method) is not suitable for the network.It develops an approximate method to predict the growth dynamics of the individual nodes,and uses this to calculate analytically the degree distribution and the scaling exponents.The analytical result agrees with the simulation well,obeying an approximately power-law form.This method can overcome a shortcoming of Baraba’si-Albert method commonly used in current network research.     

Evolution of the Internet AS-level topology:From nodes and edges to components

Studying the topology of infrastructure communication networks(e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology might elucidate disciplines governing the dynamic process of complex systems. It may also contribute to a more intelligent communication network framework based on its autonomous behavior. In this paper, the Internet Autonomous Systems(ASes) topology from 1998 to 2013 was studied by deconstructing and analysing topological entities on three different scales(i.e., nodes,edges and 3 network components: single-edge component M1, binary component M2 and triangle component M3). The results indicate that: a) 95% of the Internet edges are internal edges(as opposed to external and boundary edges); b) the Internet network consists mainly of internal components, particularly M2 internal components; c) in most cases, a node initially connects with multiple nodes to form an M2 component to take part in the network; d) the Internet network evolves to lower entropy. Furthermore, we find that, as a complex system, the evolution of the Internet exhibits a behavioral series,which is similar to the biological phenomena concerned with the study on metabolism and replication. To the best of our knowledge, this is the first study of the evolution of the Internet network through analysis of dynamic features of its nodes,edges and components, and therefore our study represents an innovative approach to the subject.     

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.     

On the degree distribution of projected networks mapped from bipartite networks

Many real-world systems can be represented by bipartite networks. In a bipartite network, the nodes are divided into two disjoint sets, and the edges connect nodes that belong to different sets. Given a bipartite network (i.e. two-mode network) it is possible to construct two projected networks (i.e. one-mode networks) where each one is composed of only one set of nodes. While network analyses have focused on unipartite networks, considerably less attention has been paid to the analytical study of bipartite networks. Here, we analytically derive simple mathematical relationships that predict degree distributions of the projected networks by only knowing the structure of the original bipartite network. These analytical results are confirmed by computational simulations using artificial and real-world bipartite networks from a variety of biological and social systems. These findings offer in our view new insights into the structure of real-world bipartite networks.