findEd: Finds add-eligible edges

In gRapHD: Efficient Selection of Undirected Graphical Models for High-Dimensional Datasets

Description

Finds the edges that can be added to a (strongly) triangulated graph such that the result is also (strongly) triangulated.

Usage

findEd(edges,p,previous=NULL,numCat,from=0,exact=FALSE,join=FALSE)

Arguments

edges	matrix with 2 columns, each row representing one edge, and each column one of the vertices in the edge.
p	number of vertices.
previous	result of a previous run of findEd.
numCat	vector with number of levels for each variable (0 if continuous).
from	initial vertex to be used in MCS.
exact	logical indicating if the exact algorithm for finding add-eligible edges is to be used. Default is FALSE.
join	logical indicating if the disjoint components can be joined. Default is FALSE.

Details

Returns all add-eligible edges for a given triangulated graph, that is, edges that preserve the triangulated property when added. In the case of a mixed graph, only edges that do not result in forbidden paths are returned.
The argument from can be used to indicate the initial vertex used in the MCS algorithm. If 0, the first vertex is used.
If exact is FALSE, the edge list may contain a few edges that are not add-eligible. Further tests (for example mcs) will be required before adding edges. Otherwise, the list contains only edges that preserve triangularity. That is, each edge that may be added to the graph such that the resulting graph is triangulated.
For graphs with both discrete and continuous vertices, the graph should be triangulated and contain no forbidden paths, and the edges that may be added preserving both properties are returned. See Lauritzen (1996), p. 11-13.

Value

A list with:

edges.to.test	matrix (k by 5), with columns: 1 - first vertex of the tested edge 2 - second vertex (the two values are ordered) 3 - index for the separator in S 4 - change in the LR by adding this edge 5 - number of parameters for that edge
S	list with the separators.

Author(s)

Gabriel Coelho Goncalves de Abreu ([e-mail])
Rodrigo Labouriau ([e-mail])
David Edwards ([e-mail])

References

Lauritzen, S.L. (1996) Graphical Models, Oxford University Press.

Examples

edges <- matrix(c(1,2,2,3,2,4,2,5,2,6,3,4,4,5,5,6),ncol=2,byrow=TRUE)
addEligible <- findEd(edges=edges,p=6,previous=NULL,numCat=rep(0,6),
                      from=1)
#    > str(addEligible)
#    List of 2
#     $ edges: num [1:7, 1:5] 1 1 3 1 4 3 1 3 4 5 ...
#     $ S    :List of 6
#      ..$ : int 2
#      ..$ : int [1:2] 2 4
#      ..$ : int 2
#      ..$ : int [1:2] 2 5
#      ..$ : int 2
#      ..$ : int 2
#    > addEligible$edges
#         [,1] [,2] [,3] [,4] [,5]
#    [1,]    1    3    1    0    0
#    [2,]    1    4    1    0    0
#    [3,]    3    5    2    0    0
#    [4,]    1    5    3    0    0
#    [5,]    4    6    4    0    0
#    [6,]    3    6    5    0    0
#    [7,]    1    6    6    0    0

# the columns in addEligible$edges
#    1: first vertex in the edge
#    2: second vertex in the edge
#    3: index os the separator in addEligible$S
#    4: change in the LRT for the edge (used if previous != NULL)
#    5: number of parameters for the edge (used if previous != NULL)

# note that the edge 3-6 (row 6) is actually a "false positive". 
# If it's used from=3,4,5, or 6, this does not happen.

gRapHD documentation built on Feb. 9, 2018, 6:05 a.m.