Levels of a scale‐free tree

Consider the random graph model of Barabási and Albert, where we add a new vertex in every step and connect it to some old vertices with probabilities proportional to their degrees. If we connect it to only one of the old vertices the graph will be a tree. These graphs have been shown to have power law degree distributions, the same as observed in some large real‐world networks. We show that the degree distribution is the same on every sufficiently high level of the tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On centripetal flows of entities in scale‐free networks with nodes of finite capability

We examine the transmission of entities from the peripheries of scale‐free networks toward their centers when the nodes of the network have finite processing capabilities. We look at varying network utilization, U and find that clogging of the network sets in after a threshold value has been exceeded, and that the congestion sets in at the downstream nodes (those nearer to the collector) having large numbers of upstream neighbors. Investigation of the question of the degree of correlation of several characteristics of scale‐free networks (such as the average path length to the collector <l_(min)> and the average clustering coefficient ) with the dynamics of centripetal flow in them reveals a negative answer: any correlation is indirect and will manifest in the number of producer nodes (which dictate the effective heaviness of the flow) and the interconnectedness of the feeder nodes, those nodes which are immediate neighbors of the collector node. An examination of reinforcement strategies shows dramatic improvements in both the finishing rate, and the average total transmission time, when the more centrally‐placed nodes are reinforced first, showing that the entities spend a large amount of their lifetime waiting in line at those nodes (which constitute the bottlenecks in the network) compared to the nodes in the periphery. Our results reinforce the importance of a network's hubs and their immediate environs, and suggest strategies for prioritizing elements of a network for optimization. © 2014 Wiley Periodicals, Inc. Complexity 21: 283–295, 2015     

Teaching complexity theory through student construction of a course wiki: The self‐organization of a scale‐free network

Complex systems are fascinating because emergent phenomena are often unpredictable and appear to arise ex nihilo. The other side of this fascination, however, is a certain difficulty in comprehending complex systems, particularly for students. To help students more fully understand emergence and self‐organization, a course on complexity theory was designed to not only be about these two concepts, but itself embody them. The principal design tool was a course wiki. Here, we quantitatively demonstrate that this course wiki self‐organized into a scale‐free network. This is particularly notable given the small size of the network. We conclude by noting a few qualitative examples of emergence, as well as offering recommendations for the future use of wikis in teaching complexity theory. © 2010 Wiley Periodicals, Inc. Complexity 16: 41–48, 2011     

The degree sequences and spectra of scale‐free random graphs

We investigate the degree sequences of scale‐free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non‐rigorous arguments of Dorogovtsev, Mendes, and Samukhin ( 14 ). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A scale‐free network model for HIV transmission among men who have sex with men in China

Objective: The study aimed to analyze sexual networks and sex role preference as factors of HIV transmission among men who have sex with men (MSM) in China. Methods: We have developed a new scale‐free network model with a sex role preference framework to study HIV transmission among MSM. We have studied the influence of different sexual networks and the effect of different proportion of sex role preference upon HIV transmission. The results are that the average ones drawn from the scenarios have been simulated for more than 30 times. Results: Compared with the traditional mathematical model, the sexual networks provide a different prediction of the HIV transmission in the next 30 years. Without any intervention, the proportion of HIV carriers will descend after some time. Conclusions: There is significant associations among network characteristics, sex role preference, and HIV infection. Although network‐based intervention is efficient in reducing HIV transmission among MSM, there are only few studies of the characteristics of sexual network, and such gaps deserve more attention and exploration. Copyright © 2016 John Wiley & Sons, Ltd.     

On the critical exponents of random k‐SAT

There has been much recent interest in the satisfiability of random Boolean formulas. A random k‐SAT formula is the conjunction of m random clauses, each of which is the disjunction of k literals (a variable or its negation). It is known that when the number of variables n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2‐SAT this happens when m/n → 1, for 3‐SAT the critical ratio is thought to be m/n ≈ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called ν = ν_k (the smaller the value of ν the sharper the transition). Experiments have suggested that ν₃ = 1.5 ± 0.1. ν₄ = 1.25 ± 0.05, ν₅ = 1.1 ± 0.05, ν₆ = 1.05 ± 0.05, and heuristics have suggested that ν_k → 1 as k → ∞. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well defined). This result holds for each of the three standard ensembles of random k‐SAT formulas: m clauses selected uniformly at random without replacement, m clauses selected uniformly at random with replacement, and each clause selected with probability p independent of the other clauses. We also obtain similar results for q‐colorability and the appearance of a q‐core in a random graph. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 182–195, 2002     

Exhaustive generation of k‐critical ‐free graphs

We describe an algorithm for generating all k‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ‐free graphs, for both and . We also show that there are only finitely many 4‐critical ‐free graphs. For each of these cases we also give the complete lists of critical graphs and vertex‐critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3‐colorability problem in the respective classes. In addition, we prove a number of characterizations for 4‐critical H‐free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4‐critical planar ‐free graphs is finite. We also determine all 52 4‐critical planar P₇‐free graphs. We also prove that every P₁₁‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P₁₂‐free graph of girth at least five. Moreover, we show that every P₁₄‐free graph of girth at least six and every P₁₇‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.     

Markovian receiver collision analysis of high‐speed multi‐channel networks

Two synchronous transmission multi‐channel multi‐access protocols for high‐speed network architecture are studied in this paper. Analytic discrete time Markovian models are developed for finite number of stations and finite number of channels for the symmetric and asymmetric access rights proposed protocols. The effect of receiver collision phenomenon is examined and analysed on the performance measures evaluation and estimated by the probability of packet rejection at destination. Also, numerical results are presented for comparison for various numbers of data channels and stations. Copyright © 2005 John Wiley & Sons, Ltd.     

Multistability of memristive neural networks with time‐varying delays

The recent discovery of memristive neurodynamic systems holds great promise for realizing large‐scale nanoionic circuits. Development of pattern memory analysis for memristive neurodynamic systems poses several challenges. In this article, it shows that an n‐dimensional memristive neural networks with time‐varying delays can have 2ⁿ locally exponentially stable equilibria in the saturation region. In addition, local exponential stability of delayed memristive neural networks in any designated region is also characterized, which allows the locally exponentially stable equilibria to locate in the designated region. All of these criteria are very easy to be verified. Finally, the effectiveness of the results are illustrated by two numerical examples. © 2014 Wiley Periodicals, Inc. Complexity 21: 177–186, 2015     

Dissipativity and synchronization control of fractional‐order memristive neural networks with reaction‐diffusion terms

This paper deals with the dissipativity and synchronization control of fractional‐order memristive neural networks (FOMNNs) with reaction‐diffusion terms. By means of fractional Halanay inequality, Wirtinger inequality, and Lyapunov functional, some sufficient conditions are provided to ensure global dissipativity and exponential synchronization of FOMNNs with reaction‐diffusion terms, respectively. The underlying model and the obtained results are more general since the reaction‐diffusion terms are first introduced into FOMNNs. The given conditions are easy to be checked, and the correctness of the obtained results is confirmed by a living example.     

Robust exponential stability of discrete‐time uncertain impulsive neural networks with time‐varying delay

The purpose of this paper is to investigate the robust exponential stability of discrete‐time uncertain impulsive neural networks with time‐varying delay. By using Lyapunov functions together with Razumikhin technique, some new robust exponential stability criteria are presented. The obtained results show that the robust stability can be retained under certain impulsive perturbations for the neural network, which has the robust stability property. The obtained results also show that impulses can robustly stabilize the neural network, which does not have the robust stability property. Some examples, together with their simulations, are also given to show the effectiveness and the advantage of the presented results. It should be noted that the impulsive robust exponential stabilization result for discrete‐time neural network with time‐varying delay is given for the first time. Copyright © 2012 John Wiley & Sons, Ltd.     

Synchronization of fractional‐order delayed neural networks with hybrid coupling

This article presents new theoretical results on the synchronization for a class of fractional‐order delayed neural networks with hybrid coupling that contains constant coupling and discrete‐delay coupling. This is the first attempt to investigate the synchronization problem of fractional‐order coupled delayed neural networks. Based on the fractional‐order Lyapunov stability theorem and Kronecker product properties, sufficient criteria are established to ensure the fractional‐order coupled neural network to achieve synchronization. Numerical simulations are given to illustrate the correctness of the theoretical results. © 2015 Wiley Periodicals, Inc. Complexity 21: 106–112, 2016     

Global lagrange stability of complex‐valued neural networks of neutral type with time‐varying delays

In this article, the problem of global exponential stability in Lagrange sense of neutral type complex‐valued neural networks (CVNNs) with delays is investigated. Two different classes of activation functions are considered, one can be separated into real part and imaginary part, and the other cannot be separated. Based on Lyapunov theory and analytic techniques, delay‐dependent criteria are provided to ascertain the aforementioned CVNNs to be globally exponentially stable GES in Lagrange sense. Moreover, the proposed sufficient conditions are presented in the form of linear matrix inequalities which could be easily checked by Matlab. Finally, two simulation examples are given out to demonstrate the validity of theory results. © 2016 Wiley Periodicals, Inc. Complexity 21: 438–450, 2016     

Finite‐time stabilization of complex dynamical networks via optimal control

An optimal control scheme is proposed to stabilize complex networks in finite time. Furthermore, since it is costly and impractical to control a network by applying controllers to all the nodes, an algorithm inspired by Kalmans controllability rank condition is presented for local stabilization by locating pinned components. Numerical examples are provided to illustrate the effectiveness of the proposed method as well as its superiority over a traditional pinning control technique. This work offers a theoretical framework for designing optimal controllers to stabilize networks in finite time with reduced control cost. © 2016 Wiley Periodicals, Inc. Complexity 21: 417–425, 2016     

Finite‐Time lag synchronization of delayed neural networks via periodically intermittent control

The problem of finite‐time lag synchronization of delayed neural networks via periodically intermittent control is studied. In two sections, based on the same finite‐time stability theory and using the same sliding mode control, by designing a periodically intermittent feedback controller and adjusting periodically intermittent control strengths with the updated laws, we achieve the finite‐time lag synchronization between two time delayed networks. In addition, we ensure that the trajectory of the error system converges to a chosen sliding surface within finite time and keeps it on forever. Finally, two examples are presented to verify the effectiveness of the analytical results obtained here. © 2015 Wiley Periodicals, Inc. Complexity 21: 211–219, 2016     

Robust adaptive synchronization of uncertain complex networks with multiple time‐varying coupled delays

In this article, the synchronization problem of uncertain complex networks with multiple coupled time‐varying delays is studied. The synchronization criterion is deduced for complex dynamical networks with multiple different time‐varying coupling delays and uncertainties, based on Lyapunov stability theory and robust adaptive principle. By designing suitable robust adaptive synchronization controllers that have strong robustness against the uncertainties in coupling matrices, the all nodes states of complex networks globally asymptotically synchronize to a desired synchronization state. The numerical simulations are given to show the feasibility and effectiveness of theoretical results. © 2014 Wiley Periodicals, Inc. Complexity 20: 62–73, 2015     

T‐optimality and neural networks: a comparison of approaches for building experimental designs

This paper deals with optimal experimental design criteria and neural networks in the aim of building experimental designs from observational data. It addresses the following three main issues: (i) the introduction of two radically different approaches, namely T‐optimal designs extended to Generalized Linear Models and Evolutionary Neural Networks Design; (ii) the proposal of two algorithms, based on model selection procedures, to exploit the information of already collected data; and (iii) the comparison of the suggested methods and corresponding algorithms by means of a simulated case study in the technological field. Results are compared by considering elements of the proposed algorithms, in terms of models and experimental design strategies. In particular, we highlight the algorithmic features, the performances of the approaches, the optimal solutions and the optimal levels of variables involved in a simulated foaming process. The optimal solutions obtained by the two proposed algorithms are very similar, nevertheless, the differences between the paths followed by the two algorithms to reach optimal values are substantial, as detailed step‐by‐step in the discussion. Copyright © 2012 John Wiley & Sons, Ltd.     

Guaranteed cost synchronization of complex networks with uncertainties and time‐Varying delays

This article focuses on the problem of Guaranteed cost synchronization of complex networks with uncertainties and time‐Varying delays. Sufficient conditions for the existence of the optimal guaranteed cost control laws are introduced in the light of linear matrix inequalities via the Lyapunov–Krasovskii stability theory. The time‐varying node delays and time‐varying coupling delays are simultaneously regarded in the complex network. The node uncertainties and coupling uncertainties are simultaneously considered as well. Numerical simulations are provided to account for the effectiveness and robustness of the proposed method. The results in this article generalize and improve the corresponding results of the recent works. © 2015 Wiley Periodicals, Inc. Complexity 21: 381–395, 2016     

The impact of network structure on innovation efficiency: An agent‐based study in the context of innovation networks

This article investigates the impact of network structure on innovation efficiency by establishing a simulation model of innovation process in the context of innovation networks. The results indicate that short path lengths between vertices are conductive to high efficiency of explorative innovations, dense clusters are conductive to high efficiency of exploitative innovations, and high small‐worldness is conductive to high efficiency of the hybrid of these two innovations. Moreover, we discussed the reason of the results and give some suggestions to innovators and innovation policy makers. © 2014 Wiley Periodicals, Inc. Complexity 21: 111–122, 2015