Reconstruction of Causal Networks by Set Covering

Details Reconstruction of Causal Networks by Set Covering Reconstruction of Causal Networks by Set Covering

2010-06-04

arxiv.org/abs/1006.0849v1

Computer Science

Data Structures and Algorithms

Under consideration for the ECML PKDD 2010 conference

Scientific paper

We present a method for the reconstruction of networks, based on the order of nodes visited by a stochastic branching process. Our algorithm reconstructs a network of minimal size that ensures consistency with the data. Crucially, we show that global consistency with the data can be achieved through purely local considerations, inferring the neighbourhood of each node in turn. The optimisation problem solved for each individual node can be reduced to a Set Covering Problem, which is known to be NP-hard but can be approximated well in practice. We then extend our approach to account for noisy data, based on the Minimum Description Length principle. We demonstrate our algorithms on synthetic data, generated by an SIR-like epidemiological model.

Affiliated with

Also associated with

No associations

Rating

Reconstruction of Causal Networks by Set Covering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstruction of Causal Networks by Set Covering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction of Causal Networks by Set Covering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-722790