ネットワークのクラスタリング手法の提案
辻 尚(0551085)
大規模ネットワークの研究は様々な分野で行われている.インターネットや,共同執筆の関係ネットワーク,食物網,病気の感染ネットワークなどがその例として挙げられる.
また,生物学の世界においても,このようなネットワーク構造が多く存在する.代表的なものを挙げると,タンパク質の相互作用ネットワーク,ゲノムネットワーク,退社ネットワークなどがある.これらのネットワークはノードとエッジからなるグラフ構造として解析されることが多い.しかし,大規模であるが故にネットワークの解析は非常に困難である.大規模ネットワークの構造を捉える手法の考案が必要であると考えられる.そこで,この論文では,ネットワーク内のクラスタ構造と呼ばれる領域に注目したネットワーク粗子化手法を提案する.ネットワークにおけるクラスタ構造とは,ネットワーク内で,エッジが密に張られた領域のことを指す.ネットワーク内からクラスタ構造を列挙することをクラスタリングという.クラスタリングのアルゴリズムとして,本研究ではDPClusアルゴリズムとNewmanアルゴリズムに注目した.DPClusアルゴリズムは,エッジが非常に密に張られたクラスタ領域を効率良く抽出することが可能なアルゴリズムである.一方で,Newmanクラスタリングアルゴリズムは,高速にクラスタリングを行うアルゴリズムである.この論文では,これらの2つのアルゴリズムについて,その性能の調査,比較を行い,階層的にクラスタリングを行う手法を提案し,その手法を実装したソフトウェアを紹介する.さらに,Newman法とDPClus法を組み合わせた,クラスタ領域をより効率的に抽出できるメソッドを提案する.