基于图分解的最优三角化图及连接树的构建

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2021-12-27

基于图分解的最优三角化图及连接树的构建徐平峰¹, 王福友¹, 邓文礼², 马文卿³, 董小刚¹1. 长春工业大学统计系, 长春 130012;
2. 恒生管理学院数学与统计系, 香港 999077;
3. 东北师范大学数学与统计学院, 长春 130024 Construction of Optimal Triangulation and Junction Tree by Graph Decomposition XU Pingfeng¹, WANG Fuyou¹, TANG Manlai², MA Wenqing³, DONG Xiaogang¹1. Department of Statistics, Changchun University of Technology, Changchun 130012, China;
2. Department of Mathematics and Statistics, Hang Seng Management College, Hong Kong 999077, China;
3. School of Mathematics and Statistics, Northeast Normal University, Changchun 130024, China

摘要
图/表
参考文献(0)
相关文章(15)
点击分布统计
下载分布统计
-->

全文: PDF(524 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要本文基于分解贝叶斯网道义图改进了传播算法的三角化图及连接树的构建.证明了寻找最优三角化图问题可以分解为素块上独立的小的子问题.于是，所有素块的最优三角化图的并即为贝叶斯网的最优三角化图.进一步，我们给出了一个算法，通过连接各个素块的最优三角化图的团树来构建全局最优三角化图的团树.我们进行了模拟实验来展示分解对于求三角化图及连接树的效果.

服务

加入引用管理器

E-mail Alert

RSS

收稿日期: 2011-04-14

PACS:

O29

基金资助:国家自然科学基金（11571050，11401047，11371083，11631003，11690012，11571051），吉林省科技发展计划项目（No.20140520059JH）资助项目.

引用本文:

徐平峰, 王福友, 邓文礼, 马文卿, 董小刚. 基于图分解的最优三角化图及连接树的构建[J]. 应用数学学报, 2017, 40(4): 594-611. XU Pingfeng, WANG Fuyou, TANG Manlai, MA Wenqing, DONG Xiaogang. Construction of Optimal Triangulation and Junction Tree by Graph Decomposition. Acta Mathematicae Applicatae Sinica, 2017, 40(4): 594-611.

链接本文:

http://123.57.41.99/jweb_yysxxb/CN/或 http://123.57.41.99/jweb_yysxxb/CN/Y2017/V40/I4/594

[1]	Cowell R G, David, A P, Lauritzen S L, Spiegelhalter D J. Probabilistic Networks and Expert Systems. New York:Springer, 1999
[2]	Jensen F V, Nielsen T D. Bayesian Networks and Decision Graphs (second edition). Berlin:Springer Verlag, 2007
[3]	Lauritzen S L, Spiegelhalter D J. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). Journal of the Royal Statistical Society, Series B, 1988, 50:157-224
[4]	Jensen F V, Lauritzen S L, Olesen K G. Bayesian updating in causal probabilistic networks by local computation. Computational Statistics Quarterly, 1990, 4:269-282
[5]	Zhang N L, Poole D. Exploiting causal independence in Bayesian network inference. Journal of Artificial Intelligence Research, 1996, 5:301-328
[6]	Jordan M I. Graphical Models. Statistical Science, 2004, 19:140-155
[7]	Wainwright M J, Jordan M I. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 20081:1-305
[8]	Gilks W, Thomas A, Spiegelhalter D. A language and program for complex Bayesian modelling. The Statistician, 1994, 43:169-177
[9]	Wen W X. Optimal decomposition of belief networks. Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, 1991, 209-224
[10]	Kjærulff U. Optimal decomposition of probabilistic networks by simulated annealing. Statistics and Computing, 1992, 2:7-17
[11]	Larrañaga P, Kuijpers, C M H, Poza M, Murga R. Decomposing Bayesian networks:Triangulation of the moral graph with genetic algorithms. Statistic and Computing, 1997, 7:19-34
[12]	Gámez J A, Puerta J. Searching for the best elimination sequence in Bayesian networks by using Ant Colony based optimization. Pattern Recognition Letters, 2002, 23:261-277
[13]	Cano A, Moral S. Heuristic algorithms for the triangulation of graphs. Advances in Intelligent Computing, 1995, 98-107
[14]	Kjærulff U. Triangulation of graphs-algorithms giving small total state space. Technical Report 90-09, Department of Mathematics and Computer Science, Strandvejen, DK 9000 Aalborg, Denmark, 1990
[15]	Olesen K, Madsen A. Maximal prime subgraph decomposition of Bayesian networks. IEEE Transactions on Systems, Man, and Cybernetics, B, 2002, 32:21-31
[16]	Flores M J, Gámez J A. Triangulation of Bayesian networks by retriangulation. International Journal of Intelligent Systems, 2003, 18:153-164
[17]	Flores M J, Gámez J A. A review on distinct methods and approaches to perform triangulation for Bayesian networks. Studies in Fuzziness and Soft Computing, 2007, 213:127-152
[18]	Prim R C. Shortest connection networks and some generalizations. Bell System Technical Journal, 1957, 36:1389-1401
[19]	Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 1956, 7:48-50
[20]	Blair J R S, Peyton B W. An introduction to chordal graphs and clique trees. Graph Theory and Sparse Matrix Computation, IMA Volumes in Mathematics and its Applications 1993, 56:1-30
[21]	Leimer H G. Optimal decomposition by cliques separators. Discrete Mathematics, 1993, 113:99-123
[22]	Wang X F, Guo J H. Junction trees of general graphs. Frontiers of Mathematics in China, 2008, 3:399-413
[23]	Rose D J, Tarjan R E, Lueker G S. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 1976, 5:266-283
[24]	Xu P F, Guo J H. A new algorithm for decomposition of graphical models. Acta Mathematicae Applicatae Sinica, English, 2012, 3:571-582
[25]	Bodlaender H L, Koster A M C A, Eijkhof F v d, Gaag L C v d. Pre-processing for triangulation of probabilistic networks. Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, 2001, pp. 32-39
[26]	Eijkhof F v d, Bodlaender H L, Koster A M C A. Safe reduction rules for weighted treewidth. Proceedings of the Twenty-eighth International Workshop on Graph Theoretic Concepts in Computer Science, 2002, 176-185

[1]	蔡晓丽, 唐应辉. *温储备失效和单重休假Min(N,V)-策略的M/G/1可修排队系统*[J]. 应用数学学报, 2017, 40(5): 702-726.
[2]	王长远, 曹海涛. 完全图的最大(最小)几乎可分解的(4,2)-圈填充(覆盖)[J]. 应用数学学报, 2015, 38(1): 183-192.
[3]	唐应辉, 吴文青, 刘云颇. *基于单重休假的Min(N,V)策略M/G/1排队系统分析*[J]. 应用数学学报, 2014, 37(6): 976-996.
[4]	李向利, 刘红卫. 求解非负矩阵分解的修正非单调投影梯度法[J]. 应用数学学报, 2014, 37(6): 1068-1076.
[5]	陈亚军, 杜其奎. 无穷凹角区域各向异性问题的非重叠型区域分解算法[J]. 应用数学学报(英文版), 2014, 37(5): 912-925.
[6]	张艳芳. 完全二部图的K_3,3-分解的大集[J]. 应用数学学报(英文版), 2013, 36(6): 1072-1079.
[7]	陈亚军, 杜其奎. 无穷凹角区域各向异性问题的重叠型区域分解算法[J]. 应用数学学报(英文版), 2012, (6): 1030-1043.
[8]	何世峰, Sotiris K. Ntouyas, 任永. 一类具有无穷时滞中立型非稠定脉冲随机泛函微分方程积分解的存在性[J]. 应用数学学报(英文版), 2012, (4): 703-718.
[9]	张宏波, 史定华. 休假时间服从T-SPH分布的M/M/1多重休假排队[J]. 应用数学学报(英文版), 2010, 33(1): 181-189.
[10]	梁志和. 完全图循环分解成2-正则图[J]. 应用数学学报(英文版), 2008, 31(6): 1137-1141.
[11]	李珍珠. 线性流形上矩阵方程$AXA^{T}=B$的极小Frobenius范数对称正交对称解[J]. 应用数学学报(英文版), 2006, 29(2): 276-281.
[12]	陈小山、黎稳. 关于近似广义极因子的误差界[J]. 应用数学学报(英文版), 2006, 29(2): 270-270=275.
[13]	覃红. 混均匀设计的构造[J]. 应用数学学报(英文版), 2005, 28(4): 704-712.
[14]	庞善起. 一类正交投影矩阵及其相关正交表[J]. 应用数学学报(英文版), 2005, 28(4): 668-674.
[15]	Zheng De DAI, Lin YANG, Jian HUANG. 非扰动耗散Hamiltonian振幅波方程的整体吸引子[J]. 应用数学学报(英文版), 2004, 27(4): 577-592.

PDF全文下载地址:

http://123.57.41.99/jweb_yysxxb/CN/article/downloadArticleFile.do?attachType=PDF&id=14350