minimal_d_separator#
- minimal_d_separator(G, u, v)[source]#
Compute a minimal d-separating set between ‘u’ and ‘v’.
A d-separating set in a DAG is a set of nodes that blocks all paths between the two nodes, ‘u’ and ‘v’. This function constructs a d-separating set that is “minimal”, meaning it is the smallest d-separating set for ‘u’ and ‘v’. This is not necessarily unique. For more details, see Notes.
- Parameters:
- Ggraph
A networkx DAG.
- unode
A node in the graph, G.
- vnode
A node in the graph, G.
- Raises:
- NetworkXError
Raises a
NetworkXErrorif the input graph is not a DAG.- NodeNotFound
If any of the input nodes are not found in the graph, a
NodeNotFoundexception is raised.
Notes
This function only finds
aminimal d-separator. It does not guarantee uniqueness, since in a DAG there may be more than one minimal d-separator between two nodes. Moreover, this only checks for minimal separators between two nodes, not two sets. Finding minimal d-separators between two sets of nodes is not supported.Uses the algorithm presented in [1]. The complexity of the algorithm is \(O(|E_{An}^m|)\), where \(|E_{An}^m|\) stands for the number of edges in the moralized graph of the sub-graph consisting of only the ancestors of ‘u’ and ‘v’. For full details, see [1].
The algorithm works by constructing the moral graph consisting of just the ancestors of
uandv. Then it constructs a candidate for a separating setZ'from the predecessors ofuandv. Then BFS is run starting fromuand marking nodes found fromZ'and calling those nodesZ''. Then BFS is run again starting fromvand marking nodes if they are present inZ''. Those marked nodes are the returned minimal d-separating set.https://en.wikipedia.org/wiki/Bayesian_network#d-separation
References