ハイパーグラフベースのスペクトルクラスタリングによる複雑なネットワークのアラインメントと統合

複雑なネットワークには、モデル化されたシステムの動的かつ機能的な組織を反映した豊富なマルチスケール構造があります。多くの場合、複数のネットワークを同時に分析し、複数のタイプの相互作用でシステムをモデル化するか、単純なペアワイズ相互作用を超えてシステムをモデル化する必要がありますが、現在、これらの問題に対処するための理論的および計算方法が不足しています。ここでは、ハイパーグラフ表現を使用して、このようなシステムでクラスタリングとコミュニティ検出のフレームワークを紹介します。私たちの主な結果は、指示されたハイパーグラフのためのスペクトルクラスタリングアルゴリズムを導出するペロンフロベニウス定理の一般化です。私たちのアプローチを、複数の種間のタンパク質間相互作用ネットワークの局所的およびグローバルな整合、民族間の三者コミュニティ検出、および指向性ネットワークの重複する調節経路のクラスターの検出のためのアプリケーションで説明します。

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.