2015/04/23 by Héctor Zenil, Narsis A. Kiani, Zenil, Hector +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Bioinformatics and Genomic Networks #Computational Drug Discovery Methods #Gene Regulatory Network Analysis
paper · pdf · doi:10.48550/arxiv.1504.06249
To cope with the complexity of large networks, a number of dimensionality\nreduction techniques for graphs have been developed. However, the extent to\nwhich information is lost or preserved when these techniques are employed has\nnot yet been clear. Here we develop a framework, based on algorithmic\ninformation theory, to quantify the extent to which information is preserved\nwhen network motif analysis, graph spectra and spectral sparsification methods\nare applied to over twenty different biological and artificial networks. We\nfind that the spectral sparsification is highly sensitive to high number of\nedge deletion, leading to significant inconsistencies, and that graph spectral\nmethods are the most irregular, capturing algebraic information in a condensed\nfashion but largely losing most of the information content of the original\nnetworks. However, the approach shows that network motif analysis excels at\npreserving the relative algorithmic information content of a network, hence\nvalidating and generalizing the remarkable fact that despite their inherent\ncombinatorial possibilities, local regularities preserve information to such an\nextent that essential properties are fully recoverable across different\nnetworks to determine their family group to which they belong to (eg genetic vs\nsocial network). Our algorithmic information methodology thus provides a\nrigorous framework enabling a fundamental assessment and comparison between\ndifferent data dimensionality reduction methods thereby facilitating the\nidentification and evaluation of the capabilities of old and new methods.\n