背景

頂点 辺 構成 ，柔軟 表現力 富 構造 ，実体間 関係

性 頂点間 辺 連結性 表現 ． 様々 分野 表現

使 ．例 Web ^繋 Web

[3, 5, 23, 24]，人間同士 友好関係 表現 [16, 29]，論文

共著者 関係[27, 30]， 通信 [2]，生物学的

[15, 34] ^．

頂点 含 多 存在 ．例 ，Web

内容 対応 Web ，電子回路 機能的 対

応 ． ，与 見 問題

問題 呼 ，多 問題

定式化 ．例 分析[29]，画像 [35],

回路設計[9] ．

一部 ， 分子構造 ，明白

的 構造 扱 ， 以外 対象 元々 ，

潜在的 関係性 抽出 作 人工的 扱 ．例 ，画像

間 類似関係 表現 ，関連語抽出 単

語 共起関係 表現 ．従 ，自然 加 ，

潜在的 適切 扱 重要

(a)^元 (^重 ) (b)^{巨視的構造}(^重 )

図4.1: 巨視的構造．元 (左図) ， 色付 (「 」 呼 ) 従 抽出 巨視的構造(右図) 例 示 ．右図 辺 重

，辺 線 太 重 対応 ．

．

問題 広 研究 ，多 存在 ．各

研究 独自 定義 ，多 内 辺 密 張

，他方 間 辺 絶対的 疎 仮定 ．例 ，Girvan 提案

GN [16] ， 同士 少数 辺 繋 仮定

，“edge betweenness” ^{呼 辺 中心性尺度 使 間 繋 辺 特定}

．

仮定 手法 ，特 以外 抽出 対

上手 機能 ．何故 潜在的 関係性 抽出 ，頂点間 関係 定義 依存 ，仮

定 満 多 得 易 ． ， 潜在的

関係 活用 解 ， 間 辺 疎 前提

開発 重要 ．

仮定 代 ，本研究 頂点 ，与

構成 大 表 巨視的構造 呼

導入 (^図4.1)^{． 例 ，}4 ^{巨視的構造 ，元々}

与 色付 求 ．色付 頂点 対応関係 表 ，

「 (view)」 呼 ．詳細 後述 ．

巨視的構造 用 ，HITS

[23] 得 ．HITS ，特定 検索 関連 Web 集合

hub authority 同定 分析 ．文献 [23] ，hub

authority 相互 強化 合 関係「良 hub ^{多 良} authority

張 ，良 authority 多 良 hub 張

」 説明 ．著者 巨視的 関係

場合 考 ．

本論文 ，対象 数 与 時 ，計算

得 巨視的構造 ，与 数 下 理想的 巨視的構造 距離

最小 見 提案

．言 換 ， 問題 最適化問題 解 ．理想

的 巨視的構造 ，m- 問題 対 ，各頂点 自己 m-頂

点 定義 ．

我々 様々 量 変化 人工 生成 ， 対 既存 提案 精度 変化 調査 実験 行 ． 結果，提案

生成 大部分 既存 精度 高 ，既存

特 多 失敗 示 ． ，

実用的 場合 ， 表現 変換 得

対 実験 行 結果， 多 対 提案 既存

高 性能 示 ．

本論文 以下 構成 ．第4.2節 問題 対

既存手法 説明 ， 欠点 指摘 ． ，著者

得 HITS ^{紹介 ．第}4.3^{節 提案手法 詳述 ，第}4.4 節 提案手法 既存手法 比較 実験 結果 示 ．最後 第4.5^{節 結論 述 ．}

4.2 ^関連研究

， 問題 先行研究 説明 ， 共通 仮

定 生 欠点 指摘 ． ，著者 得 HITS

説明 ．

4.2.1 ^先行研究

，階層的 非階層的 2種類 存在 ．前者 反復的 辺 削除， 併合

行 ， 階層 作成 ．他方，非階層的 操作 行 ， 量 計算 行 ．

Girvan Newman 提案 GN [16] 最 有名

手法 1 ． 階層的 ，

集合 階層 構築 ． “edge betweenness”^{尺度 基}

，与 各辺 辺 含 最短 数 評価 ．

複数 構成 ，2 僅

辺 繋 ，異 間 最短 大部分

少数 辺 内 含 考 ．辺 評価 ，最 高 betweenness

辺 削除 手順 繰 返 ，GN 互 分

離 ，最終的 構造 明 ． 全体 手順 以下 通

．1)各辺 betweenness 計算 ，2)最 高 betweenness 辺 削除

，3)残 辺 betweenness 再計算 ，4) 2，3 繰 返 ．

一 知 Stijn van Dongen

提案 Markov Clustering (MCL) [41] ^{， 上 基 非階}

層的 ． 与 隣接行列 求 初期

遷移行列M 始 ，行列 収束 ，反復的 拡張，膨張，刈 込 3 操作 順 行列 対 適用 ．G= (V,E) ^{入力 ，}V,E ^{頂点集合 辺} 集合 ．A |V| × |V| G 隣接行列 ，(v_i,v_j) ∈ E 場合 限 A_{i j} = 1，

以外 場合 A_{i j} = 0 ．M 要素 M_{i j} = A_{i j}/∑_|V|

k=1A_{k j} 定義 遷移

行列 ．拡張操作 M M = M × M ^更新 行 ．膨張操作 M_{i j} = M_{i j}^r/∑_|V|

k=1M_{k j}^r 定義 ． 操作 M 高 確率

低 確率 差 強調 実行 ．膨張操作 最後 ，M 格納 必要 領域 減 ，M ^{要素 確率 十分 小 要素 削除 刈 込 操作} 行 ．以上 反復 M 収束 後，M 遷移 互 繋 頂点

集合 作 ，M 解釈 ．

上述 含 多 既存 ， 内 辺 密度

間 辺 密度 差 着目 ． 実際 ， 加

，異 間 辺 絶対的 疎 仮定 ． 仮定 ，元々

潜在的 関係 抽出 対 精

度 低下 ．何故 ，抽出 多 傾向 ，

仮定 反 ． ，本論文 我々 与 巨視的構造

活用 ， 内 間 辺密度 差 注目 ．

4.2.2 分類手法 HITS

我々 基本的 問題 巨視的構造 利用

． Kleinberg HITS [23] ^{得 ．}HITS

分析 権威 Web 同定

．

関連 Web ^{集合 中 権威 同定 ，}

Kleinberg Web 2種類 ，authority 呼

権威 hub 呼 集 構成 仮定 ．

仮定 ， 「良 hub ^{多 良} authority ^張

，良 authority 多 良 hub 張

」 ，相互 強化 合 関係 ．HITS

構造 authority ^{同定 利用 ．}HITS Web 2

分 見 ，HITS

応用 思 至 ．

HITS 有用 考 ，HITS hub authority

分類 目的 ，仮定 hub authority ^{相互関係構造}

適 ． ， 適

用 ．次節 ， 向 適切 関係構造 提案

． ，彼等 一般的 最適化問題 再度定式化 ．