适合复杂网络分析的最短路径近似算法

基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.     

基于k-shell的复杂网络最短路径近似算法

复杂网络最短路径经典算法的处理效率较低，不适用于大规模复杂网络，而现有近似算法通用性有限，且计算准确率不理想，不能满足规模日益扩大的复杂网络中的最短路径计算需求。针对于此，提出基于[k]-shell的复杂网络最短路径近似算法。算法利用节点的[k]-shell值进行网络划分并引导搜索路径，利用超点聚合处理[k]-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明，算法通用性较好，在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率。     

双人博弈问题中的蒙特卡洛树搜索算法的改进

蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。 由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显著改进了蒙特卡洛树搜索的准确性和效率。     

基于遗传退火算法的最大简约树构建的研究

针对最大简约法的搜索速度慢等特点,提出了一种遗传算法与模拟退火算法相结合的启发式搜索方法.利用模拟退火算法保障物种的多样性,克服了遗传算法的早熟现象,加快了实验后期的收敛速度.结果表明,该算法的准确性和运算效率都有较大提高.     

基于排序学习的复杂网络节点接近中心性近似排序

随着网络规模的增大, 节点接近中心性的精确算法效率越来越低. 本文提出一种基于RankNet排序学习算法的模型以快速逼近复杂网络节点接近中心性排序. 首先通过相关性分析得到与接近中心性呈正相关的节点重要度指标作为模型的输入特征, 然后在给定网络中随机选取节点子集用于模型的训练样本数据. 在一个真实航空网络数据集和典型的复杂网络模型上对提出的模型进行了验证, 实验结果表明基于RankNet排序学习算法的模型能够在一定程度上降低计算时间复杂度, 而且保持了较高的近似准确性, 所提出的模型排序效果明显优于采用回归学习的基准模型.     

目的驱动最短路径树的快速算法

通过分析目的驱动最短路径生成树算法DDSP(Destination-drivenShortestPath)的节点搜索过程,提出一种以较小的存储空间为代价,减少DDSP算法在搜索当前节点、父节点和待处理节点时搜索空间的快速算法FDDSP(Fastdestination-driv-enshortestpath)。随机网络模型的仿真结果表明,FDDSP算法生成的多播树与DDSP算法相同,但FDDSP算法的效率更高。     

基于度系数的社团分裂算法

复杂网络社团划分中的分裂算法是比较经典的算法,本文通过引入度系数这一局部变量,通过运用kruksal算法对经典的GN算法进行适当改进,提高了搜索效率,并通过对其模块度特征的分析,表明了结果的准确性。     

一种应用遗传算法的彩色图像分割方法

遗传算法在复杂大空间搜索近似最优值有着很好的效果,利用遗传算法的优势,应用其解决图像分割问题.图像分割中,区域间差别度和区域内相似度是评价图像分割的重要因素,用遗传算法优化图像区域间差别和区域内相对相似度,获得高质量的图像分割结果.为了提高算法效率,采用贪心方法进行图像预处理,以及最小生成树初始化来减小算法的规模和搜索空间.实验证明采用遗传算法在图像分割问题可取得有效的结果.     

一种自适应拟牛顿-状态转移混合智能优化算法及应用

针对基本状态转移算法在某些复杂高维函数寻优后期表现出收敛慢、精度低的问题,引入局部搜索拟牛顿算子,构造一种混合状态转移算法,以弥补状态转移算法后期搜索效率低和拟牛顿法对初始点敏感的不足,保证算法能够快速收敛到全局或精度较高的近似最优解.混合算法采用自适应调用策略,判断算法收敛到全局最优附近的时机,并在此时调用拟牛顿算子,最大程度上发挥其局部搜索能力强的优势.在算法收敛到全局最优或者近似最优解附近时,不再进行无用的拟牛顿局部搜索,节省计算资源.通过对典型测试函数的仿真与无线传感器网络定位问题的求解,验证了混合智能优化算法的有效性,且与其他群智能算法相比,混合算法具有更高的收敛速度与精度.     

基于重叠区域的高性能近似kD树算法

kD树是近邻搜索中应用最广泛的算法之一,针对其性能随着空间维度的增加而迅速降低的问题,提出一种可应用到高维空间的kD树搜索算法——okD树.在该okD树的创建过程中,左右子结点之间保留重叠区域,重叠区域不参与后续的划分而是直接传递到子结点;在搜索过程中,对于存在重叠区域的子结点不进行回溯,以提高okD树的搜索效率,不进行回溯的子结点中包含的重叠区域扩大了搜索范围,从而提高了搜索精度.实验结果表明okD树算法的性能优于当前主流的近似kD树算法.     

Efficient and Scalable Algorithms for Inferring Likely Invariants in Distributed Systems

Distributed systems generate a large amount of monitoring data such as log files to track their operational status. However, it is hard to correlate such monitoring data effectively across distributed systems and along observation time for system management. In previous work, we proposed a concept named flow intensity to measure the intensity with which internal monitoring data reacts to the volume of user requests. We calculated flow intensity measurements from monitoring data and proposed an algorithm to automatically search constant relationships between flow intensities measured at various points across distributed systems. If such relationships hold all the time, we regard them as invariants of the underlying systems. Invariants can be used to characterize complex systems and support various system management tasks. However, the computational complexity of the previous invariant search algorithm is high so that it may not scale well in large systems with thousands of measurements. In this paper, we propose two efficient but approximate algorithms for inferring invariants in large-scale systems. The computational complexity of new randomized algorithms is significantly reduced, and experimental results from a real system are also included to demonstrate the accuracy and efficiency of our new algorithms.     

Constructing Multicast Routing Tree for Inter-cloud Data Transmission: An Approximation Algorithmic Perspective

Networking plays a crucial role in cloud computing especially in an inter-cloud environment, where data communications among data centers located at different geographical sites form the foundation of inter-cloud federation. Data transmissions required for inter-cloud federation in the complex inter-cloud networking system are often point-to-multi points, which calls for a more effective and efficient multicast routing algorithm in complex networking systems. In this paper, we investigate the multicast routing problem in the inter-cloud context with K constraints where K ≥ 2. Unlike most of existing algorithms that are too complex to be applied in practical scenarios, a novel and fast algorithm for establishing multicast routing tree for inter-clouds is proposed. The proposed algorithm leverages an entropy-based process to aggregate all weights into a comprehensive metric, and then uses it to search a multicast tree (MT) on the basis of the shortest path tree (SPT). We conduct complexity analysis and extensive simulations for the proposed algorithm from the approximation perspective. Both analytical and experimental results demonstrate that the algorithm is more efficient than a representative multi-constrained multicast routing algorithm in terms of both speed and accuracy, and thus we believe that the proposed algorithm is applicable to the inter-cloud environment.      

基于故障树的专家系统推理机设计

针对微小卫星强实时性和资源受限的特点,提出一种基于故障树的专家系统推理机。根据广度优先搜索设计正向推理算法,根据深度优先搜索设计逆向推理算法,2种算法在时间和空间上均满足线性复杂度。实验结果表明,该推理机可满足微小卫星对实时性的要求,同时也能节省星上资源。     

节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。     

弱连接边缘独立判别社交网络社区快速生成树推荐

针对传统社交网络社区推荐算法精度不高且计算复杂度过高的问题,提出一种弱连接边缘独立判别社交网络社区快速生成树检测算法,在提高社区推荐精度同时,降低算法计算复杂度。首先,结合社交网络社区推荐特点,设计基于边缘重量分配节点相似性的最大生成树算法,实现对社交网络社区的有效检测;其次,针对所提算法,存在弱连接边缘重复添加、删除,浪费计算资源的问题,提出弱连接边缘独立判别的快速生成树检测算法,进一步提高算法计算效率;最后,通过在标准测试数据库中的实验对比,验证了所提算法的有效性。     

基于Gnutella协议的P2P网络路由搜索算法:Light-Flooding

通过对Gnutella协议搜索算法的分析，结合Gossip分布式向前搜索算法和生成树算法的优点，实现了一种高效的路由搜索算法：Light—Flooding。实验结果表明：与Gossip算法相比，Light—Flooding算法提高搜索效率63．4％，减少冗余消息60％，平均延迟为2．6s，使网络的整体综合性能维持在一个优良状态。     

基于加权模糊隶属度的二叉树多分类算法

针对二叉树支持向量机多分类算法准确率与分类效率较低的问题,提出了一种基于加权模糊隶属度的二叉树支持向量机多分类算法（binary tree support vector machines multi-classification algorithm based on weighted fuzzy membership,PF-BTSVM）。该算法依据最大最小样本距离与质心距离构造出一个近似完全二叉树,提高了整体结构的分类效率;利用模糊隶属度函数以及正负辅助惩罚因子对训练集进行筛选,剔除掉对分类无用的样本与噪声值,实现了训练集的提纯并且削弱了不平衡分类时超平面的偏移。在数据集上的实验结果表明,与其他二叉树多分类算法相比,该算法在提高了分类准确率以及稳定性的的同时还加快了训练与分类的速度,而且这种优势当分类的不平衡度越大时越明显。     

基于Sherman-Morrison公式的K-FAC算法

二阶优化方法可以加速深度神经网络的训练,但是二阶优化方法巨大的计算成本使其在实际中难以被应用.因此,近些年的研究提出了许多近似二阶优化方法的算法.K-FAC算法提供了一种近似自然梯度的有效方法.在K-FAC算法的基础上,结合拟牛顿方法的思想,提出了一种改进的K-FAC算法.在开始的少量迭代中利用KFAC算法计算,在后续迭代中构造秩–1矩阵,通过Sherman-Morrison公式进行计算,大大降低了计算复杂度.实验结果表明,改进的K-FAC算法比K-FAC算法有相似甚至是更好的实验表现.特别的,改进的K-FAC算法与KFAC算法相比减少了大量的训练时间,而且与一阶优化方法相比,在训练时间上仍具有一定的优势.     

Experiments with improved approximate mean value analysis algorithms

Approximate mean value analysis (MVA) is a popular technique for analyzing queueing networks because of the efficiency and accuracy that it affords. In this paper, we present a new software package, called the improved approximate mean value analysis library (IAMVAL), which can be easily integrated into existing commercial and research queueing network analysis packages. The IAMVAL packages include two new approximate MVA algorithms, the queue line (QL) algorithm and the fraction line (FL) algorithm, for analyzing multiple class separable queueing networks. The QL algorithm is always more accurate than, and yet has approximately the same computational efficiency as, the Bard–Schweitzer proportional estimation (PE) algorithm, which is currently the most widely used approximate MVA algorithm. The FL algorithm has the same computational cost and, in noncongested separable queueing networks where queue lengths are quite small, yields more accurate solutions than both the QL and PE algorithms.