Network Enhancement: a general method to denoise weighted biological networks

Project website: http://snap.stanford.edu/ne.

Overview

Networks are abundant in many areas of biology. These networks often entail non-trivial
topological features and patterns critical to understanding interactions within the
natural system. However, networks observed in real-world are typically noisy. The presence
of high levels of noise can hamper discovery of structures and dynamics present in the network.

We propose Network Enhancement (NE), a novel method for improving the
signal-to-noise ratio of a symmetric networks and thereby facilitating the downstream network
analysis. NE leverages the transitive edges of a network by exploiting local structures to
strengthen the signal within clusters and weaken the signal between clusters. At the same time
NE also alleviates the corrupted links in the network by imposing a normalization that removes
weak edges by enforcing sparsity. NE is supported by theoretical justifications for its
convergence and performance in improving community detection outcomes.

The method provides theoretical guarantees as well as excellent empirical performance on
many biological problems. The approach can be incorporated into any weighted network analysis
pipeline and can lead to improved downstream analysis.

Running NE in Matlab

At current stage, we provide examples showing how to apply NE to two problems in biology, which
are discussed in the manuscript. All datasets required to run the examples are included in this
repository.

1. The first example is about fine-grained species identification. Run the example as:

    run_butterfly_network.m 

This script reports retrieval accuracy values and generates a retrieval curve for the task of
butterfly species identification, as reported in the manuscript.

2. The second example is about denoising Hi-C interaction networks. We provide sample data for
   Chrom 16 with two measurement resolutions, 1kb and 5kb Hi-C data. Run the example as:

    run_hiC_network.m

In order to use community detection with the Hi-C interaction networks, you need to
compile two C++ files. Instructions are provided in script run_hiC_network.m.