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

Tom Michoel and Bruno Nachtergaele

Phys. Rev. E 86, 056111 – Published 26 November 2012

Abstract

Complex networks possess a rich, multiscale 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.

Received 16 May 2012

DOI:https://doi.org/10.1103/PhysRevE.86.056111

Authors & Affiliations

Tom Michoel^*

Freiburg Institute for Advanced Studies (FRIAS), University of Freiburg, Albertstrasse 19, D-79104 Freiburg, Germany and The Roslin Institute, The University of Edinburgh, Easter Bush, Midlothian, EH25 9RG, Scotland, United Kingdom

Bruno Nachtergaele^†

Department of Mathematics, University of California Davis, One Shields Avenue, Davis, California 95616-8366, USA

^*tom.michoel@roslin.ed.ac.uk
^†bxn@math.ucdavis.edu

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 86, Iss. 5 — November 2012

Reuse & Permissions

Access Options

Article Available via CHORUS

Download Accepted Manuscript

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
(a) Example of a randomly generated geometric graph with 100 vertices and radius $r^{2} = 0.02$ , showing the largest connected component with the six highest-scoring edge clusters indicated by filled nodes. (b) Dominant eigenvector profiles for the six highest-scoring edge clusters. (c) Edge-to-node ratio scores (left blue bars) and theoretical upper bound (right red bars) for all 25 edge clusters. (d) Cluster size as the fraction $Φ$ of total number of network nodes for the highest-scoring triangle-based cluster in random geometric graphs with $N =$ 200, 400, 600, 800, and 1000 nodes and constant edge density ( $ρ = 4$ ) as a function of $p$ . Each data point is an average over 10 random networks. The inset shows the absolute mean cluster size and standard deviation over 10 random networks as a function of $N$ for $p = 1$ .Reuse & Permissions
Figure 2
Phase diagrams of $s_{p} (α_{1}, α_{2})$ for $p = 1, 1.65, 1.95$ , and 5 (left to right, top to bottom). More yellow (lighter gray) indicates higher values of $s_{p}$ ; the thin lines are contours of constant $s_{p}$ , while the thick line indicates a possible boundary of admissible states. Colors (gray scale levels) are relative to the minimum and maximum in each panel and not comparable between panels.Reuse & Permissions
Figure 3
(a) A (directed) hyperedge in the yeast-human protein interaction network alignment hypergraph is an interolog: a pair of interacting yeast (Y) proteins and a pair of interacting human (H) proteins connected by orthology relations (dashed lines). (b) Examples of aligned protein complexes (cluster no. 19 left, no. 1 right). (c) Example of a functional network alignment (cluster no. 48). In all panels, yeast proteins are white and human proteins are gray; protein interactions are solid lines and orthology relations are dashed lines.Reuse & Permissions
Figure 4
(a) CiteULike hyperedge, which represents one instance of a user (hexagonal node) who has annotated an article (circular node) with a certain tag (rectangular node). (b) Example of two tripartite communities where the same set of users (top) has annotated two sets of articles (middle) with two sets of tags (bottom). Only the two central articles and one central tag (“pattern recognition”) overlap between the two clusters. User-tag edges have been omitted for clarity. (c) Coarse-grained view of the CiteULike hypergraph using the 100 highest-scoring hyperedge clusters. Each node represents a cluster (with node size proportional to the number of hyperedges in the cluster) and edges represent significant overlap between clusters (overlap score $> 0.5$ ; edge size proportional to overlap score). Solid edges: user overlap; dashed edges: tag overlap; wavy edges: article overlap.Reuse & Permissions
Figure 5
Examples of high-scoring combinatorial [(a), cluster no. 6] and hierarchical [(b), cluster no. 1] path clusters in the yeast transcriptional regulatory network. Red (dark gray) rectangular nodes: knocked-out transcription factors (TFs); yellow (light gray) circular nodes: genes differentially expressed upon knock out of the TFs; white diamond-shaped nodes: all other TFs. Node size is proportional to out-degree and edge width to edge “betweenness” (defined for the purposes of this figure as the number of shortest paths between all pairs of cluster nodes passing through a given edge).Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics