著者

高木 允 田村 慶一 森 康真 北上 始

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告情報学基礎(FI)

巻号頁・発行日

vol.2007, no.54, pp.39-45, 2007-05-31

---

本研究では、Newman らの提案するネットワーク構造解析に基づくクリスプなクラスタリングアルゴリズムを改良し、ひとつのノードが複数のクラスタに重複してクラスタリングされることを許したグラフのクラスタリング手法を提案する。提案する手法は、一度 Newman らの提案するアルゴリズムを用いてグラフのクラスタリングを行った後、それぞれのクラスタをひとつのノードとした縮約グラフの作成を行う。縮約グラフを再度 Newman らの提案するアルゴリズムを用いてクラスタリングし、重複してクラスタリングされるノードを識別する。重複を許したクラスタリングを行うことで、クリスプなクラスタリングに比べ、柔軟なクラスタリングを行うことができる。ブログのトラックバックデータを用いた評価実験を行い、提案手法の有効性を示すことができた。In this paper, we propose a method of overlapping cluster based on network structure analysis which improves the clustering algorithm proposed by Newman et al. Newman's clustering algorithm is the crisp clustering algorithm. In the proposed technique, first, we cluster the nodes using the Newman's algorithm. Then, we make the contraction graph which is considerd a cluster as a node. In addition, we cluster the created contraction graph by using the Newman's clustering algorithm again and identify the overlapping nodes. Overlapping clustering is more flexible than crisp clustering. The experimental results using the trackback data based on blog represented efficacy of proposed technique.