[1]张柏礼,杨娟,吕建华,等.基于不确定图的最可靠最大流的改进算法[J].东南大学学报(自然科学版),2015,45(2):241-246.[doi:10.3969/j.issn.1001-0505.2015.02.008]
 Zhang Baili,Yang Juan,Lü Jianhua,et al.Improved algorithm of most reliable maximum flow on uncertain graph[J].Journal of Southeast University (Natural Science Edition),2015,45(2):241-246.[doi:10.3969/j.issn.1001-0505.2015.02.008]
点击复制

基于不确定图的最可靠最大流的改进算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
45
期数:
2015年第2期
页码:
241-246
栏目:
计算机科学与工程
出版日期:
2015-03-20

文章信息/Info

Title:
Improved algorithm of most reliable maximum flow on uncertain graph
作者:
张柏礼12杨娟1吕建华12田伟3
1东南大学计算机科学与工程学院, 南京 211189; 2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189; 3南京弘毅电气自动化有限公司, 南京 210039
Author(s):
Zhang Baili12 Yang Juan1 Lü Jianhua12 Tian Wei3
1School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China
3Nanjing Hongyi Electric Automation Technology Co., Ltd, Nanjing 210039, China
关键词:
不确定图 最大流 流可靠性 最小割
Keywords:
uncertain graph maximum flow flow reliability minimum cut
分类号:
TP311
DOI:
10.3969/j.issn.1001-0505.2015.02.008
摘要:
针对网络规模和稠密度的增大最可靠最大流SDBA算法性能下降较快的不足,提出了基于概率和割集双过滤的状态空间划分算法DF-SDBA.首先,在状态空间划分过程中使用概率约束,针对每一个待处理的区间,筛选掉下界分布概率值小于当前最可靠最大流分布的未处理区间,有效地减少了算法迭代的次数;然后,针对不确定的区间使用割集约束,即在区间上界对应的子图中求出最大流,同时求出最小割集,根据最小割集中的边必须都出现在合格子区间上界向量中这一规则,对待划分的子区间进行筛选,从而进一步减少了划分区间的数量.实验结果表明,相对于SDBA算法,DF-SDBA算法有效地减少了需要划分的区间,很大程度上克服了网络规模和稠密度对算法性能的影响,具有显著的性能优势,有效地提高了算法的适用性.
Abstract:
For the most reliable maximum flow problem(MRMF), the performance of the space decomposition-based algorithm(SDBA)decreases rapidly with the increase in size and density of the graph. The probability filter and the cut-set filter are therefore used to solve this problem and the double filter space decomposition-based algorithm(DF-SDBA)is proposed. First, the probability constraint is used to filter out all intervals in the process of space decomposition. For each interval to be processed, the DF-SDBA algorithm filters off the intervals of which the probability is smaller than the current maximum flow to effectively reduce the number of iterations. Then the cut-set constraint is applied to the unspecified intervals. It computes the maximum flow in the upper bound of the unspecified interval, meanwhile the minimum cut-sets are obtained. Based on the rule that all the edges in the cut-sets must exist in the upper bound of each interval, the unspecified intervals are filtered out. The experimental results show that the DF-SDBA algorithm can not only effectively reduce the number of the intervals in need of dividing, but also reduce the impact of network size and density compared with the SDBA algorithm. The DF-SDBA algorithm has significant performance advantages and improves the applicability of algorithms.

参考文献/References:

[1] Hintanen P, Toivonen H, Sevon P. Fast discovery of reliable subnetworks [C]//International Conference on Advances in Social Networks Analysis and Mining. Odense, Denmark, 2010: 104-111.
[2] Hintsanen P. The most reliable subgraph problem [C]//European Conference on Principles and Practice of Knowledge Discovery in Databases. Crete, Greece, 2007: 471-478.
[3] 邹兆年,李建中,高宏,等.从不确定图中挖掘频繁子图模式[J].软件学报,2009,20(11):2965-2976.
  Zou Zhaonian, Li Jianzhong, Gao Hong, et al. Mining frequent subgraph patterns from uncertain graphs [J]. Journal of Software, 2009, 20(11): 2965-2976.(in Chinese)
[4] 张硕,高宏,李建中,等.不确定图数据库中高效查询处理[J].计算机学报,2009,32(10):2066-2079.
  Zhang Shuo, Gao Hong, Li Jianzhong, et al. Efficient query processing on uncertain graph databases [J]. Chinese Journal of Computers, 2009, 32(10): 2066-2079.(in Chinese)
[5] Yuan Ye, Wang Guoren, Chen Lei, et al. Efficient subgraph similarity search on large probabilistic graph databases [C]//International Conference on Very Large Database. Istanbul, Turkey, 2012: 800-811.
[6] 张海杰,姜守旭,邹兆年.不确定图上的高效top-k近邻查询处理算法[J].计算机学报,2011,34(10):1885-1896.
  Zhang Haijie, Jiang Shouxu, Zou Zhaonian. An efficient algorithm for top-k proximity query on uncertain graphs [J]. Chinese Journal of Computers, 2011, 34(10): 1885-1896.(in Chinese)
[7] 张应龙,李翠平,陈红,等.不确定图上的kNN查询处理[J].计算机研究与发展,2011,48(10):1850-1858.
  Zhang Yinglong, Li Cuiping, Chen Hong, et al. K-nearest neighbors in uncertain graph [J]. Journal of Computer Research and Development, 2011, 48(10): 1850-1858.(in Chinese)
[8] Rasteiro D D M L, Anjo A J B. Optimal paths in probabilistic networks [J]. Journal of Mathematical Sciences, 2004, 120(1): 974-987.
[9] Alexopoulos C. A note on state-space decomposition methods for analyzing stochastic flow networks[J]. IEEE Transactions on Reliability, 1995, 44(2): 354-357.
[10] Jane Chin-Chia, Laih Yih-Wenn. A practical algorithm for computing multi-state two-terminal reliability [J]. IEEE Transactions on Reliability, 2008, 57(2): 295-302.
[11] Jane Chin-Chia, Laih Yih-Wenn. Computing multi-state two-terminal reliability through critical arc states that interrupt demand [J]. IEEE Transactions on Reliability, 2010, 59(2): 338-345.
[12] Ramirez-Marquez J E, Coit D W. A monte-carlo simulation approach for approximating multi-state two terminals reliability [J]. Reliability Engineering & System Safety, 2005, 87(2): 253-264.
[13] Rocco C M, Muselli M. Approximate multi-state reliability expressions using a new machine learning technique [J]. Reliability Engineering & System Safety, 2005, 89(3): 261-270.
[14] 蔡伟,张柏礼,吕建华.不确定图最可靠最大流算法研究[J].计算机学报,2012,35(11):2371-2380.
  Cai Wei, Zhang Baili, Lü Jianhua. Algorithms of the most reliable maximum flow on uncertain graph [J]. Chinese Journal of Computers, 2012, 35(11): 2371-2380.(in Chinese)
[15] Ford L R, Fulkerson D R. Flows in networks [M]. Princeton: Princeton University Press, 1962.
[16] Klingman D, Napier A, Stutz J. NETGEN: a program for generating large scale capacitated assignment, transportation and minimum cost flow network problems [J]. Management Science, 1974, 20(5): 814-821.

备注/Memo

备注/Memo:
收稿日期: 2014-09-17.
作者简介: 张柏礼(1970—),男,博士,副教授,bailey_zhang@163.com.
基金项目: 国家自然科学基金资助项目(61300200,61232007,61073059).
引用本文: 张柏礼,杨娟,吕建华,等.基于不确定图的最可靠最大流的改进算法[J].东南大学学报:自然科学版,2015,45(2):241-246. [doi:10.3969/j.issn.1001-0505.2015.02.008]
更新日期/Last Update: 2015-03-20