Detecting community structure: From parsimony to weighted parsimony

Community detection has attracted a great deal of attention in recent years. A parsimony criterion for detecting this structure means that as minimal as possible number of inserted and deleted edges is needed when we make the network considered become a disjoint union of cliques. However, many small groups of nodes are obtained by directly using this criterion to some networks especially for sparse ones. In this paper we propose a weighted parsimony model in which a weight coefficient is introduced to balance the inserted and deleted edges to ensure the obtained subgraphs to be reasonable communities. Some benchmark testing examples are used to validate the effectiveness of the proposed method. It is interesting that the weight here can be determined only by the topological features of the network. Meanwhile we make some comparison of our model with maximizing modularity Q and modularity density D on some of the benchmark networks, although sometimes too many or a little less numbers of communities are obtained with Q or D, a proper number of communities are detected with the weighted model. All the computational results confirm its capability for community detection for the small or middle size networks.     

基于最小连通支配集的复杂网络关键节点与连边识别方法

复杂网络关键节点与关键连边在网络中均起着十分重要的作用,目前的识别方法往往无法做到同时识别,并且识别指标角度较为单一。为解决上述问题,提出一种基于最小连通支配集(minimum connected dominatingset,MCDS)的复杂网络关键节点与连边识别方法,通过使用免疫粒子群(immune particle swarm optimization,IPSO)算法寻找网络最小连通支配集,构建核心骨干网,实现对复杂网络关键节点与连边的同时识别。该算法在求解过程中引入免疫机制指导粒子节点搜索方向、加快算法收敛速度,同时优化搜索节点质量。经实验验证表明,所提识别方法能够有效识别网络中的关键节点与关键连边。     

A New Evaluation Method of Node Importance in Directed Weighted Complex Networks

Current researches on node importance evaluation mainly focus on undirected and unweighted networks, which fail to reflect the real world in a comprehensive and objective way. Based on directed weighted complex network models, the paper introduces the concept of in-weight intensity of nodes and thereby presents a new method to identify key nodes by using an importance evaluation matrix. The method not only considers the direction and weight of edges, but also takes into account the position importance of nodes and the importance contributions of adjacent nodes. Finally, the paper applies the algorithm to a microblog-forwarding network composed of 34 users, then compares the evaluation results with traditional methods. The experiment shows that the method proposed can effectively evaluate the node importance in directed weighted networks.     

基于区域毁伤的基础设施网络抗毁性评估模型

基础设施网络对国家经济、人民生活和社会安全具有重要意义,为了能够准确迅速地评估基础设施网络面对物理攻击或自然灾害时的抗毁性,提出了基于区域毁伤的基础设施网络抗毁性评估模型。该模型将网络的边均分成虚拟节点,提出加权聚类算法寻找关键区域,使用归一化方法平衡网络规模和网络地理覆盖范围对评估结果的影响,算法复杂度低,运算量小,模型应用范围广,便于多个网络之间或同一网络不同规划方案的抗毁性比较。以智利电力输送网络为例,设计多组实验对评估模型进行检验,并给出可视化结果和分析。     

基于谱方法的复杂网络中社团结构的模块度

现实中的大量复杂网络表现出明显的社团结构, 模块度是衡量网络社团结构划分的重要指标函数, 但最常用的NG模块度存在分辨率限制问题, 不能识别出小于一定规模的社团. 文章在谱映射的基础上, 提出了复杂网络社团结构的两种模块度. 改进的表现模块度不仅能够应用于有权网络, 而且部分解决了NG模块度的局限性问题; 内聚模块度以社团内部的内聚度为衡量依据, 从根本上避免了NG模块度和表现模块度可能出现的不恰当划分情况. 最后通过计算机生成的测试网络和两个经典网络, 与NG模块度对比验证了表现模块度和内聚模块度的可行性和有效性.     

变聚类系数加权网络的建模及其级联抗毁性分析

针对ＢＢＶ 等传统加权网络模型生成的网络聚类系数较小、簇度幂律特征偏弱等不足,提出了一个变 聚类系数加权网络模型,其中新节点的加入根据节点强度和初始吸引度共同驱动的优先连接机制或三角连接机 制与网络中的旧节点建立连接。仿真表明,当初始吸引度和三角连接概率取不同值时,生成网络的度、强度和边 权都服从幂律分布,并且聚类系数可调,特别是随着三角连接概率的变大,簇度之间的幂律特征更加明显。最后 构建了基于加权网络的级联故障模型,分析了权重因素、聚类系数等对网络级联抗毁性的影响。     

多峰函数优化的免疫人工鱼群网络算法

针对人工鱼群算法(artificial fish swarm algorithm, AFSA)多峰寻优能力不足的问题,提出了一种免疫人工鱼群网络算法。应用改进的觅食行为,提升了算法的局部寻优能力;采用免疫网络调节机理,保持了人工鱼群多样性,不〖JP2〗断探寻新的局部峰值;执行模式搜索法（pattern search method, PSM）,完成精英人工鱼群的精细搜索。仿真实验结果表明,该算法具有较强全局优化能力和局部优化能力,且搜索到每个最优解都达到了理想值。     

二分网络社团结构的比较性定义

为了解决二分网络的聚类问题,借鉴单顶点网络社团结构的比较性定义,提出了直接基于原始二分网络社团结构的比较性定义,这个定义允许社团之间存在重叠,并定义了在二分网络中顶点与社团之间的作用力.在不引进额外参数的情况下,设计了基于此定义的二分网络的聚类算法,并将此算法应用于人工网和一些实际网络中,结果表明这个算法可以比较准确地对网络进行聚类,说明该定义是有效的.     

基于蚁群优化的贝叶斯网络学习

针对贝叶斯网络学习中的混合算法容易缩小搜索空间,同时易陷入局部最优等缺点,提出了基于蚁群优化的贝叶斯网络学习算法。首先应用最大最小父子节点集合算法(max min parents and children, MMPC)来构建无向网络的框架,然后利用蚁群优化算法进行评分〖CD*2〗搜索,通过平衡“开发”和“探索”力度来修补搜索空间并确定网络结构中边的方向。最后应用本算法学习逻辑报警还原机理网（a logical alarm reduction mechanism, ALARM),结果显示本算法减少了丢失边的数量,得到了更接近真实结构的贝叶斯网络。     

Algorithmof communication network reliability combining links,nodes and capacity

1 .INTRODUCTIONWhen communication networkis studied macroscopi-cally,exchange nodes ,links and transmission capaci-ty are the most i mportant parameters .If all these pa-rameters are consideredtogether ,the performancein-dex of communication network can be objectivelyshown.In Refs .[1 ,2] the reliabilityindex of a com-munication network whichintegrates the capacity andthe connection reliability of the links is defined.InRef .[1] ,the reliabilityindexis defined as the trans-mission probab…     

两种策略下的最短路径并行算法研究与实现

随着智能交通运输系统的研究与应用,对在大规模交通网络上求解最短路径的实时性提出了更高的要求。为了找出适用于实际交通网络的高效最短路径并行算法,首先选取了3种最短路径标号串行算法,以此为基础分别实现了网络复制及网络分割两种策略下求解最短路径的并行算法。最后,从基于G IS的交通规划软件T ransCAD中提取了实际交通路网数据,同时还随机产生了不同规模的稀疏格网,在这些网络中对并行算法的性能进行了测试和分析。结果表明,在8台机器上求解含5 181个节点的实际交通网络中32个源点的最短路径时,基于网络分割的双队列标号修正并行算法的加速比可达到6.32,在其他网络中也表现出较好的加速比及可扩展性。     

基于复合边权重的加权复杂网络级联抗毁性优化

针对加权网络级联抗毁性问题,融合对级联失效动力学过程有重要影响的节点度和介数两种指标,提出一种节点度和介数相关的边权重模型,该模型通过定义调整两种指标占边权比重的参数,以及调整网络异质度的权重参数,使得边对故障引起的额外负载的承载能力更强。理论分析与仿真结果表明,存在某一权重参数以及比重系数取值使得BA无标度网络和NW小世界网络鲁棒性达到最强;相比单一指标边权方法,提出的模型能够更加有效地提升网络级联抗毁性能。     

基于小世界模型动态演化邻域的微粒群算法

分析了影响网络中信息传播的主要因素,并结合小世界网络的形成机制,提出了一种具有动态邻域结构的微粒群算法.该算法初始化群体拓扑结构为"聚集系数大,平均最短路径长"的环形规则网络,以降低邻域间信息交流的速度,保持种群的多样性.在算法进化过程中,当邻域多样性小于给定阈值时,以小概率向网络随机增加长距离边,逐步形成"聚集系数大,平均最短路径小"的小世界网络,加快邻域间信息交流的速度.仿真结果表明,结合适当的惯性策略,该算法能获得更好的收敛性能和收敛速度.     

基于一种新型动态神经网络的非线性自适应逆控制

根据生物神经元的机能,提出了一种具有动态激励函数的新型神经元模型,由此构成的神经网络(DAFNN)应用在非线性自适应逆控制中时只需要确定隐层神经元个数,从而克服了用NARX回归神经网络时需确定输入和输出延时阶数及隐层神经元个数等多个参数的不足。通过对单输入单输出(SISO)及多输入多输出(MIMO)非线性系统的自适应逆控制仿真研究,证实了DAFNN是一种很好的非线性系统建模和控制工具。     

Hybrid hierarchical trajectory planning for a fixed-wing UCAV performing air-to-surface multi-target attack

This paper considers the problem of generating a flight trajectory for a single fixed-wing unmanned combat aerial vehicle (UCAV) performing an air-to-surface multi-target attack (A/SMTA) mission using satellite-guided bombs. First, this problem is formulated as a variant of the traveling salesman problem (TSP), called the dynamic-constrained TSP with neighborhoods (DCTSPN). Then, a hierarchical hybrid approach, which partitions the planning algorithm into a roadmap planning layer and an optimal control layer, is proposed to solve the DCTSPN. In the roadmap planning layer, a novel algorithm based on an updatable probabilistic roadmap (PRM) is presented, which operates by randomly sampling a finite set of vehicle states from continuous state space in order to reduce the complicated trajectory planning problem to planning on a finite directed graph. In the optimal control layer, a collision-free state-to-state trajectory planner based on the Gauss pseudospectral method is developed, which can generate both dynamically feasible and optimal flight trajectories. The entire process of solving a DCTSPN consists of two phases. First, in the offline preprocessing phase, the algorithm constructs a PRM, and then converts the original problem into a standard asymmetric TSP (ATSP). Second, in the online querying phase, the costs of directed edges in PRM are updated first, and a fast heuristic searching algorithm is then used to solve the ATSP. Numerical experiments indicate that the algorithm proposed in this paper can generate both feasible and near-optimal solutions quickly for online purposes.     

Universality of Competitive Networks in Complex Networks

The paper proposes a model which helps to investigate the competitive aspect of real networks in quantitative terms. Through theoretical analysis and numerical simulations, it shows that the competitive model has the universality for a weighted network. The relation between parameters in the weighted network and the competitiveness in the competitive network is obtained by theoretical analysis. Based on the expression of the degree distribution of the competitive network, the strength and degree distributions of the weighted network can be calculated. The analytical solution reveals that the degree distribution of the weighted network is correlated with the increment and initial value of edge weights, which is verified by numerical simulations. Moreover, the evolving pattern of a clustering coefficient along with network parameters such as the size of a network, an updating coefficient, an initial weight and the competitiveness are obtained by further simulations.     

基于路由表哈希匹配算法的压缩策略

哈希算法是一种最优的匹配算法。但是在现今的网络应用中,该匹配算法的应用有一定的局限性。在分析了路由表地址匹配的延迟过程之后,得出产生延迟的主要原因是现今的路由表容量比较有限,从而造成在路由表中无法找到IP目的地址。提出了一种以现实的最大路由表容量为准来解决路由匹配延迟的压缩策略。其目的是去掉无法找到路由表目的地址的现象,通过对压缩后路由表容量的仿真试验,结果显示,在路由表中查找目的地址失败的问题已经解决,所以该策略是可行的。     

An improved algorithm for solving all <Emphasis Type="Italic">d</Emphasis>-MPs in multi-state networks

Reliability is a desirable performance indicator of many real-world systems to measure the quality level. One general method for evaluating multi-state reliability is using d-minimal paths (d-MPs). However, being an NP-hard problem, searching for all d-MPs is a rather challenging task. This paper proposes an improved algorithm to solve the d-MP problem. To reduce the search space of d-MPs, a concept of lower capacity bound is introduced into the d-MP problem, and an effective technique is developed to find lower capacity bounds. Meanwhile, the fast enumeration method which is a recent improvement to the traditional enumeration method is employed to solve d-MPs. In addition, by introducing the operation of transforming undirected edges into directed edges, the proposed algorithm is applicable to solving both directed networks and undirected networks. Through numerical experiments, it is found that the proposed algorithm holds a distinct advantage over the existing methods in solving all d-MPs.     

Reliability index algorithm of a sub-domain interconnection large communication network

The normalized weighted capacity reliability index of a sub-domain interconnection large scale communication network is defined and a new algorithm to calculate the reliability index is proposed.The proposed algorithm can be performed using logical or algebraic operation by means of computer-aided programming and the correctness of each key step is validated in detail.This paper takes the sub-domain interconnection symmetrical topological network for a typical example to calculate the network reliability index and verifies the correctness of the proposed algorithm using the real measured statistical data,The real measured results are well in accordance with the results obtained by the proposed algorithm.The result shows that the proposed algorithm is a valid means to estimate the reliability index of a sub-domain interconnection large-scale communication network.     

改进的加权复杂网络节点重要度评估的收缩方法

分析了加权复杂网络的结构特点,综合考虑了边权对节点重要度评估的影响,给出了加权节点重要度的新定义,并提出了改进的适用于加权网络的节点收缩方法.该方法认为最重要的节点就是收缩后加权网络凝聚度最大的节点,其算法的时间复杂度为O(n³).该方法有助于更准确地发现复杂网络中的关键节点.最后的实验分析验证了方法的有效性和可行性.