Name
Title | ||
|---|---|---|
Thinning A Triangulation Of A Bayesian Network Or Undirected Graph To Create A Minimal Triangulation |
Abstract | ||
|---|---|---|
In one procedure for finding the maximal prime decomposition of a Bayesian network or undirected graphical model, the first step is to create a minimal triangulation of the network, and a common and straightforward way to do this is to create a triangulation that is not necessarily minimal and then thin this triangulation by removing excess edges. We show that the algorithm for thinning proposed in several previous publications is incorrect. A different version of this algorithm is available in the R package gRbase, but its correctness has not previously been proved. We prove that this version is correct and provide a simpler version, also with a proof. We compare the speed of the two corrected algorithms in three ways and find that asymptotically their speeds are the same, neither algorithm is consistently faster than the other, and in a computer experiment the algorithm used by gRbase is faster when the original graph is large, dense, and undirected, but usually slightly slower when it is directed. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1142/S0218488517500143 | INTERNATIONAL JOURNAL OF UNCERTAINTY FUZZINESS AND KNOWLEDGE-BASED SYSTEMS |
Keywords | Field | DocType |
Bayesian network, graphical model, minimal triangulation, maximal prime decompositio | Discrete mathematics,Bowyer–Watson algorithm,Minimum-weight triangulation,Correctness,Triangulation (social science),Bayesian network,Graphical model,Mathematics,Delaunay triangulation,Point set triangulation | Journal |
Volume | Issue | ISSN |
25 | 3 | 0218-4885 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edmund Jones | 1 | 0 | 0.34 |
| Vanessa Didelez | 2 | 16 | 4.03 |