mcSearch: Orders variables using Maximum Cardinality search

In ralmond/CPTtools: Tools for Creating Conditional Probability Tables

Orders variables using Maximum Cardinality search

Description

Takes a graph described by an incidence matrix, and creates an ordering of the nodes using maximum cardinality search (Tarjan and Yannakakis, 1984). A primary application of this method is to chose an ordering of nodes in an undirected graph to make a corresponding directed graph.

Usage

mcSearch(sm, start = colnames(sm)[1])

Arguments

sm	A logical matrix whose rows and columns correspond to nodes (variables) and a true value indicates an edge between the variables.
start	The name of the first element.

Details

The sm argument should be an incidence matrix for a graph, with row and column names set to the names of the nodes/variables.

The function returns an ordering of the nodes where each node is chosen so that it has a maximum number of neighbors among those nodes higher in the order.

Ties are broken by chosing the first node in the graph (using the order of the columns) matching the criteria. One special case is the first node which is always an arbitrary choice. The start argument can be used to force a particular selection.

Value

A vector of lenght equal to the number of rows whose values correspond to the order of the variable in the final order.

Note

If the graph is triangulated, then the ordering produced by mcSearch should be perfect — for each node in the order, the set of neighbors of that node which preceed it in the ordering is completely connected. Perfect node orderings are useful in going from undirected to directed graphical representations. If we take an undirected graph and a perfect ordering, a define as the parents of an node all of its neighbors which are previous in the order and define as its children all of the nodes which are later in the order, then when converting the graph back to the undirected form no additional “moralization” edges will be required. Thus, this function can be used to generate orders for buildParentList.

Graphical models generally exist only over triangulated graphs. Therefore, and incidence matrix which has been produced through the use of the structMatrix function should alway work. Tarjan and Yannakakis (1984) prove that the maximum cardinality search always produces a perfect ordering when the graph is triangulated.

When the graph is not triangulated, the maximum cardinality search algorithm can be used to generate “fill-ins” to triangulate the graph. Lauritzen and Spiegelhalter (1988) note this use. While maximum cardinality search will produce an ordering quickly, the ordering itself has now particular optimality properties as far as the triangulated graph which it creates (Almond, 1995).

Author(s)

Russell Almond

References

Almond, R.G. (1995). Graphical Belief Modeling. Chapman and Hall.

Lauritzen, S.L. and D.J. Spiegelhalter (1988). Local Computation with Probabilities on Graphical Structures and their Application to Expert Systems (with discussion). Journal of the Royal Statistical Society,Series B, 50, 205-247.

Tarjan, R.E. and M. Yannakakis (1984). Simple Linear-Time Algorithms to test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. Siam J. Comput. 13, 566-579.

See Also

structMatrix, buildParentList

Examples

data(MathGrades)
MG.struct <- structMatrix(MathGrades$var)

ord <- mcSearch(MG.struct)   # Arbitrary start
orda <- mcSearch(MG.struct, "Algebra") # Put algebra first.

names(sort(orda)) # names of the variables in the chosen order.

# Sort rows and columns of structure matrix by MC order
MG.struct[order(orda), order(orda)]

ralmond/CPTtools documentation built on Dec. 27, 2024, 7:15 a.m.