Topological network alignment uncovers biological function and phylogeny

こちらの論文がゼミで紹介されたのでメモ

提案されている方法：

・事前情報を使わない

・トポロジーの近さでアライメントをやる

・n-node graphlets：ノードの数によって、どのようなグラフパターンがあるか列挙

・トポロジーを考える：トポロジー的に同じノードをオービットと定義する。

・1-node to 5-nodesでオービットは72個

・Graphlet Degree Vecotrを計算(ネットワーク中にオービットがいくつ表れているか数える)

・Signature similarity(各ノードについて、いくつのオービットに対応しているか、ユニークさを計算)

・GRAph Aligner algorithm(GRAAL)：Costを計算。Densityとtopologyを計算。αは0.8位が良いとのこと。

・球を定義していく。中心を決め(cost matrix中でcostが最小となるようなu,vを定める、候補が複数ある場合はrandomで選ぶ)、半径を徐々に拡大してalingmentを行う。

・Alignment後、Edge correctnessを計算。

・Statistical significanceを計算する方法も提示されている。

・論文の最後には他の手法との比較も掲載されている