Network biology approaches have over the last decade proven to be very useful for the integration and generation of functional hypothesis by providing a context for specific molecular components and processes. Recent experimental and computational techniques yield networksof increased size and sophistication. The study of these complex cellular networks is emerging as a new challenge in biology. A number of dimensionality reduction techniques for graphs have been developed to cope with complexity of networks . However, it is yet not clear to what extent information is lost or preserved when these techniques are applied to reduce the complexity of large networks . Here we therefore develop a rigorous framework, based on algorithmic information theory, to quantify the capability to preserve information when network motif analysis, graph spectra and sparsification methods respectively, are applied to over twenty different well-established networks. We find that the sparsification method is highly sensitive to deletion of edges leading to significant inconsistencies with respect to the loss of information and that graph spectral methods were the most irregular measure only capturing algebraic information in a condensed fashion but in that process largely lost the information content of the original networks.  Our algorithmic information methodology therefore provides a rigorous framework enabling  fundamental assessment and comparison between different methods for reducing the complexity of networks while preserving key structures in the networks thereby facilitating the identification of such core processes .
To cope with the complexity of large networks, a number of dimensionality reduction techniques for graphs have been developed . However, the extent to which information is lost or preserved when these techniques are employed has not yet been clear . Here we develop a framework, based on algorithmic information theory, to quantify the extent to which information is preserved when network motif analysis, graph spectra and spectral sparsification methods are applied to over twenty different biological and artificial networks. We find that the spectral sparsification is highly sensitive to high number of edge deletion, leading to significant inconsistencies , and that graph spectral methods are the most irregular , capturing algebraic information in a condensed fashion but largely losing most of the information content of the original networks. However, the approach shows that network motif analysis excels at preserving the relative algorithmic information content of a network, hence validating and generalizing the remarkable fact that despite their inherent combinatorial possibilities, local regularities preserve information to such an extent that essential properties are fully recoverable across different networks to determine their family group to which they belong to (eg genetic vs social network). Our algorithmic information methodology thus provides a rigorous framework enabling a fundamental assessment and comparison between different data dimensionality reduction methods thereby facilitating the identification and evaluation of the capabilities of old and new methods .
R
Network biology approaches have over the last decade proven to be very useful for the integration and generation of functional hypothesis by providing a context for specific molecular components and processes. Recent experimental and computational techniques yield networksof increased size and sophistication. The study of these complex cellular networks is emerging as a new challenge in biology. A
To cope with the complexity of large networks, a
D
to cope with complexity of networks
R
it is yet not clear to what extent
the extent to which
R
applied to reduce the complexity of large networks
employed has not yet been clear
R
therefore develop a rigorous
develop a
R
capability to preserve information
extent to which information is preserved
R
sparsification methods respectively,
spectral sparsification methods
R
well-established
biological and artificial
R
sparsification method
spectral sparsification
R
deletion of edges
high number of edge deletion,
R
with respect to the loss of information
,
R
were
are
R
measure only
,
R
in that process largely lost
largely losing most of
A
However, the approach shows that network motif analysis excels at preserving the relative algorithmic information content of a network, hence validating and generalizing the remarkable fact that despite their inherent combinatorial possibilities, local regularities preserve information to such an extent that essential properties are fully recoverable across different networks to determine their family group to which they belong to (eg genetic vs social network).
R
therefore
thus
A
a
R
methods for reducing the complexity of networks while preserving key structures in the networks
data dimensionality reduction methods
R
of such core processes
and evaluation of the capabilities of old and new methods