一种不确定图中最可靠最大流问题的解决方案

最可靠最大流是不确定图中可靠性最高的最大流,它是传统最大流问题在不确定图上的自然延伸.现有的最可靠最大流算法SDBA时间复杂性较高,无法满足实际中不同应用的需求,为此,文中提出一种具有普遍适用性的最可靠最大流解决方案.该方案包含面向不同需求的3种算法:基于负权群落消去的NWCE算法、基于时间约束优先单环消去的SPEA-t算法和基于概率阈值约束优先单环消去的SPEA-p算法.其中,NWCE算法借鉴最小费用最大流的"流平移"思想并基于文中提出的负权群落概念,在辅助剩余图中不断地消去可使可靠性增加而流量不变的负权群落,可证当消去所有负权群落时对应的最大流即为最可靠最大流.根据负权群落中由单环组成的群落占很高比例且相对于多环组成的群落更易查找和消去的性质,同时考虑到NWCE算法为了获得最优解,往往为了消去最后少数几个对概率提高贡献很小的负权群落却花费了很长时间的现象,提出SPEA-t和SPEA-p两种快速近似算法,前者是以规定时间内尽可能逼近最优解为目标,后者是以最少时间达到预设的概率阈值为目标,它们都采用了优先消去概率-时间效益较好的单环群落的策略,加快对最优解的逼近速度,减少或放弃时间开销较大的多环群落的消去,以满足那些对算法时间性能要求很高而结果以近似最优即可的应用需求.实验表明,相对于SDBA算法,NWCE算法结合概率剪枝策略在时间性能上有了数量级的提高,而SPEA-t算法和SPEA-p算法则具有更高的性能和更好的适用性.     

不确定图最小割边问题研究

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在。文中研究的是不确定图中最小割问题,也就是说:在不确定图中,由于数据的不确定性,当某边或者某顶点去掉时,可能造成最小割变化,而通常最为关心的则是这个最小割的最大值在不确定图中的概率是多少。     

不确定图上的kNN查询处理

在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等．同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解.由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用. 在此基础上为了进一步提高效率,算法在不确定图上引入采样技术.最后从理论、实验说明验证了算法的高效性和有效性.     

面向不确定图的概率可达查询

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR).处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度.进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计.     

基于并行图计算框架大规模图最大流加速算法

最大流是一个重要的图计算问题,很多实际场景中如城市车流量和排水管道的排水量等问题若转化为最大流问题可以得到有效的解决.已有工作从多个角度对最大流问题进行了探讨,但仍存在一些问题.针对一些分布式图计算系统进行图分割计算复杂度较高,多次计算存在大量冗余工作等问题,提出基于GraphChi框架的大规模图最大流加速算法.根据原...     

不确定图数据上的不确定查询处理

图数据结构广泛应用于各种领域的数据建模.由于测量手段和问题特性的限制,数据的不确定性普遍存在.这种不确定性表现在图结构数据中,形成不确定图.之前对于不确定图数据上查询处理的研究,主要是在不确定的图结构数据上查找某一结构确定的图.然而,针对不确定的图数据,其查询很可能也是不确定的.该项工作主要是实现查询过程中的双向匹配,即对于一个不确定的查询,在不确定的图上,得到查询与图的一个可能性最大的匹配组合.这样的研究是具有现实意义的,通过不确定图上对于不确定查询的匹配,可以找到两个不确定结构间存在的最大相似结构,并度量其相似性.     

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

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

面向不确定图的k最近邻查询

生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.     

面向不确定平面图的模式匹配查询

平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定平面图的查询处理技术不能有效地处理不确定性,因此利用概率语义描述的平面图的模式进行匹配查询。具体地,使用可能世界概率模型定义不确定平面图,基于该模型,研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界,同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法,可快速地估算出匹配概率,并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割,结果表明此方法优于经典的图像分割算法。     

基于可能图的攻击意图检测方法

攻击图模型是网络风险评估的主要技术之一,其通过攻击步骤之间的因果关系来描述攻击者从初始状态到目标状态的攻击过程,分析的整个过程也是以某种形式化方式表述的图数据为基础的,但分析时很少考虑网络链路、网络拥塞、入侵报警等不确定性。结合不确定图的概念将攻击图扩展为可能攻击图(PAG),给出了可能攻击图的构建方法,同时基于可达概率提出了最大可达概率求解算法和最大攻击子图生成及最大可能攻击路径选取算法。实验结果表明,本文所提方法能够在可接受的时间内生成可能攻击图,并能够有效地推测出攻击意图,为作为网络管理员的管理方提供决策依据。     

Algorithms to Calculate the Most Reliable Maximum Flow in Content Delivery Network

Calculating the most reliable maximum flow (MRMF) from the edge cache node to the requesting node can provide an important reference for selecting the best edge cache node in a content delivery network (CDN). However, SDBA, as the current state-of-the-art MRMF algorithm, is too complex to meet real-time computing needs. This paper proposes a set of MRMF algorithms: NWCD (Negative Weight Community Deletion), SCPDAT (Single-Cycle Preference Deletion Approximation algorithm with Time constraint) and SCPDAP (Single-Cycle Preference Deletion Approximation algorithm with Probability constraint). NWCD draws on the “flow-shifting” algorithm of minimum cost and maximum flow, and further defines the concept of negative weight community. This algorithm continuously deletes the negative weight communities, which can increase reliability while keeping the flow constant in the residual graph. It is proven that when all negative weight communities are deleted, the corresponding maximum flow is the MRMF. SCPDAT tries to approach the optimal solution to the greatest extent possible within the limited time, while SCPDAP tries to reach the probability threshold in the shortest amount of time. Both of these adopt the strategy of first deleting single-cycle communities (which contribute more to the reliability with lower time cost). Experiments show that, compared with SDBA, NWCD combined with the probabilistic pruning achieves an order of magnitude improvement in time cost, while SCPDAT and SCPDAP demonstrate better time performance and increased applicability.     

解决最大流问题的Ford-Fulkerson标号算法

现实生活中很多问题都会建立网络模型来实现,根据建立的图,求其最大值或最小值。最大流问题本质上即是求解极值的问题,相关的实际问题有很多,比如:旅游景点的最大人流量,高速公路的最大车流量,江河大坝的最大水流量等。笔者探讨了该算法在最大流中的应用,并通过实例体现其用法。     

最可靠控制系统的综合

本文讨论利用复式的方法,综合最可靠控制系统的问题.对只受一个约束条件的系统,直接从工程设计中少花钱、多收益的概念出发,加强薄弱环节,平衡提高各个串联环节的可靠性,应用偏微分求最大值的原理,推导出最可靠控制系统的准确表达式.对带有多个约束条件的可靠性最优化问题,则借助拉格朗日乘子法直接求解.同时,指出不受任何条件约束的复式混合故障系统,也有可靠性最优化的问题,并导出了答案.另外举出计算例题,便于一般工程技术人员参阅和应用.本文明确提出按照控制系统中元器件的故障性质分为独立(开路型)故障与相依(短路型)故障两类,这样不但有利于分析元器件或分系统故障对总系统可靠性影响的大小,同时也便于进行最可靠控制系统的设计.     

A Symbolic Algorithms for Maximum Flow in 0-1 Networks

We present an algorithm for finding the maximum flow in a 0-1 network. The algorithm is symbolic and does not require explicit enumeration of the nodes and edges of the network. Therefore, it can handle much larger graphs than it was previously possible (more than 10³⁶ edges). The main idea is to trace (implicitly) sets of edge-disjoint augmenting paths. Disjointness is enforced by solving an edge matching problem for each layer of the network with the help of newly defined priority functions.     

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

基于完全图的能量高效可靠分簇算法

在采用多跳通信方式的分簇无线传感器网络中,接近sink点的簇头负担较重,容易过早耗尽能量而失效,引起大量簇重组。针对该问题,基于完全图理论提出一种能量高效可靠分簇算法以均衡簇间负载,设计动态簇头轮换机制来实现快速簇头选举和故障处理。仿真结果表明,该算法能延长网络生命周期、节约网络能耗、提高网络可靠性。