收缩邻居节点集方法求解有向网络的最大流问题

最大流问题在许多领域有广泛的应用,然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题.对一个给定的有向网络,文中提出一种收缩邻居节点集的方法(CNA)求解其最大流.该方法通过收缩邻居节点集有效降低网络规模,使经典算法及改进算法可直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半,且能以较小的误差求得初始网络的最大流.     

基于网络流的C语言代码查重研究

随着计算机行业的快速发展,在高校中代码抄袭的现象频频出现.方案兼具准确性与实用性,可以有效地检测出代码之间的相似程度.对于代码文本的降噪处理,将降噪后的代码文本构成流网络模型,通过比较节点间的最长公共子序列来建边,将已构造的二分图转化为流网络,求解网络流最大流,使用Dinic算法计算最大流的方案.     

基于记忆化搜索的分层网络最大流算法

当前,路由选择算法、计算机视觉图像切割以及机器学习领域的许多问题都可以归结为求解网络最大流.为了提高基于分层网络最大流算法的效率,提出了一种基于记忆化搜索策略的最大流算法,针对传统EdmondsKarp算法和Dinic算法重复搜索无效路径所导致的额外开销问题,设计了一种能够记录搜索状态的记忆化搜索策略,来避免重复搜索流网络中的无效部分.实例分析表明了记忆化搜索策略的高效性与可行性.最终实验结果表明,基于记忆化搜索的最大流算法执行效率优于传统的Dinic算法.     

求解网络最大流问题的信念传播算法

为解决目前网络最大流问题求解效率低、数据溢出等问题,设计求解网络最大流问题的信念传播算法.根据网络最大流问题的特性,使最大流问题的线性规划方程与信念传播算法传递方程结合,得到描述函数,将带权随机有向图映射为对应的因子图模型;在此模型基础上,利用信念传播算法的信息迭代方程进行特征值收敛计算,提高寻优效率.选取若干随机有向图进行数值实验,实验结果表明,该算法在寻优速度上优于同类算法,验证了其可行性及有效性.     

基于深度优先的一种网络最大流求解法

网络最大流问题在工程和科学领域应用广泛,许多线性规划的实际问题都可转化为网络最大流的模型来求解,开辟了图论应用的新途径.为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题,文中在原有算法的基础上作了一些改进,应用图的深度优先搜索原理,提出一种新的求解最大流问题的算法.该算法可以简单快速地找到增广链,提高了算法效率和可控性,易于实现,且避免了标号过程,只需要在一个图上即可完成,整个运算过程直观性强,计算方便.     

级连层次图的网络最大流算法研究

给出一种通过构造网络级连层次图的方法,来间接求出最大网络流的算法。对于给定的有n个顶点,e条边的网络N=G,s,t,C,该算法可在On2时间内快速求出流经网络N的最大网络流及达最大流时的网络流。     

网络最大流求解算法的研究

近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展。文章简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法。此算法使得计算网络最大流变得简便,且具有很强的实用性。     

基于图分割的求解最大流加速方法研究

随着科技的不断发展,交通、信息服务、电信等领域产生的数据都在飞速增长,通常这些数据都是以大规模图的形式呈现出来,城市交通最大车流量、双十一用户的交易信息传输、承载能力等很多实际问题都可以转化为最大流问题,大规模图中的最大流问题已经成为图论体系中的重要研究方向。现有的网络最大流问题,经过人们多年来的努力,建立的理论已趋于完善,但是大规模图的求解最大流的效率较低,依然无法满足目前很多应用场景的需求。为解决上述问题提出了利用割点构造原图覆盖图,确定从源点到汇点在覆盖图上对应的唯一路径后,将该路径上的节点对应的子图提交到GraphChi平台并行计算最大流。保证了每个子图最大流计算的独立性,可快速求解大规模图的最大流的。     

蚁群算法在网络最大流问题中的应用

网络最大流问题是一个经典组合优化问题,是计算机科学和运筹学的重要内容。根据蚁群算法的特点,将网络最大流问题进行相应地转化,然后利用蚁群算法进行求解。仿真结果表明,该算法能方便快捷地解决最大流问题,是行之有效的方法。     

基于邻域相似的层次粒化的网络表示学习方法

捕获更多的结构特征给网络表示学习方法带来较高的复杂度.基于分层递阶思想,文中提出基于邻域相似的层次粒化的网络表示学习方法,降低已有网络表示学习方法的复杂度.首先利用节点邻域相似性将网络逐步压缩至粗粒度的表示空间中.然后利用已有的网络表示学习方法学习粗粒的特征表示.最后利用图卷积网络将已学习的粗粒特征逐步细化为原始网络的节点表示.在多个数据集上的实验表明,文中方法可以快速有效大幅压缩网络,降低算法的运行时间.针对节点分类和链接预测任务,当粒化层次较低时,文中方法可以较大幅度提升原有算法的性能.     

基于动态间隔压缩的鲁棒网络流水印算法

针对基于间隔质心的流水印缺乏纠错能力且难以抵御多流攻击的问题,提出一种基于动态间隔压缩的鲁棒网络流水印算法。该算法在基于间隔质心流水印基础上利用编解码技术增强其纠错能力,将携带同一水印信息的网络流量采用动态间隔压缩的方式调制为多种模式以抵御多流攻击。同时在检测端对水印进行分层检测,减少检测端计算资源浪费。实验结果表明,当检测阈值设为0.8时,误报率低于5%,且水印检测率可高于原始间隔质心方法10%左右,合并多条水印数据流后也无明显静默间隔。可见该算法具有良好的鲁棒性和隐蔽性,能够有效提高网络流水印的可用性。     

大流识别方法综述

首先介绍大流识别方法的研究动机和国内外发展现状,根据采用技术的差异,将现有方法分为基于抽样的方法、基于计数的方法、基于最近最少使用算法的方法和基于哈希的方法,简要分析了几类方法的优缺点;然后分别选取经典算法进行剖析,并给出大流识别的典型应用;最后探讨了值得进一步研究的问题和可能的发展方向.     

On a simple deadlock recovery problem

In this note a polynomial time algorithm is given for the minimum cost recovery from a deadlock situation resulting from a new request by a single task in a deadlock free system of tasks. We obtain the algorithm by reducing this deadlock recovery problem to a particular network flow problem.     

Circular and radial design comparison of survivability in asymmetrical hierarchical networks

Communication networks are immensely important today, since both companies and individuals use numerous services that rely on them. This paper considers the design of hierarchical (communication) networks. We consider the survivability of asymmetrical hierarchical network flows (AHNF), when arcs failure and, hence, flow destruction is probable. In such networks, it is supposed that the remaining arc capacities are known and the guaranteed evaluation of the functional capability assumes finding the worst distribution of flow in the destructed network. Since, in the network flows, a unique efficiency criterion is not generally known or defined, we assess the quality of the network functioning by a measure of demands satisfaction, i.e. the fraction of satisfied demands at the sink nodes. With regard to this criterion, we construct the mathematical model of the network regardless of the design structure. Then, by defining a measure of satisfying the demands, we compute and compare the survivability of two well-known reserve designs, namely radial and circular reserves.     

基于混合神经网络的异常信息流检测模型

针对传统的异常信息流检测方法的不足,设计了一个异常信息流检测模型,该模型采用了神经网络中的决策树算法对信息流进行归纳分类,采用信息增益作为分类属性选择标准来构造规则决策树,针对网络流量进行分析,能提高检测速度。开辟了一条检测异常信息流的新途径。     

无线MESH网络安全模型研究

近年来,无线Mesh网络已成为一个倍受关注的研究领域,对无线Mesh网络流量特性的研究将有助于网络协议的研究、评估,本文通过对无线Mesh测试网上采集的数据包进行统计分析,揭示了网络流量具有自相似的特性,并通过仿真进一步分析了节点移动性对流量自相似性的影响。     

浅析网络异常流量分析检测研究与实现

伴随着互联网技术与网络业务的快速发展,网络规模逐渐扩大,网络运用开始逐步朝多元化、多样化以及复杂化的方向发展.现今,网络流量监测已经逐渐发展为计算机网络运用当中一个必不可少的内容与环节.文章将对网络异常流量加以说明,并对网络异常流量检测技术研究与实现进行分析与研究.     

基于SNMP的校园网流量监测与分析

网络流量检测与分析是网络管理的一项重要内容,利用标准的SNMP协议及SNMP＋＋技术,开发了在Win-dows平台下的校园网流量监测和分析系统。系统实现简单、工作可靠稳定,可以作为开发局域网络监控系统软件的范例。     

Computing Mimicking Networks

A mimicking network for a k -terminal network, N , is one whose realizable external flows are the same as those of N . Let S(k) denote the minimum size of a mimicking network for a k -terminal network. In this paper we give new constructions of mimicking networks and prove the following results (the values in brackets are the previously best known results): S(4)=5 [2 ¹⁶ ] , S(5)=6 [2 ³² ] . For bounded treewidth networks we show S(k)= O(k) [2^ 2 ^k ] , and for outerplanar networks we show S(k) 10k-6 [k ² 2 ^k+2 ] . Received April 1, 1997; revised December 10, 1997.