Alignment and integration of complex networks by hypergraph-based spectral clustering

Abstract

Complex networks possess a rich, multi-scale structure reflecting the dynamical and functional organization of the systems they model. Often there is a need to analyze multiple networks simultaneously, to model a system by more than one type of interaction or to go beyond simple pairwise interactions, but currently there is a lack of theoretical and computational methods to address these problems. Here we introduce a framework for clustering and community detection in such systems using hypergraph representations. Our main result is a generalization of the Perron-Frobenius theorem from which we derive spectral clustering algorithms for directed and undirected hypergraphs. We illustrate our approach with applications for local and global alignment of protein-protein interaction networks between multiple species, for tripartite community detection in folksonomies, and for detecting clusters of overlapping regulatory pathways in directed networks.

16 pages, 5 figures; revised version with minor corrections and figures printed in two-column format for better readability; algorithm implementation and supplementary information available at Google code at http://schype.googlecode.com

References in corpus (20)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Link communities reveal multiscale complexity in networks
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Line Graphs, Link Partitions and Overlapping Communities
• Module identification in bipartite and directed networks
• Perron-Frobenius theorem for nonnegative multilinear forms and extensions
• Random hypergraphs and their applications
• Cross-species analysis of biological networks by Bayesian alignment
• Directed network modules
• Hypergraph topological quantities for tagged social networks
• Population stratification using a statistical model on hypergraphs
• Enrichment and aggregation of topological motifs are independent organizational principles of integrated interaction networks

Cited by in corpus (21)

• Multilayer Networks
• The structure and dynamics of multilayer networks
• Eigenvector centrality of nodes in multiplex networks
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Integrative multi-omics module network inference with Lemon-Tree
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Complex networks with complex weights
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Cycle and flow trusses in directed networks
• Adjacency and Tensor Representation in General Hypergraphs Part 1: e-adjacency Tensor Uniformisation Using Homogeneous Polynomials
• Testing Community Structures for Hypergraphs
• Learning differential module networks across multiple experimental conditions
• Information Extraction from Larger Multi-layer Social Networks
• Detection of regulator genes and eQTLs in gene networks
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Network Composition from Multi-layer Data
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Computing the $p$-Spectral Radii of Uniform Hypergraphs with Applications
• Computing Eigenvalues of Large Scale Sparse Tensors Arising from a Hypergraph