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.     

Physical generation of random numbers using an asymmetrical Boolean network

Autonomous Boolean networks (ABNs) have been successfully applied to the generation of random number due to their complex nonlinear dynamics and convenient on-chip integration. Most of the ABNs used for random number generators show a symmetric topology, despite their oscillations dependent on the inconsistency of time delays along links. To address this issue, we suggest an asymmetrical autonomous Boolean network (aABN) and show numerically that it provides large amplitude oscillations by using equal time delays along links and the same logical gates. Experimental results show that the chaotic features of aABN are comparable to those of symmetric ABNs despite their being made of fewer nodes. Finally, we put forward a random number generator based on aABN and show that it generates the random numbers passing the NIST test suite at 100 Mbits/s. The unpredictability of the random numbers is analyzed by restarting the random number generator repeatedly. The aABN may replace symmetrical ABNs in many applications using fewer nodes and, in turn, reducing power consumption.     

Evolving networks with bimodal degree distribution

Networks with bimodal degree distribution are most robust to targeted and random attacks. We present a model for constructing a network with bimodal degree distribution. The procedure adopted is to add nodes to the network with a probability p and delete the links between nodes with probability (1 − p). We introduce an additional constraint in the process through an immunity score, which controls the dynamics of the growth process based on the feedback value of the last few time steps. This results in bimodal nature for the degree distribution. We study the standard quantities which characterize the networks, like average path length and clustering coefficient in the context of our growth process and show that the resultant network is in the small world family. It is interesting to note that bimodality in degree distribution is an emergent phenomenon.     

An empirical study of Chinese language networks

Chinese is spoken by the largest number of people in the world, and it is regarded as one of the most important languages. In this paper, we explore the statistical properties of Chinese language networks (CLNs) within the framework of complex network theory. Based on one of the largest Chinese corpora, i.e. People’s Daily Corpus, we construct two networks (CLN1 and CLN2) from two different respects, with Chinese words as nodes. In CLN1, a link between two nodes exists if they appear next to each other in at least one sentence; in CLN2, a link represents that two nodes appear simultaneously in a sentence. We show that both networks exhibit small-world effect, scale-free structure, hierarchical organization and disassortative mixing. These results indicate that in many topological aspects Chinese language shapes complex networks with organizing principles similar to other previously studied language systems, which shows that different languages may have some common characteristics in their evolution processes. We believe that our research may shed some new light into the Chinese language and find some potentially significant implications.     

Synchronization in complex networks with a modular structure

Networks with a community (or modular) structure arise in social and biological sciences. In such a network individuals tend to form local communities, each having dense internal connections. The linkage among the communities is, however, much more sparse. The dynamics on modular networks, for instance synchronization, may be of great social or biological interest. (Here by synchronization we mean some synchronous behavior among the nodes in the network, not, for example, partially synchronous behavior in the network or the synchronizability of the network with some external dynamics.) By using a recent theoretical framework, the master-stability approach originally introduced by Pecora and Carroll in the context of synchronization in coupled nonlinear oscillators, we address synchronization in complex modular networks. We use a prototype model and develop scaling relations for the network synchronizability with respect to variations of some key network structural parameters. Our results indicate that random, long-range links among distant modules is the key to synchronization. As an application we suggest a viable strategy to achieve synchronous behavior in social networks.     

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.     

Cluster synchronization in networks of distinct groups of maps

In this paper, we study cluster synchronization in general bi-directed networks of nonidentical clusters, where all nodes in the same cluster share an identical map. Based on the transverse stability analysis, we present sufficient conditions for local cluster synchronization of networks. The conditions are composed of two factors: the common inter-cluster coupling, which ensures the existence of an invariant cluster synchronization manifold, and communication between each pair of nodes in the same cluster, which is necessary for chaos synchronization. Consequently, we propose a quantity to measure the cluster synchronizability for a network with respect to the given clusters via a function of the eigenvalues of the Laplacian corresponding to the generalized eigenspace transverse to the cluster synchronization manifold. Then, we discuss the clustering synchronous dynamics and cluster synchronizability for four artificial network models: (i) p-nearest-neighborhood graph; (ii) random clustering graph; (iii) bipartite random graph; (iv) degree-preferred growing clustering network. From these network models, we are to reveal how the intra-cluster and inter-cluster links affect the cluster synchronizability. By numerical examples, we find that for the first model, the cluster synchronizability regularly enhances with the increase of p, yet for the other three models, when the ratio of intra-cluster links and the inter-cluster links reaches certain quantity, the clustering synchronizability reaches maximal.     

Transforming a complex network to an acyclic one

Acyclic networks are a class of complex networks in which links are directed and do not have closed loops. Here we present an algorithm for transforming an ordinary undirected complex network into an acyclic one. Further analysis of an acyclic network allows one to find the structural properties of the network. With our approach one can find the communities and key nodes in complex networks. Also we propose a new parameter of complex networks which can mark the most vulnerable nodes of the system. The proposed algorithm can be applied to finding communities and bottlenecks in general complex networks.     

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.     

Density-based shrinkage for revealing hierarchical and overlapping community structure in networks

The investigation of community structure in networks is an important issue in many disciplines, which still remains a challenging task. First, complex networks often show a hierarchical structure with communities embedded within other communities. Moreover, communities in the network may overlap and have noise, e.g., some nodes belonging to multiple communities and some nodes marginally connected with the communities, which are called hub and outlier, respectively. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also to identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm DenShrink. By combining the advantages of density-based clustering and modularity optimization methods, our algorithm can reveal the embedded hierarchical community structure efficiently in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the resolution limit possessed by other modularity-based methods. Our experiments on the real-world and synthetic datasets show that DenShrink generates more accurate results than the baseline methods.     

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

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

Sample-to-sample fluctuations in real-network ensembles

Network modeling based on ensemble averages tacitly assumes that the networks meant to be modeled are typical in the ensemble. Previous research on network eigenvalues, which govern a range of dynamical phenomena, has shown that this is indeed the case for uncorrelated networks with minimum degree ≥ 3. Here, we focus on real networks, which generally have both structural correlations and low-degree nodes. We show that: (i) the ensemble distribution of the dynamically most important eigenvalues can be not only broad and far apart from the real eigenvalue but also highly structured, often with a multimodal rather than a bell-shaped form; (ii) these interesting properties are found to be due to low-degree nodes, mainly those with degree ≤ 3, and network communities, which is a common form of structural correlation found in real networks. In addition to having implications for ensemble-based approaches, this shows that low-degree nodes may have a stronger influence on collective dynamics than previously anticipated from the study of computer-generated networks.     

A thermal flux-diffusing model for complex networks and its applications in community structure detection

We introduce a thermal flux-diffusing model for complex networks. Based on this model, we propose a physical method to detect the communities in the complex networks. The method allows us to obtain the temperature distribution of nodes in time that scales linearly with the network size. Then, the local community enclosing a given node can be easily detected for the reason that the dense connections in the local communities lead to the temperatures of nodes in the same community being close to each other. The community structure of a network can be recursively detected by randomly choosing the nodes outside the detected local communities. In the experiments, we apply our method to a set of benchmarking networks with known pre-determined community structures. The experiment results show that our method has higher accuracy and precision than most existing globe methods and is better than the other existing local methods in the selection of the initial node. Finally, several real-world networks are investigated.     

The structural role of weak and strong links in a financial market network

We investigate the properties of correlation based networks originating from economic complex systems, such as the network of stocks traded at the New York Stock Exchange (NYSE). The weaker links (low correlation) of the system are found to contribute to the overall connectivity of the network significantly more than the strong links (high correlation). We find that nodes connected through strong links form well defined communities. These communities are clustered together in more complex ways compared to the widely used classification according to the economic activity. We find that some companies, such as General Electric (GE), Coca Cola (KO), and others, can be involved in different communities. The communities are found to be quite stable over time. Similar results were obtained by investigating markets completely different in size and properties, such as the Athens Stock Exchange (ASE). The present method may be also useful for other networks generated through correlations.     

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

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

Maximum modular graphs

Modularity has been explored as an important quantitative metric for community and cluster detection in networks. Finding the maximum modularity of a given graph has been proven to be NP-complete and therefore, several heuristic algorithms have been proposed. We investigate the problem of finding the maximum modularity of classes of graphs that have the same number of links and/or nodes and determine analytical upper bounds. Moreover, from the set of all connected graphs with a fixed number of links and/or number of nodes, we construct graphs that can attain maximum modularity, named maximum modular graphs. The maximum modularity is shown to depend on the residue obtained when the number of links is divided by the number of communities. Two applications in transportation networks and data-centers design that can benefit of maximum modular partitioning are proposed.     

Error and attack tolerance of synchronization in Hindmarsh–Rose neural networks with community structure

Synchronization is one of the most important features observed in large-scale complex networks of interacting dynamical systems. As is well known, there is a close relation between the network topology and the network synchronizability. Using the coupled Hindmarsh–Rose neurons with community structure as a model network, in this paper we explore how failures of the nodes due to random errors or intentional attacks affect the synchronizability of community networks. The intentional attacks are realized by removing a fraction of the nodes with high values in some centrality measure such as the centralities of degree, eigenvector, betweenness and closeness. According to the master stability function method, we employ the algebraic connectivity of the considered community network as an indicator to examine the network synchronizability. Numerical evidences show that the node failure strategy based on the betweenness centrality has the most influence on the synchronizability of community networks. With this node failure strategy for a given network with a fixed number of communities, we find that the larger the degree of communities, the worse the network synchronizability; however, for a given network with a fixed degree of communities, we observe that the more the number of communities, the better the network synchronizability.     

Detecting community structure in complex networks based on a measure of information discrepancy

Properties of complex networks, such as small-world property, power-law degree distribution, network transitivity, and network- community structure which seem to be common to many real-world networks have attracted great interest among researchers. In this study, global information of the networks is considered by defining the profile of any node based on the shortest paths between it and all the other nodes in the network; then a useful iterative procedure for community detection based on a measure of information discrepancy and the popular modular function Q is presented. The new iterative method does not need any prior knowledge about the community structure and can detect an appropriate number of communities, which can be hub communities or non-hub communities. The computational results of the method on real networks confirm its capability.     

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.     

Feedback arcs and node hierarchy in directed networks

Directed networks such as gene regulation networks and neural networks are connected by arcs(directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which leads to complex information-processing dynamics in the network and makes it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks.