Search

We formulate a discrete optimization problem that leads to a simple and informative derivation of a widely used class of spectral clustering algorithms. Regarding the algorithms as attempting to bi-partition a weighted graph with N vertices, our derivation indicates that they are inherently tuned to tolerate all partitions into two non-empty sets, independently of the cardinality of the two sets. This approach also helps to explain the difference in behaviour observed between methods based on the unnormalized and normalized graph Laplacian. We also give a direct explanation of why Laplacian eigenvectors beyond the Fiedler vector may contain fine-detail information of relevance to clustering. We show numerical results on synthetic data to support the analysis. Further, we provide examples where normalized and unnormalized spectral clustering is applied to microarray data—here the graph summarizes similarity of gene activity across different tissue samples, and accurate clustering of samples is a key task in bioinformatics.

Drug discovery is moving away from the single target-based approach towards harnessing the potential of polypharmacological agents that modulate the activity of multiple nodes in the complex networks of deregulations underlying disease phenotypes. Computational network pharmacology methods that use systems-level drug-response phenotypes, such as those originating from genome-wide transcriptomic profiles, have proved particularly effective for elucidating the mechanisms of action of multitargeted compounds. Here, we show, via the case study of the natural product pinosylvin, how the combination of two complementary network-based methods can provide novel, unexpected mechanistic insights. This case study also illustrates that elucidating the mechanism of action of multitargeted natural products through transcriptional response-based approaches is a challenging endeavor, often requiring multiple computational-experimental iterations.