Resolving the Structure of Interactions with Hierarchical Agglomerative Clustering

• Activity Number: 223
• Type: Topic Contributed
• Date/Time: Monday, August 1, 2011 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Yongjin Park*+
• Companies: The Johns Hopkins University
• Keywords: biological networks ; model comparison ; clustering ; link prediction ; systems biology

Abstract

Network clustering is a valuable approach for summarizing the structure in large networks, for predicting unobserved interactions, and for predicting functional annotations. A new algorithm, Hierarchical Agglomerative Clustering (HAC), is developed for fast clustering of heterogeneous interaction networks. This algorithm uses maximum likelihood to drive the inference of a hierarchical stochastic block model for network structure. Bayesian model selection provides a principled method both for identifying the major top-level groups and for collapsing the fine-structure of the bottom-level groups within a network. Model scores are additive over independent edge types, providing a direct route for simultaneous analysis of multiple biological interactions. In addition to inferring network structure, this algorithm generates link predictions that with cross-validation provide a quantitative assessment of performance for real-world examples. When applied to genome-scale data sets representing several organisms and interaction types, HAC provides the overall best performance in link prediction when compared with other clustering methods and with model-free graph diffusion kernels.