Controllability of Boolean control networks avoiding states set

In this paper, using semi-tensor product and the vector form of Boolean logical variables, the Boolean control network （BCN） is expressed as a bilinear discrete time system about state and control variables. Based on the algebraic form, the reachability and controllability avoiding undesirable states set are discussed. The reachability and controllability discussed here are under certain constraint and tile definitions of reachability and controllability avoiding undesirable states set have practical meaning. Also, the necessary and sufficient conditions for reachability and controllability are given. At last, the control sequence that steers one state to another is constructed.     

Controllability of multiagent systems based on path and cycle graphs

This paper studies the controllability of multiagent systems based on path and cycle graphs. For paths or cycles, sufficient and necessary conditions are presented for determining the locations of leaders under which the controllability can be realized. Specifically, the controllability of a path is shown to be determined by a set generated only from its odd factors, and the controllability of a cycle is determined by whether the distance between 2 leaders belongs to a set generated from its even (odd) factors when the number of its nodes is even (odd). For both graphs, the dimension of the controllable subspace is also derived. Moreover, the technique used in the derivation of the above results is further used to get sufficient and necessary conditions for several different types of graphs generated from path and cycle topologies. These types of graphs can be regarded as typical topologies in the study of multiagent controllability, and accordingly the obtained results have meaningful enlightenment for the research in this field.     

面向级联失效的复杂网络加权策略

针对加权复杂网络抵制级联失效的鲁棒性问题,提出一种介数相关的节点加权方法,并应用加权流局域重新分配原则构建了带有可调权重参数的级联模型。在典型模型网络和真实网络上探讨了级联行为。数值模拟和理论分析结果给出了网络达到最强鲁棒性水平时所对应的权重参数值。与现有的度相关加权策略对比,介数相关加权策略使得网络鲁棒性更强。     

基于拷贝模型的复杂网络鲁棒性研究*

拷贝机制被广泛认为是系统通过构造冗余提高自身鲁棒性的主要机制之一。为了探究拷贝机制是否是真实网络鲁棒的基本机制,通过计算机仿真的方法对基于拷贝机制的网络模型的鲁棒性进行了进一步的研究。仿真结果表明,随着拷贝机制的增强,相应网络对于随机故障的鲁棒性增强,而对于蓄意攻击的鲁棒性减弱。这一事实启发人们,基于拷贝机制的网络,其鲁棒性仅局限于随机失效,单纯的拷贝机制还不足以有效抵抗基于网络全局结构信息的蓄意攻击。     

Evolution and stability of Linux kernels based on complex networks

This paper presents a novel method to study Linux kernel evolution using complex networks.Having investigated the node degree distribution and average path length of the call graphs corresponding to the kernel modules of 223 different versions(V1.1.0 to V2.4.35),we found that the call graphs are scale-free and smallworld networks.Based on the relationship between average path length and nodes,we propose a method to find unusual points during Linux kernel evolution using the slope of the average path length.Using the unusual points we identify major structural changes in kernel modules.A stability coefficient is also proposed to describe quantitatively the stability of kernel modules during evolution.Finally,we verify our result through Vasa’s metrics method.     

复杂网络能控性鲁棒性研究进展

研究复杂网络能控性鲁棒性对包括社会网络、生物和技术网络等在内的复杂系统的控制和应用具有重要价值. 复杂网络的能控性是指: 可通过若干控制节点和适当的输入, 在有限时间内将系统状态驱动至任意目标状态. 能控性鲁棒性则是指在受到攻击的情况下, 复杂网络依然维持能控性的能力. 设计具有优异能控性鲁棒性的复杂网络模型和优化实际网络的能控性鲁棒性一直是复杂网络领域的重要研究内容. 本文首先比较了常用的能控性鲁棒性定义及度量, 接着从攻击策略的角度分析了3类攻击的特点及效果, 包括随机攻击、基于特征的蓄意攻击和启发式攻击. 然后比较了常见模型网络的能控性鲁棒性. 介绍了常用优化策略, 包括模型设计和重新连边等. 目前的研究在攻击策略和拓扑结构优化方面都取得了进展, 也为进一步理论分析提供条件. 最后总结全文并提出潜在研究方向.     

基于复杂网络的操作系统内核演化与稳定性研究

出了基于复杂网络研究操作系统内核模块演化的方法.通过研究223个Linux版本(从1.1.0到2.4.35)内核模块函数调用图的度分布和平均路径长度,发现函数调用图具有无标度和小世界特征.根据复杂网络中平均路径长度与网络节点的关系,提出了通过平均路径长度斜率发现演化过程中的异常点,从而发现内核模块结构重大变化的方法.提...     

Event-triggered sampled-data synchronization of complex networks with uncertain inner coupling and time-varying delays

This paper focuses on event-triggered sampled-data synchronization of uncertain complex networks with time-varying coupled delays. First of all, a discrete event-triggered sampled-data control scheme is adopted, which not only makes the state of the system be monitored in discrete time, but also the sampling information is effectively transmitted. The proposed event-triggered mechanism effectively prevents Zeno behavior. In addition, we also use some novel piecewise time-dependent Lyapunov–Krasovskii and Wirtinger inequality to handle the time-varying delays and parameter uncertainties of complex networks. Then, synchronization criteria are given for uncertain complex networks. Finally, the simulation results show that the control scheme can significantly reduce the number of transmitted signals while maintaining the uncertain complex networks synchronization.     

基于负载流的点加权复杂网络节点重要性评估方法研究

基于目前节点重要度评估方法大多针对静态无权网络拓扑结构的研究现状,考虑实际加权网络节点之间负载流动情况,从事理层面提出了一种基于网络贡献度的节点重要性评估方法。该方法基于典型加权复杂网络拓扑结构,从节点间负载流动和网络系统运行的角度出发,定义了流出负载量、流入负载量和流经负载量三个特征参数,并给出了具有一定现实意义的评价方法。该方法有助于更准确地发现复杂网络中的关键节点。最后的实验分析验证了该方法的有效性和可行性。     

Controllability and stabilization of Boolean control networks by the auxiliary function of flipping

In this article, a hybrid method combining flip matrix approach and an open (or closed) loop control is proposed to study global controllability and stabilization of Boolean control networks (BCNs). First, the necessary and sufficient condition for global controllability of BCNs, by flipping some members of a perturbation set and under free control sequences, is proposed. After that, using a search algorithm, the minimal perturbation sets for global controllability (MS‐GCs) of the BCN are obtained. Next, we propose a necessary and sufficient criterion for global stabilization of BCNs by flipping some members of a perturbation set and under a state feedback control. Similarly, an algorithm is given to search for the minimal perturbation sets for global stabilization (MS‐GSs) of the BCN. Moreover, the time‐optimal MS‐GSs of the BCN are also obtained by an algorithm. Some examples are given to illustrate the effectiveness of the results.     

Complex agent networks: An emerging approach for modeling complex systems

Complexity and complex systems are all around us: from molecular and cellular systems in biology up to economics and human societies. There is an urgent need for methods that can capture the multi-scale spatio-temporal characteristics of complex systems. Recent emphasis has centered on two methods in particular, those being complex networks and agent-based models. In this paper we look at the combination of these two methods and identify “Complex Agent Networks”, as a new emerging computational paradigm for complex system modeling. We argue that complex agent networks are able to capture both individual-level dynamics as well as global-level properties of a complex system, and as such may help to obtain a better understanding of the fundamentals of such systems.     

软件执行过程的加权复杂网络

软件规模庞大,结构复杂,使软件测试和软件可信性评价成为一个亟待解决的理论问题,可信软件研究也因此成为目前软件工程研究的热点。实验证明大型软件的静态函数调用网络和动态执行所得到的函数调用加权（函数调用次数）网络都具有小世界效应和无标度特性,这就为采用基于关键模块和关键路径的软件测试方法提供了理论依据,从而提高测试效率,降低测试费用。提出基于关键路径的测试方法,利用较少的测试用例覆盖较多的软件执行过程。     

Controllability and observability of state‐dependent switched Boolean control networks with input constraints

This paper investigates the controllability and observability of state‐dependent switched Boolean control networks (SDSBCNs) with input constraints. First, the algebraic form of SDSBCNs is derived via the semi‐tensor product of matrices. Then constrained model‐input‐state (CMIS) matrices are introduced for SDSBCNs with input constraints. On the basis of CMIS matrices, two necessary and sufficient conditions are provided for the controllability and observability. Finally, two examples are given to show the effectiveness of the main results.     

Scalable percolation search on complex networks

We introduce a scalable searching protocol for locating and retrieving content in random networks with heavy-tailed and in particular power-law (PL) degree distributions. The proposed algorithm is capable of finding any content in the network with probability one   in time O(logN)$\mathrm{O}(\log N)$, with a total traffic that provably scales sub-linearly with the network size, N. Unlike other proposed solutions, there is no need to assume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. The scaling behavior of the size of the giant connected component of a random graph with heavy-tailed degree distributions under bond percolation is at the heart of our results. The percolation search algorithm can be directly applied to make unstructured peer-to-peer (P2P) networks, such as Gnutella, Limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and approximate scale-free network structures), scalable. For example, simulations of the protocol on the limewire crawl number 5 network [Ripeanu et al., Mapping the Gnutella network: properties of large-scale peer-to-peer systems and implications for system design, IEEE Internet Comput. J. 6 (1) (2002)], consisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%.     

非线性耦合的复杂网络自适应同步

提出了一种通过非线性耦合的复杂网络自适应同步方案,方案具有自适应律简单和应用范围广等特点。证明了动力系统满足给定条件下,该同步方案同步,且同步解是局部和全局渐进稳定的。两个计算机仿真实例分别展示了在无标度网络和最近邻耦合网络上的同步误差变化趋势,验证了同步方案的有效性。     

半监督模式下复杂网络分类的方法

提出了一种基于半监督模式的复杂网络社团划分新方法,通过引入物理学中的万有引力定理进而计算出有标签节点与周围无标签节点的相互作用值,最终将网络中的社团划分出来。实验表明,算法可以比较准确地划分出一些网络中的社团结构。     

复杂动态网络演化社团结构探测分析的研究进展

针对复杂动态网络中演化社团结构的探测,综述了该新领域的研究进展。首先对演化社团结构探测进行了问题描述,总结了四种研究思路。重点介绍了其中一些有代表性的分析方法及其特点,以及衡量探测方法好坏的基准图。最后指出该领域值得进一步探索的研究方向。     

复杂网络中选举免疫策略研究

受现代社会选举制度启发,提出了一种新的节点免疫策略,提出的选举免疫策略按节点得票数量多少选择节点并免疫。基于消息传递方法,给出了大规模配置模型网络上SIR传染病模型的选举免疫策略的数学解析,并比较了选举免疫、随机免疫、目标免疫和熟人免疫策略的效果。数学解析结果和仿真结果表明,选举免疫能够有效控制疾病在无标度网络上的传播。