Max flow algorithm based Cyber Community Extraction

サイバーコミュニティ（以降，単にコミュニティと呼ぶ）とは，話題が共通するウェブページの集合を意味し，ウェブ検索やウェブの成長分析， ウェブからのトレンド発見など幅広いウェブ技術への応用が期待できる概念として近年非常に重要視されている．

ウェブページとその間に張られたハイパーリンクをそれぞれノード，エッジと見なせば，ウェブは巨大な有向グラフ（ウェブグラフと呼ばれる）である．コミュニティ特有のグラフ構造を解析することにより，コミュニティを効率よく発見するための種々の手法が提案されてきた．本研究では，Max-Flowアルゴリズムを利用した手法とそれにより得られたコミュニティ（Max-Flowコミュニティ）に着目している．

Max-Flowコミュニティとは，「コミュニティの外のページへの（又は，からの）リンクよりもコミュニティ内のページ同士のリンクを多くもつ」という条件を満たすウェブページの集合である．完全2部グラフに基づくコミュニティと比べて，コミュニティのグラフ構造としての条件が緩和されており，完全2部グラフを形成し得ないような疎に連結しているページ群であっても，コミュニティのメンバーと成りうるようになっている．

本研究では，これまでに，Max-FlowコミュニティとHITS系コミュニティを比較しMax-Flowコミュニティの特徴を分析した．また，既存のMax-Flowコミュニティ抽出手法の問題点を明示し，新たな抽出手法を提案した．今後は，Max-Flowコミュニティの時系列的変化を分析し，ウェブ空間の成長過程に伴うグラフ構造変化の特徴付けを目指す．

(今藤 紀子)