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

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

基于节点中心性的时变复杂网络布局算法

目前,时变网络布局算法主要从网络结构和美学指标出发维持用户意象图,并没有考虑节点中心性的影响。为此,将嵌入节点中心性改进传统静态网络布局算法为时变网络布局算法。首先,引用节点半局部中心性指标改进PageRank算法来评估节点的中心性;然后,根据节点的中心性和稳定度来计算动态半径作为节点的约束因子;最后,在静态网络布局算法中加入控制节点移动的约束因子,形成基于节点中心性的时变网络布局算法。实验结果表明,所提方法可以在保存用户意象图和美学标准间达到平衡,且对大型时变网络也具有良好的计算能力。     

无线传感器网络中一种关键节点集轮换算法

针对传感器网络多跳通信和多对一的流量特征,提出负载均衡的约束条件,将关键节点集选取问题转化为多目标优化问题,提出一种基于非支配遗传算法的关键节点集轮换算法.通过节点密度控制机制,从投放的节点池中选取关键节点集,以满足监测区域覆盖连通.在每轮网络工作的开始,激活不同的关键节点集,保证在每个时刻,有且仅有一个节点集完成对网络的充分覆盖.仿真结果表明该算法能够快速收敛于最优解,极大化网络关键节点集数目,有效延长网络的生存时间.     

有向图"与连通"遍历中初始结点集求解分析

研究内容是在系统故障图分析中抽象出的一个基础问题。定义了有向图"与连通"概念。提出了如何确定有向图的初始结点集,从初始结点集出发,经"与连通"遍历整个图的问题,将初始结点集分解为源结点集和圈核结点集,并提出了求解初始结点集的一个算法。研究结论及算法被应用于多项自动化处理中。     

传感器网络中一种能量高效的数据收集算法

为了在无线传感器网络中降低能耗和最大化网络生存期,提出一种能量高效的数据收集算法(energy efficient data gathering algorithm, EEDGA)。该算法利用移动代理模型在网络中进行数据收集。首先,EEDGA根据监测精度的要求控制活动节点的数量;然后,通过求最小支配集得到具体的工作节点;最后,利用蚁群算法规划移动代理迁移的最优路线,移动代理以渐进方式收集活动节点的监测数据。仿真结果表明,与典型算法相比,该算法具有更低的能耗和更长的网络生存期。     

改进的聚类算法及在复杂大群体决策中的应用

针对现有FCM聚类算法中存在的局部极值和伸缩性较差等问题,提出了基于全部最小连通支配集算法(minimum connected donating set algorithm,MCDSA)的改进的聚类算法(minimum fuggy C-means,MF-CM)。用改进的聚类算法MFCM辅助复杂大群体决策(complex huge group-decision,CHGDS),定义了群体偏好矢量和群体一致性指标,提供了一种新的解决CHGDS中群体决策的理论和方法,并通过实验证明了该方法的有效性和稳定性。还提供了基于属性加权进化的群体一致性决策机制新思路。     

无线传感器网络移动Agent路由算法的研究与仿真

提出一种新的基于虚拟连通拓扑子图的优化模型用于无线传感器网络移动Agent路由．建立包含有效节点的虚扭连通拓扑子图，将Agent访问路径分解为采集子路径和返回子路径，提出一种基于GA与离散PSO的混合算法GAPSO用于求解该问题。该算法可大大降低解空间复杂度，提高搜索效率。仿真结果表明随着网络规模增大，该优化模型优势明显，GAPSO表现出比GA更好的性能。     

多目标决策下Pareto非支配解的快速构造方法

有效构造非支配解集可加快Pareto前沿的求解速度,提升多目标决策的质量和效率.在非支配解定义和性质分析基础上,推导出支配关系传递性引理,非支配解集构造定理及引理,并据此提出一种基于性质定理的非支配解集构造方法.基于所提方法,分析其循环次数和比较次数,推导出在最坏情况下能算出确定值的复杂度计算公式.最后证明该方法的正确性与完备性,分析最坏情形下其构造集的结构特征,并通过ZDT1~ZDT3测试函数进行检验.结果表明:所提方法比排除法和选举法的计算复杂度更低,构造速度更快.     

延迟容忍网络中基于社会属性的负载感知路由

延迟容忍网络中采用中心性作为路由尺度会使部分节点承载过多的网络流量。针对这一问题,提出了一种基于社会属性的负载感知路由算法。使用节点的介数中心性（betweenness centrality, BC）和相似性两个社会属性指标以及节点的负载状况作为选择中继节点的依据,避免了消息传播能力强的节点产生严重的拥塞,均衡了网络流量。仿真结果表明,该算法能够提高网络的交付比率,减小网络的开销。     

基于超立方体弱连通性质的多态网络研究

针对超立方体互联网络可能出现的链路故障以及实现本地化处理的需要,分析了3类已有的子立方体弱连通性质.通过探讨由于不同的维度序列而产生的多种节点集团,提出了基于子立方体弱连通性质的多态网络及其基本特征.仿真实验表明,所提出的多态网络比基于单一维度序列的网络,更能准确地反映实际存在的满足弱连通性质的节点集团.     

HAMILTONICITY IN 2-CONNECTED {K_(1,3) F}-FREE GRAPHS

ＨＡＭＩＬＴＯＮＩＣＩＴＹＩＮ２－ＣＯＮＮＥＣＴＥＤ｛Ｋ_（１，３）Ｆ｝－ＦＲＥＥＧＲＡＰＨＳ￥ＬＩＧｕｏｊｕｎ（ＭａｔｈｅｍａｔｉｃｓＤｅｐｅｒｔｍｅｎｔｏｆＹａｎｔａｉＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ，Ｙａｎｔａｉ２６４０００，Ｃｈｉｎａ）ＬＩＵ?..     

基于连通树的兵棋推演热区检测算法

提出了一种基于连通树的热区检测算法, 可检测任意形状的热区, 目的是通过检测兵棋推演过程中军事行动频繁的区域, 为受训人员了解整个战场态势提供辅助参考. 算法在明确了热区定义的基础上, 首先构建连通树将数据集按连通区域进行最小划分, 再根据设定的密度阈值对连通树进行剪枝. 剪枝处理后的每棵连通子树是最终的热区. 理论和实验结果均验证了该算法的有效性.     

EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS

In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.     

SPANNING TRAILS OF GRAPHS

Let G be a 2-edge-connected simple graph.We give a sufficient condition in which for anyx,y∈V(G),there is an(x,y)-trail which contains every vertex of G(x-y is allowed)exceptsome graphs.     

LONGEST CYCLES IN REGULAR 3—CONNECTED GRAPHS

It is proved that for k≥71,the circumference c(G)of a 3-connected k-regular graphG on n vertices is at least min{|G|,3k+5}.This result is essentially best possible.     

ASYMPTOTIC BEHAVIOR OF THE SOLUTION FOR THE NEUTRON TRANSPORT EQUATION IN A SLAB WITH GENERALIZED REFLECTING BOUNDARY CONDITIONS

This paper discusses the neutron transport equation in a slab with generalized reflectingboundary conditions.By means of the positive C_0-semigroup theory,we have proved that this problemhas a unique nonnegative solution and found the spectral property of the corresponding transportoperator.Finally we give the asymptotic behavior of the solution for this equation.     

网络系统的点权核、点权核度及应用

具有社会关系结构的经济系统及通讯网络系统等许多现实的系统理论常常归结为赋点权的连通网络系统的研究．本文对节点加权的连通的网络系统引进了点权核与点权核度的概念，推广了［４］中核与核度的概念，研究了点权核与点权核度的基本理论，证明了点权核度的取值范围与点权核、点权核度的计算结构定理．同时还通过引入极大点权核的连通包等概念提出一种新的点权网络系统的层次分析法．     

网络中的最优控制树问题

众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.     

多属性决策的等级偏好优序法

提出了等级偏好占优关联系数的新概念, 在此基础上给出了多属性决策的等级偏好优序法. 等级偏好优序法克服了已有优序法的不足, 使各方案优劣的区分度更明显, 而且等级偏好优序法可以通过计算机编程进行实现, 从而可使等级偏好优序法在实际决策问题中发挥重要作用.