Causal network discovery by iterative conditioning: Comparison of algorithms

Estimating causal interactions in complex dynamical systems is an important problem encountered in many fields of current science. While a theoretical solution for detecting the causal interactions has been previously formulated in the framework of prediction improvement, it generally requires the c...

Full description

Saved in:
Bibliographic Details
Published in:Chaos (Woodbury, N.Y.) N.Y.), 2020-01, Vol.30 (1), p.013117-013117
Main Authors: Kořenek, Jakub, Hlinka, Jaroslav
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Computer simulation
Iterative methods
Polynomials
Simulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Estimating causal interactions in complex dynamical systems is an important problem encountered in many fields of current science. While a theoretical solution for detecting the causal interactions has been previously formulated in the framework of prediction improvement, it generally requires the computation of high-dimensional information functionals—a situation invoking the curse of dimensionality with increasing network size. Recently, several methods have been proposed to alleviate this problem, based on iterative procedures for the assessment of conditional (in)dependences. In the current work, we bring a comparison of several such prominent approaches. This is done both by theoretical comparison of the algorithms using a formulation in a common framework and by numerical simulations including realistic complex coupling patterns. The theoretical analysis highlights the key similarities and differences between the algorithms, hinting on their comparative strengths and weaknesses. The method assumptions and specific properties such as false positive control and order-dependence are discussed. Numerical simulations suggest that while the accuracy of most of the algorithms is almost indistinguishable, there are substantial differences in their computational demands, ranging theoretically from polynomial to exponential complexity and leading to substantial differences in computation time in realistic scenarios depending on the density and size of networks. Based on the analysis of the algorithms and numerical simulations, we propose a hybrid approach providing competitive accuracy with improved computational efficiency.
ISSN:1054-1500
1089-7682
DOI:10.1063/1.5115267