Statistical and Machine Learning Approaches for Network Analysis

1.5 Partitioning Biological Networks

Often a reconstructed network is too broad of a representation for a specific biological process. The partitioning of biological networks allows for the careful analysis of hypothesized biological functional units. Users may choose to partition high fidelity biological networks obtainable from a variety of sources such as the Kyoto Encyclopedia of Genes and Genomes (KEGG) database [75]. There is no universal definition for partitions, clusters, and especially communities. However, in this chapter we define a partition as a subnetwork (subgraph) of the given network (graph) such that (1) the internal connections of the partition from node to node are strong and (2) the external connections between other partitions are weak.

There are two major classes of partitioning algorithms called graph clustering algorithms and community detection algorithms [22]. Graph clustering algorithms originated from computer science and other closely related fields. Community detection algorithms have their origin in sociology, which now encompass applications in applied mathematics, physics, and biology.

For graph clustering algorithms, the number of clusters is a user-specified parameter. A graph clustering algorithm must always return the specified number of clusters regardless of whether the clusters are structurally meaningful in the underlying graph. These algorithms were developed for specific applications, such as placing the parts of an electronic circuit ...