Comments
Description
Transcript
ウェブのリ ンク構造を用いて話題の 時系列変化を分析及び可視化する
修 士論文 ウ ェ ブ の リン ク構 造 を用 い て 話 題 の 時 系 列 変 化 を 分 析 及 び 可 視 化 す る手 法 に 関 す る研 究 平 成18年2月3日 指導教官 提出 喜連川 東京大 学大学 院 優 情 報 理 工 学 系研 究 科 電子 情報学 専攻 46420丹 教授 波 秀紀 目次 第1章 1.1. 1.2. 序論 は じめ に 1 1 本 論文 の構 成 1 関連研 究 3 第2章 2.1. 2.2. リン ク構 造 解 析 Webの 3 発 展過 程 マイ ニ ン グ 4 2.2.1. 様 々な変 化 量の測 定 4 2.2.2. トピ ック の 発 展 過 程 5 2.3. 情 報構 造 の発展 過 程 の可 視化 5 2.4. グ ラ フ レ イ ア ウ ト手 法 6 時系 列デ ー タの 分析 8 第3章 3.1. キ ー ワ ー ドか ら の 時 系 列 グ ラ フ の 抽 出 8 3.2. 時 系 列デ ー タの例 9 第4章WebRelievoの 4.1. WebRelievOの 概要 グ ラ フ レイ ア ウ ト 20 20 4.2. グラ フ間の位 置合 わせ 20 4.3. ノ ー ド ・エ ッ ジ の 発 生 と 消 滅 の 表 現 21 第5章 時系 列 グラフ の可視 化 22 5.1. グ ラ フ の ノ ー ドとエ ッジ の 取 得 22 5.2. 時 系 列 グ ラ フ の描 画 22 第6章 6.1. 部分 時 系列 グラ フの抽 出 全 体 の構 造 を考 慮 した 部 分 時 系 列 グ ラ フ 6.1.1. あ る時 間 に お け るペ ー ジ の 重 要 度 6.1.2. 時 系列 にわた って のペ ー ジ の重要 度 32 32 32 32 6.2. あるペ ー ジの周辺 の グ ラフの抽 出 33 6.3. WebRelievoの 33 第7章 改良 部分 時 系列 グラ フの可視 化 34 7.1. 全 体 的 な 時 系 列 変 化 の例 と分 析 34 7.2. 一 つ の ペ ー ジ に 注 目 し た 例 と分 析 38 7.3. ペ ー ジ の ス コア を 変 え た 場 合 の 例 と分 析 40 第8章 結論 47 8.1. ま とめ 47 8.2. 今後 の課 題 47 謝辞 48 参 考文 献 49 図 目次 図1:キ ー ワ ー ドに ヒ ッ トす る ペ ー ジ とinlink数 10 図2:キ ー ワ ー ドに ヒ ッ トす る ペ ー ジ 間 で のinlink数 11 図3:キ ー ワ ー ドか ら 得 ら れ るConnected 図4:時 系 列 間 で 見 た ペ ー ジ 数 とConnected 図5:時 系 列 変 化(キ ー ワ ー ド:winny) 13 14 図6:時 系 列 変 化(キ ー ワ ー ド:ト リ ビ ア の 泉) 15 図7:時 系 列 変 化(キ ー ワ ー ド:千 と 千 尋 の 神 隠 し) 16 図8:時 系 列 変 化(キ ー ワ ー ド:ダ ン デ ィ 坂 野) 図9:inlink数 ・CC・ Componentの 数 とサ イ ズ Componentの 数 12 ・最 大 サ イ ズ 17 時 系 列 変 化 一 括 表 示(キ-ワ ー ド:鳥 イ ン フ ル エ ン ザ) 18 図10:inlink数 ・CC・ 時 系 列 変 化 一 括 表 示(キ ー ワ ー ド:livedoor) 19 図11:時 系 列 グ ラ フ(1998/8-2003/7,キ-ワ 図12:時 系 列 グ ラ フ(1998/8キ-ワ 図13:時 系 列 グ ラ フ(2008/8キ 図14:時 系 列 グ ラ フ(2001/10キ 図15:時 系 列 グ ラ フ(2002/2キ ー ワ ー ド:Woodpecker) 27 図16:時 系 列 グ ラ フ(2003/2キ ー ワ ー ド:Woodpecker) 28 図17:時 系 列 グ ラ フ(2003/7キ ー ワ ー ド:Woodpecker) 29 図18:page,CCの ー ド:Woodpecker) ー ド:Woodpecker) 24 ー ワ ー ド:Woodpecker) 25 ー ワ ー ド:Woodpecker) 時 系 列 変 化(キ-ワ 26 ー ド:woodpecker) 図19:部 分 時 系 列 グ ラ フ(全 図20:部 分 時 系 列 グ ラ フ(2002/02∼2003/02,キ 図21:部 分 時 系 列 グ ラ フ(2003/02∼2003/07,キ-ワ 図22:部 23 時 間,キ-ワ ー ド:ベ 30 ッ カ ム) 35 ー ワ ー ド:ベ ッ カ ム) 36 ー ド:ベ ッ カ ム) 37 分 時 系 列 グ ラ フ(2003/02∼2003/07,キ ー ワ ー ド:ベ ッ カ ム,url 指 定:"http://www.albatros-film.com/movie/beckham/") 図23:部 分 時 系 列 グ ラ フ(全 図24:部 分 時 系 列 グ ラ フ(2000/08∼2001/10,キ 図25:部 時 間,キ 38 ー ワ ー ド:BSE) 分 時 系 列 グ ラ フ(2003/07∼2004/01,キ 40 ー ワ ー ド:BSE) ー ワー ド:BSE,ス 41 コ アS) 43 図26:部 分 時 系 列 グ ラ フ(2003/07∼2004/01,キ-ワ 図27:部 分 時 系 列 グ ラ フ(2003/07∼2004/05,キ ー ド:BSE,ス コ アa) 44 http://news.kyodo.co.jp/kyodonews/2003/bse/) ー ワ ー ド:BSE,url指 定: 46 表 目次 表1:Eadesの 表2:ウ レ イ ア ウ トア ル ゴ リ ズ ム ェブ アー カイ ブ の詳細 表3:id→URLの ア ル ゴ リズ ム 7 8 22 第1章 序論 1.1.は じめ に Web上 に 蓄 積 され る情 報 は 現 在 も急 増 して お り,膨 大 な 量 の 情 報 が 溢 れ て い る.こ の 中か ら必 要 な 情 報 を探 し 出 す の は 非 常 に 困難 で あ り,テ キ ス ト解 析 に よ る 検 索 の み で は な く,リ ン ク構 造 の 解 析 な ど,ペ ー ジ 間 の 関 係 性 を 考 え たWeb全 が 重 要 と な っ て く る.リ 1998年 にStanford大 体 の構 造解析 ン ク構 造 を ラ ン キ ン グ に 応 用 して い る 検 索 シ ス テ ム と して, 学 のPageとBrinがWebペ ー ジ の 重 要 度 を 表 す 指 標 と して 提 案 したPageRank[1]が 効 果 を 挙 げ て お り,さ ら にPageRankを 改 良 し よ う とす る研 究 も盛 ん に 行 わ れ て い る[2,3]. しか し,現 状 の 主 要 な 検 索 エ ン ジ ン で は,最 新 の ペ ー ジ を い か に 検 索 す るか に焦 点 が 当て られ て お り,過 去 を 紐 解 く よ うな 調 査 方 法 は ほ とん ど提 供 され て い な い.膨 大 な アー カ イ ブ を 基 に,ペ ー ジ の 内 容 を過 去 に さ か の ぼ っ て 見 られ るサ ー ビ ス[4]も 始 ま って い る が,未 だそ の機 能 は限 定 的で ある。 現 在 は 多 くのWebペ ー ジ が,生 成,更 新,お よ び 消 滅 の 過 程 を 経 て 日々 変 化 して お り,そ れ に応 じてWebの ネ ッ トワ ー ク 構 造 も動 的 に変 化 を続 け て い る.こ う した 背 景 の 下,Webの 発 展 過 程 を 把 握 す る こ とは,実 社 会 で 起 き る事 象 の 背 景 や 予 兆 を探 る 上 で 重 要 な課 題 と な っ て お り,以 下 の よ うな 状 況 で 有 用 で あ る. 1.Webに お け る トピ ッ ク の履 歴 に 関 す る質 問 に 答 え る. 2.新 た な 情 報 の発 生 を 監 視 ま た は観 察 し,ト レ ン ドを分 析 す る こ とで,市 場 調 査 な どに 応 用 す る. 3.Webに お け る社 会 学 的 な 現 象 とそ の推 移 を調 査 す る. 以 上 の 状 況 を踏 ま え,本 論 文 で は,本 研 究 室 で 定 期 的 に 収 集 した ウ ェ ブ ア ー カ イ ブ か ら,あ る キ ー ワー ドに 対 す る リン ク構 造 グ ラ フ を抽 出 し,そ の 時 系 列 変 化 を分 析 す る.ま た,Webの WebRelievo[5]を ペ ー ジ 問 の 関 連 が 発 展 す る 過 程 を 可 視 化 す る シ ス テ ム, 利 用 し,改 良 を 行 っ て,キ ー ワ ー ドに 対 す る リ ン ク グ ラ フ を 可 視 化 す る.話 題 に 対 す る ウ ェ ブ 上 の リン ク構 造 の 発 展 過 程 を 可 視 化 す る こ とで,過 去 の 事 象 に 関 す る 事 実 を確 認 し,ウ ェブ 上 の 話 題 に 関 す る変 化 を 検 出す る. 1.2.本 論 文 の構 成 以 下,第2章 に て リ ン ク構 造 解 析,ウ ェ ブ の 発 展 過 程 マ イ ニ ン グ,構 造 の発 展 過 程 の 可 視 化 お よ び そ の 際 の グ ラ フ レイ ア ウ トアル ゴ リズ ム に つ い て,関 連 研 究 を 紹 介 す る.第3章 で は,キ ー ワー ドに 対 す る 時 系 列 グ ラ フデ ー タ の 抽 出 の 手 法 とそ の デ ー タ ―1― の 分 析 を行 う.第4章 し,第5章 で グ ラ フ の 発 展 過 程 可 視 化 シ ス テ ムWebRelievoの 概 要 を紹 介 で そ れ ら を用 い て キ ー ワー ドに 対 す る 時 系 列 グ ラ フ を 可視 化 す る. 第6章 で は,時 系 列 グ ラ フ か ら部 分 グ ラ フ を 得 る手 法 と そ の た め のペ ー ジ の 順 位 付 け の手 法 を 述 べ,第7章 で さ ま ざま な 条 件 で の 部 分 時 系 列 グ ラ フ の 可 視 化 と,そ の 例 の 分 析 を行 い,最 後 に ま と め と今 後 の 課 題 を述 べ る. ―2― 第2章 2.1.リ Web上 関連 研 究 ン ク構 造 解 析 の ハ イ パ ー リ ン ク で つ な が れ た ペ ー ジ 群 は,そ の ペ ー ジ を ノー ドと し、 リン ク を エ ッ ジ と し た 有 向 グ ラ フ と考 え ら れ る 。 そ し て そ の 構 造 を 解 析 す る こ と で 関 連 し た ペ ー ジ 群 を 見 つ け る 研 究 が あ る[8,9].Web上 で は,互 い に 関連 す るペ ー ジ は グ ラ フ に お い て 近 く に 存 在 し て い る 傾 向 が あ る.こ の 理 由 と し て は,同 種 類 の ペ ー ジ へ の リ ン ク を 集 め た リ ン ク 集 が 数 多 く 作 成 さ れ て い る こ と,ウ ェ ブ ペ ー ジ の 作 者 は 自 分 の べ ー ジ に 関 連 す る 情 報 を 持 つ ペ ー ジ に リ ン ク を 張 る 傾 向 が あ る こ と ,が 挙 げ ら れ る.こ の 特 徴 を 利 用 し て,密 に 結 合 さ れ た ペ ー ジ を 抽 出 す る こ と で 互 い に 関 連 す る ペ ー ジ の 集 合 を 得 る こ と が で き る. Kleinberg[6]は,オ ー ソ リテ ィ お よ び ハ ブ の 概 念 に 基 づ い て 関 連 ペ ー ジ を 計 算 す る 手 法 を 提 案 し て い る.オ ー ソ リ テ ィ ー と は,あ つ ペ ー ジ の こ と を 指 し,多 くの 良 い ハ ブ か ら リ ン ク を 張 られ て い る ペ ー ジ と定 義 され る.ハ ブ は,あ る トピ ッ ク に つ い て 良 質 な 内 容 を 持 る ト ピ ッ ク に 関 す る リ ン ク 集 や ブ ッ ク マ ー ク ペ ー ジ の こ と を 指 し,多 く の 良 い オ ー ソ リ テ ィ ー に リ ン ク を 張 っ て い る ペ ー ジ と 定 義 さ れ る.HITS[6]は, こ の 定 義 に 基 づ い で,ウ ェ ブ の 部 分 グ ラ フ か ら オ ー ソ リテ ィ お よ び ハ ブ を 効 率 良 く 抽 出 す る ア ル ゴ リ ズ ム で あ る. ま たDeanら は,シ Companion[7]と ー ドペ ー ジ に 対 し 関 連 す る ペ ー ジ の リ ス トを 結 果 と し て 返 す, い う 関 連 ペ ー ジ ア ル ゴ リ ズ ム(RPA)にHITSを Companionは,シ 応 用 し て い る. ー ドペ ー ジ 周 辺 の グ ラ フ か ら オ ー ソ リ テ ィ を 抽 出 す る. 豊 田 ら は,Companionの ―[10]を 提 案 し て い る .こ さ れ たURLに 再 現 率 を 下 げ る 代 わ り に 精 度 を 上 げ る 手 法,Companion れ はHITSを 基 に 改 良 を 行 っ た ア ル ゴ リ ズ ム で あ り,入 対 し て そ の 関 連 ペ ー ジ を 求 め る も の で あ る 。Companion― 力 の アル ゴ リ ズ ム は 次 の 通 りで あ る. ま ず 入 力URLに 対 応 す る シ ー ドペ ー ジ か ら リ ン ク で 結 ば れ た 近 隣 の ペ ー ジ を 集 め, 近 傍 グ ラ フ を 作 る.近 傍 グ ラ フ に はHITSと 異 な り,シ ー ドペ ー ジ ヘ リ ン ク を 持 つ ペ ー ジ と そ れ ら が リ ン ク す る ペ ー ジ の み を 含 め る .後 者 の リ ン ク で は そ の 出 現 順 序 を 考 慮 し,シ ー ドペ ー ジ へ の リ ン ク の 前 後R個 持 つ ミ ラ ー ペ ー ジ は 代 表 と し て1つ の リ ン ク の み を 含 め る 。ま た 同 一 の 内容 を の ペ ー ジ を 定 め,そ の ペ ー ジ に ま と め る. 次 に ペ ー ジ の サ ー バ 名 に よ っ て リ ン ク に 対 す る 重 みhub 計 算 す る.こ 重 み を 表 す.同 れ は そ れ ぞ れ ペ ー ジpか ジpが らqへ _wt(p,q),auth_wt(p,q)を の リ ン ク の ハ ブ の 重 み ・オ ー ソ リ テ ィ の 一 サ ー バ 内 の リ ン ク に 対 し て は こ の 両 方 の 重 み を0に 外 部 の 同 一 サ ー バ にn個 の リ ン ク を 持 っ て い れ ば,そ す る.あ るペ ー の リン ク に 当 た る hub _wt(p,q)を す べ て1/nと す る.ま た 同 じ外 部 サ ー バ か らn個 の リ ン ク が あ る ペ ー ジpが あ れ ば,そ のauth_wt(q,p)を1/nと す る. ハ ブ ・オ ー ソ リテ ィ ス コ アhub(p)・auth(p)を1に 初 期 化 し,以 下 の 式 を 各 ス コ ア が 収 束 す る ま で 繰 り 返 す. ―3― hub(p).auth(p)そ れ ぞ れ に つ い て 、 そ の 二 乗 和 が1と こ の よ う に し て 得 ら れ たauth(p)の な る よ うに 正 規 化. 高 い も の か ら シ ー ドペ ー ジ へ の 関 連 ペ ー ジ と し て 出 力 す る. 2.2.Webの 発 展 過 程 マ イ ニ ン グ ウェ ブ ア ー カ イ ブ を用 い た 発 展 過 程 の マ イ ニ ン グ は,ク ロ ー ラ を用 い て 定期 的 に ウ ェブ ペ ー ジ を収 集 し,ど の よ うな変 化 が ど の程 度 起 き た か を調 査 す る こ とが 基 本 とな る.ウ ェ ブ の様 々 な変 化 量 の 測 定 に 基 づ い て,ウ ェ ブ の将 来 の 変 化 を予 測 可 能 か ど うか の調 査,ウ ェ ブ にお け る トピ ック の 出 現 を検 出 し,そ の 発 展 過 程 を 追跡 す る試 み 等 が行 わ れ て い る. 2.2.1.様 々 な 変 化 量 の 測 定 Fetterlyら は,大 規 模 な ク ロー リン グ を行 っ て 一 週 間 ご と に15億 ペ ー ジ を 収 集 し, こ れ を11週 間 に わ た っ て 繰 り返 す こ とで,各 ペ ー ジ の 変 化 の 度 合 を解 析 し た[17].こ の 解 析 か ら,以 下 の よ うにペ ー ジ の 未 来 度 が あ る 程 度 予 測 で き る こ とが 明 ら か に な っ た. ・ ク ロ ー ル ご と に 取 得 で き な く な るペ ー ジ が 増 加 す る .11週 間 後 に は10数%の べ ー ジ が 取 得 で き な く な って い た .こ の うち,サ ー バ 管 理 者 の 設 定 す る ロ ボ ッ トル ー ル に よ っ て 排 除 され た ケ ー ス も3%ほ ど存 在 し ,こ れ は ウ ェ ブ の 観 測 行 為 に よ っ て 観 測 され る側 の 行 動 を変 化 させ 得 る こ とを 示 して い る. ・ ペ ー ジ 内 容 は1週 間 で は ほ とん ど更 新 され な い .2週 間続 け て取 得で きた すべ て の ペ ー ジ 対 に つ い て 変 化 を 調 べ た と こ ろ,65%の 対 で 更 新 が な か っ た. ・ サ イ ズ の 小 さ い ペ ー ジ よ り大 き な ペ ー ジ の ほ うが 変 化 の 度 合 が 大 き い .こ の こ と は,ペ ー ジ のサ イ ズ が未 来 の 変 過 度 を 予 測 す る 手 が か り とな る こ とを示 して い る. ・ 前 の 週 に 変 化 の 小 さい ペ ー ジ は 次 の 週 も変 化 は 小 さ く ,大 き い ペ ー ジ は 次 の 週 も 変 化 が 大 き い.よ と な る. っ て,過 去 に お け る 変 化 度 も未 来 の 変 化 度 を 予 測 す る 手 が か り Fetterlyら の 手 法 は,URLの 集 合 を 固 定 して 繰 り返 し収 集 す る た め,新 し い ペ ー ジ の 出 現 は 検 出 で き な い.Ntoulasら は,Google Directryか ら著 名 な150サ イ トを 選 択 して 固 定 し,1週 間 ご と に そ れ らの サ イ トの 中 身 を 取 りつ くす こ とで 新 規 ペ ー ジ や 新 規 ハ イ パ ー リン ク の発 生 す る度 合 を調 査 した[18].Ntoulasら が1年 分(52週 間) の ア ー カ イ ブ か ら得 た 結 果 を 以 下 に 示 す. ・ 選 択 した サ イ ト内 の ペ ー ジ は 速 い ペ ー ス で 新 しい ペ ー ジ と入 れ 替 わ っ て い る .1 週 間 ご との ア ー カ イ ブ 中,平 均8%が 新 し く作 られ た ペ ー ジ で あ る.ま た 初 回 に 取 得 で き た ペ ー ジ の う ち,半 年 後 に は50%,1年 て い る. ―4― 後 に は60%が 取 得 で き な くな っ ・ ペ ー ジ の コ ン テ ン ツ の 入 れ 替 わ りは ,ペ ー ジ 自 体 の 入 れ 替 わ り よ り も 緩 や か で あ る. ・ ハ イ パ ー リン ク数 の 入 れ 替 わ りは ペ ー ジ の 入 れ 替 わ り よ り さ らに 急 で ,1週 間ご と に25%の 新 規 リ ン ク が 作 成 さ れ,1年 後 に は80%の リ ン ク が 消 滅 し て い る. ・ ペ ー ジ 内容 の 変 化 に つ い て は ,Fetterlyら の 結 果 と 概 ね 同 じ よ う な 結 果 で あ る. つ ま り,ペ ー ジ 内 容 は ほ と ん ど 変 化 し て お ら ず,過 去 の 変 化 の 度 合 と未 来 の 変 化 の 度 合 に 相 関 が あ る こ と を 確 認 し て い る. 2.2.2.ト Internet ピ ッ ク の発 展 過 程 Archive(www.archive.org)は,1996年 収 集 し続 け て お り,2001年 に は,URLを か ら統 計 的 に ウ ェ ブ ペ ー ジ を 大 規 模 に 入 力 す る と そ のURLの 変更履歴 を閲覧で きる Wayback Machine[4]イ ン タ ー フ ェー ス を 公 開 し て い る. Recall(reca11.archive.org)はInternet Archive上 に 構 築 さ れ た 全 文 検 索 エ ン ジ ン で, 1996年 か ら2003年5月 2003年9月 Recallは ま で に 収 集 さ れ た 約110億 ∼2004年9月 ペ ー ジ(0.5ペ タ バ イ ト)を 索 引 化 し, ま で 公 開 さ れ た. 単 な る全 文 検 索 エ ン ジ ン で は な く,ア ー カ イ ブ か ら 自動 的 に カ テ ゴ リー お よ び ト ピ ッ ク を 抽 出 し て トピ ッ ク の 発 展 過 程 を 調 査 で き る 機 能 を 持 っ て い た.キ ー ワ ー ド を 指 定 して 検 索 す る と,そ の 出 現 頻 度 の 時 系 列 的 な 変 化 を グ ラ フ 化 し,同 時 に 関 連 す る キ ー ワ ー ドの 出 現 頻 度 も グ ラ フ 化 して 提 示 す る .こ れ らの キ ー ワ ー ドの 動 き か ら ト ピ ッ ク の 変 遷 を 調 査 す る こ と が で き,ネ ッ トワ ー ク 上 の 流 行 調 査 な ど に 有 益 な も の だ っ た が,現 在 は 停 止 し て い る. 2.3.情 報 構 造 の発 展 過 程 の 可 視 化 情 報 構 造 の 発 展 過 程 を 可 視 化 す る手 法 に つ い て は,学 術 文 献 の 関 連 可 視 化,グ フ描 画 な どの 分 野 で 様 々 な 研 究 が な され て い る. Chenら ラ は科 学 論 文 にお け る著 者 間 の 共参 照 関係 の発 展 過 程 を可視 化 す る手 法 を 提 案 して い る[11].さ ら に,発 展 過 程 の 可 視 化 に 適 した 辺 の フ ィル タ リン グ手 法 に 関 す る 考 察 を 行 っ て い る[12]. Chiら は タイ ム チ ュ ー ブ と呼 ば れ る手 法 を 提 案 し,1つ の ウ ェ ブ サ イ トに お け るペ ー ジの階 層構 造 ,お よび 訪 問 者 の ア ク セ ス パ ター ン の 発 展 過 程 を 可 視 化 した[131.こ の 手 法 で は ま ず サ イ トの 階 層 構造 を,ル ー トペ ー ジ を 中 心 と して,子 ペ ー ジ を 同心 円 上 に 配 置 した デ ィス ク ツ リー 手 法 で 可 視 化 す る.さ らに 各 時 間 に つ い て デ ィ ス ク ツ リ ー を作成 し ,並 べ て 表 示 す る こ とで 時 間 に よ る 変 化 を 閲 覧 可 能 に す る. Diehlら は,変 化 す る グ ラ フ の列 か らア ニ メ ー シ ョ ン を 作 成 す る た め の,グ ラ フ 描 画 手 法 を 提 案 し て い る[9].Diehlら の 手 法 は,グ ラ フ列 に含 まれ る 全 グ ラ フ の 和 を 取 っ た ス ー パ ー グ ラ フ に 対 して 事 前 に力 学 的 レイ ア ウ トを 施 し,そ の 結 果 を基 に 各 グ ラ フ の レイ ア ウ トを 決 定 す る こ とで,グ ラ フ 変 化 に よ る レイ ア ウ トの 急 激 な 変 化 を抑 え て い る. ま た,Ertenら 列 配 置 した り,2次 は,力 学 的 グ ラ フ レイ ア ウ トを 拡 張 して,変 化 す る グ ラ フ の列 を 並 元 レイ ア ウ トを3次 元 的 に 重 ね て 表 示 す る 等,様 々 な 形 で 描 画 す ―5― る 枠 組 を提 案 し て お り[14],最 近 で は 学 術 文 献 の 関係 の進 化 を 可 視 化 す る 事 例 に 応 用 して い る. 2.4.グ ラ フ レ イ ア ウ ト手 法 グ ラ フ を レイ ア ウ トす る に は,ど の よ うな ノ ー ド配 置 が 審 美 的 基 準 を 最 適 化 す るか を 探 索 す る.し か し,総 当 り的 に 探 索 す る こ とは 組 み 合 わ せ 的 に 膨 大 な 数 とな り多 く の 場 合NP困 難 で あ る た め,ユ ー ザ に よ る イ ン タ ラ クテ ィ ブ な 情 報 獲 得 を 支 援 す るた め に は,近 似 的 な 最 適 解 を 短 時 間 で 求 め る た め の 手 法 が 求 め られ る.そ の た め の 手 法 は 大 ま か に グ ラ フ理 論 を べ ー ス に した ア ル ゴ リズ ム 的 ア プ ロー チ,物 理 モ デ ル をベ ー ス と し た モ デ ル 的 ア プ ロー チ の2種 類 に 分 類 され る. アル ゴ リズ ム 的 ア プ ロー チ は,主 に グ ラ フ ア ル ゴ リズ ム や,計 算 幾 何,離 散 数 学 な ど の理 論 的 手 法 を利 用 し,あ らか じ め用 意 され た 拘 束 条 件 を 準 最 適 化 す る よ うに設 計 され た 高 速 な ア ル ゴ リズ ム に よ る レイ ア ウ ト手 法 で,多 く の 場 合,格 子 点 上 に ノー ド を配 置 し,そ の組 み 合 わ せ を 探 索 す る.比 較 的 小 さな 計 算 時 間 で 行 う こ とが で き るが, ア ル ゴ リズ ム の 設 計 に 用 い られ た 拘 束 条 件 以 外 の 制 約 を あ とか ら組 み 込 む こ とが 難 し く,ユ ー ザ に よ る拘 束 条 件 の 指 定 が で き な い た め,汎 用 性 に 乏 し い とい う欠 点 が あ る. モ デ ル 的 ア プ ロ ー チ は グ ラ フ を何 らか の モ デ ル に よ っ て 表 現 し,そ の モ デ ル を解 く 事 に よ っ て 近 似 的 な 最 適 解 を 求 め る 手 法 で あ る.多 少 計 算 量 が 大 き い もの の 様 々 な 拘 束 条 件 を 組 み 込 み や す く拡 張 性 が 高 い とい う特 徴 を持 つ.グ ラ フ レイ ア ウ トに 用 い ら れ る モ デ ル は,遺 伝 子 モ デ ル,生 物 モ デ ル,力 学 モ デ ル 等 で あ る が そ の な か で も特 に 力 学 的 な モ デ ル が よ く用 い られ る.こ れ は,日 常 的 に 目に す る 自然 界 の 力 学 的 な 現 象 を用 い る こ とで 視 覚 的 に 自然 な レイ ア ウ トが で き る と考 え られ て い る か らで あ る. 力 学 的 モ デ ル に よ る レイ ア ウ ト手 法 で 最 も簡 潔 で よ く知 られ た モ デ ル が,Eadesに よ る"Spring Embedder"で あ る[15].こ の モ デ ル で は,エ ッ ジ を 自然 長 を 持 っ た ば ね と仮 定 し,エ ッジ で 接 続 した ノー ド間 に は ば ね 力 を模 した 力Fs,隣 接 し な い ノ ー ド同 士 に は 逆2乗 則 の 斥 力 に よ っ て 互 い に 反 発 しあ う力Frを 仮 定 す る. た だ し 、 こ こ でc1,c2,c3は 表1に 示 す よ う に,各 定 数,dは ノ ー ド間 の 距 離 で あ る. ノ ー ドに 働 く 力 の 合 計 を 計 算 し 、 そ れ に 従 っ て ノ ー ド を 移 動 さ せ る 処 理 の 繰 り返 し 計 算 で レイ ア ウ トを 変 形 さ せ る こ と に よ り,ノ ー ドが 近 づ き す ぎ ず,隣 称 的 な レイ ア ウ 接 ノ ー ドが 近 く に 配 置 され,エ ッ ジ の 長 さ が 均 一 に 近 く,対 トを 得 る. ―6― 表1:Eadesの レイ ア ウ トア ル ゴ リズ ム こ の モ デ ル は こ の 後 に 提 案 され た 多 くの 力 学 的 モ デ ル の ベ ー ス と な っ て い る が,計 算 量 が 大 き い,力 の 定 義 が 単 純 す ぎ て グ ラ フ に よ っ て は うま く レイ ア ウ トで き な い (局所 最 適 解 に 陥 る ・収 束 し な い)な どの 問 題 が あ り,様 々 な 改 良 手 法 が 開 発 され て い る. ―7― 第3章 時 系 列 デ ー タの分 析 本 研 究 室 で は,1999年8月 か ら2004年5月 ま で に 渡 っ て 定 期 的 に 収 集 され たWeb アー カ イ ブ が 存 在 す る(表2).こ れ を も と に あ る キ ー ワー ドに対 して 得 られ るペ ー ジ の リン ク構 造 を グ ラ フ化 す る. 表2:ウ 3.1.キ ェブ ア ー カ イ ブ の 詳 細 ー ワ ー ドか ら の 時 系 列 グ ラ フ の 抽 出 時 系 列 グ ラ フ とは,あ る 時 間 間 隔 を お い て 作 成 され た 有 向 グ ラ フ の 列 で あ り,最 初 の 時 間 を1,最 後 の 時 間 をTと した とき 以 下 の よ うに 表 さ れ る. 添 字tは 各 ウ ェ ブ ア ー カ イ ブ が 収 集 さ れ た 時 期 を 表 す.Vt中 ジ を 表 し,Et中 の 有 向 辺(u,v)は,uを 関 連 ペ ー ジ と し て 出 力 さ れ る こ と を 示 し て い る.時 び 辺 は,各 の ノ ー ドは ウ ェ ブ ペ ー 関 連 ペ ー ジ ア ル ゴ リ ズ ム に 入 力 す る とvが 系 列 グ ラ フ に お い て,ノ 時 間 に お い て 発 生 お よ び 消 滅 す る 可 能 性 が あ り,Vtお よ びEtの ー ドお よ 要 素数 は 一 定 と は 限 ら な い. 本 研 究 で は,uと ペ ー ジ と し て ,グ し て,あ る キ ー ワ ー ド に マ ッ チ す る ペ ー ジ を と る.vを ラ フGtを 2003/2,2004/1,2004/5)と ま ず,あ 得 る.ま そ のinLink たtは(1999/8,2000/8,2001/10,2002/2, して い る. る キ ー ワ ー ド に 対 し,ア ン カ ー ・タ イ トル ・本 文 に そ の キ ー ワ ー ドが 含 ま ―8― れ る 文 書 を 検 索 し,各 ペ ー ジ ご と のIDを 得 る.こ の ペ ー ジ の 集 合Uが グ ラ フ の ノー ド と な る. 次 に 各 ペ ー ジ ご と に リ ン ク デ ー タ ベ ー ス か らinLinkを ー ジuと そ こ に リ ン ク を 張 っ て い る ペ ー ジv'のIDを 得 る.キ ー ワ ー ドを 含 む ペ そ れ ぞ れuid ,vid'と す る と, (uid,vid') の 形 でinLinkが 得 られ る. こ の と き ペ ー ジv'は 全 ペ ー ジ が 対 象 に な っ て い る の で,集 け を 対 象 に フ ィ ル タ リ ン グ を 行 う.つ ま り,キ 合Uに 属 す るペ ー ジだ ー ワ ー ドを 含 む ペ ー ジ 同 士 の リ ン ク と し て, (uid,vid') を 得 る.こ れ が が リ ン ク 構 造 グ ラ フ の エ ッ ジ と な る. こ の よ う に し て 得 ら れ た ノ ー ド と エ ッ ジ に よ り,リ れ ら の 処 理 を 各 時 系 列 に お い て 行 い,文 ン ク 構 造 グ ラ フ が 得 ら れ る.こ 書 デ ー タ ベ ー ス と リ ン ク デ ー タ ベ ー ス か ら, キ ー ワ ー ドに 対 す る 時 系 列 グ ラ フ が 得 られ る. 3.2.時 系 列 デ ー タ の 例 得 られ た 各 デ ー タ の 例 を 以 下 に 示 す.時 過 程 で 得 ら れ たinLink等 図1は,ペ ー ジuの 表 示 し た も の で あ る.縦 系 列 グ ラ フ の デ ー タ だ け で な く,前 項 の各 の デ ー タ も 共 に 示 す. そ れ ぞ れ に 対 す るinLinkペ 軸 がinLink数,横 こ れ に 対 し て 図2は,フ ー ジvの 数 を ヒ ス トグ ラ ム 化 し て 軸 が ペ ー ジ 数 で あ る. ィ ル タ リ ン グ 後 のinLinkペ ー ジv'に つ い て,同 様 に ヒス トグ ラ ム 化 し た も の で あ る. 図3は,得 ら れ た グ ラ フ のConnected Componentに つ い て,1成 分 の ノ ー ド数 つ ま りサ イ ズ を 横 軸 に と っ て 同 様 に ヒ ス トグ ラ ム 化 し た も の で あ る. 図4は,時 間 を 横 軸 に と り,ペ 最 大 のConnected 図1∼4の Componentの ー ジuの 数,Connected Componentの 数,お サ イ ズ を 時 系 列 ご と に 表 示 し た も の で あ る. 例 で は キ ー ワ ー ドは"東 京 大 学"で あ る. ―9― よび 図1:キー ワー ドに ヒ ッ トす るペ ー ジ とinlink数 ―10― 図2:キ ー ワー ドに ヒ ッ トす るペ ー ジ間 で のinlink数 ―11― 図3:キ ー ワ ー ドか ら得 られ るConnend ―12― Componentの 数 とサ イ ズ 図4:時 系 列 間 で 見 た ペ ー ジ 数 とConnnected Componentの ―13― 数･最 大サ イ ズ 図4を 見 る と,2003/7か え て,サ ら2004/1に か け て は,Cennected イ ズ が 小 さ く な っ て い る の で,連 結 せ ず に,つ ラ バ ラ に 存 在 す る ペ ー ジ が 増 え た と 言 う こ と で あ る.全 Connectec る."東 Componentの Componentの 数 が増 ま り リ ン グ で つ な が らず に バ 体 と して は ペ ー ジ 数 と 数 ・大 き さ 共 に 概 ね 同 じ よ う な 傾 向 で 推 移 し て い る と 言 え 京 大 学"と い う キ ー ワ ー ドは 時 間 ご と の 変 動 が そ れ ほ ど 顕 著 で な い,一 般的な キ ー ワ ー ド と し て 選 ん だ. 図5,6に お い て は,max は 比 較 的 最 近 の ト ピ ッ ク の 例 を 示 す.特 sire of CCが に 図5(キ 大 き く 伸 び て い る こ と か ら,winny関 ン ク で 連 結 さ れ て い る も の が 多 い と い う 傾 向 が わ か る. 図5:時 ー ワ ー ド"winny")に 系 列 変 化(キ ー ワ ー ド:winny) ―14― 連 の ペ ー ジは リ 図6:時 一方 ,一 系 列 変 化(キ ー ワー ド:ト リ ビア の 泉 ） 時 期 に 変 化 が 集 中 し て い る よ う な 例 を 図7,8に 時 期 に 注 目 が 集 ま っ て い る 様 子 が わ か る.ま と ん ど 増 減 な く ペ ー ジ 数 とConnected か ら,無 て は,max Component数が 関 係 に 多 く の ペ ー ジ が 発 生 し,消 size of CCと た 図7に 示 す.ト お い て は,max ピ ッ ク と し て一 size of CCが え て い っ た 様 子 が わ か る.逆 に 図8に ペ ー ジ 数 が 似 た よ う な 推 移 を し て い る こ と か ら,リ な が っ た 大 き な ペ ー ジ 群 が 現 れ て,そ ほ 同 じ よ うに 増 減 して い る こ と おい ン クで つ の 集 合 ご と 消 え て い っ た 様 子 が 見 て 取 れ る. ―15― 図7:時 系列変化(キ ーワ ー ド:千 と千尋の神隠し) ―16― 図8:時 図1で 系 列 変化(キ ー ワー ド:ダ ン デ ィ坂 野) 示 し た ペ ー ジ のinlink数,図2で 内 で のinlink数,図3のConnected Connected も の を 図9に Componentの 示 す.た 示 し た キ ー ワ ー ド に ヒ ッ トす る ペ ー ジ 集 合 Componentの 数 ・max だ し,キ sizeの グ ラ フ を 見 る と,わ 時 系 列 変 化 の4種 ー ワ ー ドは 異 な る(キ 右 下 の 時 系 列 変 化 の グ ラ フ だ け 見 る と,ご やinlinkの 数 と サ イ ズ,図4の ペ ー ジ数 ・ の グ ラ フ を 一 括 表 示 した ー ワ ー ド"鳥 イ ンフ ル エ ン ザ"). く 最 近 の 話 題 で あ る こ と が わ か る が,CC す か な が ら1999年 い た と い う こ と が わ か る. ―17― か ら ペ ー ジ 自 体 やCCは 存在 して 図9:inlink数 図10も 図9と ペ ー ジ 数 とCCの な り,CCの ・CC・ 時 系 列 変 化 一 括 表 示(キ ー ワ ー ド;鳥 イ ンフ ル エ ンザ) 同 じ よ うに 一括 表 示 した もの で あ る が,あ る 時 期(2003/2)ま で は, 数 が と も に 増 え て いた の に,そ れ 以 降 急 速 にCCの サ イ ズ が 大 きく 数 は あ ま り増 え な くな っ て い る こ と が 見 て 取 れ る.こ れ は つ ま り,あ る 時 期 ま で はCCが 凝 縮 せ ず に バ ラ バ ラ に ペ ー ジ が 増 え て い た の が,あ る時 期 を 境 に グ ラ フ と して つ な が り始 め,そ の 後 増 え るペ ー ジ も ほ と ん ど最 大 のCCに 取 り込 ま れ て い る とい う こ と を 意 味 し て い る. ―18― 図10:inlink数 ・CC,時 系 列 吏 化 一括 表 示(キ ー ワー ド:livedoor) こ の よ うに,デ ー タ を 見 た だ け で も様 々 な キー ワ ー ドに 対 し て,ウ 造 が 多 様 な 変 化 を 見 せ て い る こ と が わ か る. ―19― ェ ブ の リン ク 構 第4章WebRelievoの 概 要 本 章 で は,Webの ペ ー ジ 問 の 関 連 の発 展 過 程 を 可 視 化 す る シ ス テ ム,WebRelievo[5] の 概 要 を示 す.WebRelievoは,ユ ー ザ の 指 定 した ペ ー ジ に 対 して,各 収 集 時 期 の ア ー カ イ ブ か らペ ー ジ の相 関 図 を表 す グ ラ フ を抽 出 して ,時 系 列 グ ラ フ と呼 ば れ る グ ラ フ の 列 を作 成 し,時 間 に 沿 っ て 漫 画 の コ マ 割 の よ うに 表 示 す る こ とで,発 展 過 程 の 閲 覧 を可 能 に す る.各 グ ラ フ は,同 じペ ー ジ が 概 ね 同 じ位 置 に 表 示 され る よ う同 期 して 自動 的 に レイ ア ウ トされ る た め,各 時 間 で どの よ うな 変 化 が 起 き た か を グ ラ フ を比 較 しな が ら容 易 に 把 握 す る こ とが で き る. 4.1.WebRelievoの WebRelievoに グ ラ フ レイ ア ウ ト お け る グ ラ フ レ イ ア ウ トに は,力 学 的 ア プ ロ ー チ[15,16]を 時系 列 グ ラ フ 間 の 位 置 調 整 を 行 う よ う に 修 正 し た ア ル ゴ リ ズ ム が 用 い られ て い る. す な わ ち,各 時 系 列 グ ラ フGt(p)を 列 方 向 に ノ ー ドの 位 置 調 整 を 行 う.ユ き,そ 力 学 的 ア プ ロ ー チ で レ イ ア ウ トし な が ら,時 系 ー ザ は 対 話 的 に ノ ー ドを ドラ ッ グ す る こ と が で の 場 合 に も ノ ー ドの 位 置 が 自 動 的 に 同 期 さ れ る. 2.3.で 述 べ た よ う に,力 学 的 ア プ ロ ー チ は,グ ラ フ に お け る ノ ー ドを 質 点,辺 を ば ね と す る 力 学 モ デ ル の シ ミ ュ レ ー シ ョ ン を 用 い て グ ラ フ を レ イ ア ウ トす る 手 法 で あ り,辺 で つ な が れ た2点 の 間 に は 引 力Fsが 働 き,全 て の2点 の 間 に は 斥 力Frが 働 く.WebRelievoで は 点u,v間 に 働 く 引 力 お よ び 斥 力 と して 以 下 の 定 義 を 用 い て い る.そ れ ぞ れ の 力 はu,v間 の ユ ー ク リ ッ ド距 離dを 引 数 と す る 関 数 で 表 さ れ る. た だ し,c1は2点 間 の 望 ま し い 距 離 を 表 す 定 数 で あ る.辺 で 結 ば れ た2点 がc1と な っ た とき に 引 力 と斥 力 が つ りあ う よ うに な っ て い る. 4.2.グ ラ フ 間 の位 置 合 わせ 時 系 列 グ ラ フ の 差 分 を 理 解 しや す く す る た め,隣 が で き る だ け 同 じ 位 置 に あ る こ と が 望 ま し い.こ は 引 力,斥 り合 う グ ラ フ の 間 で は 同 じ ノ ー ド れ を 実 現 す る た め,WebRelievoで 力 に加 え て 隣 り合 うグ ラ フ 間 で位 置 合 わ せ を 行 う力 を 各 点 に 与 え て い る 。 ノ ー ドut∈Gtに Ft.1お 間 の距離 よ びFt+1が は,ut-1∈Gt-1お 加 え られ る.utが よ びut+1∈Gt+1に 近 付 く 方 向 の 力, 隣 の グ ラ フ に存 在 しな い 場 合 に は こ れ らの 力 ―20― は0と な る.定 義 は,以 下 の 通 りで あ る.Ft-1は,utとut-1問 の 距 離dt.1を 数 とす る 関数 で 定 義 され,Ft+1も 同様 に 定 義 され る. Ft-1(dt.1)=dt-1/c2,Ft+1(dt+1)=dt+1/c2 こ こ で,c2は 位 置 合 わ せ の 力 の 強 さ を 調 整 す る定 数 で あ る.c2=1の 引 と き,位 置 合 わ せ の力 は最 大 に な り,uは 各 グ ラ フ で ほ ぼ 同 位 置 に 表 示 され る.c2を 大 き くす る と,各 グ ラ フ で の 引 力,斥 力 の 方 が 相 対 的 に 強 く な り,位 置 合 わ せ の 力 は 弱 ま る. 直 感 的 に は,位 置 合 わ せ の 力 を 最 大 に す る と最 も理 解 しや す い レイ ア ウ トに な る と予 想 され る.し か し,位 置 合 わ せ を厳 密 に 行 う と,最 初 の 時 間 に お け る 位 置 関 係 が,最 後 の 時 間 に お け る位 置 関 係 に も影 響 す る た め(逆 も 同様),構 造 の変 化 が 大 き い とき に は か え っ て グ ラ フ の 形 を い び つ に し て しま う.こ の た め,時 間 の 経 過 と共 に緩 や か に 位 置 の変 更 を許 す ほ うが レイ ア ウ トは 見 や す く な る. WebRelievoは,漫 画 に お け る コマ 割 の よ うに 画 面 を 分 割 して,左 か ら右,上 から 下 の 順 番 で 各 時 間 毎 に 時 系 列 グ ラ フ を 表 示 す る.グ ラ フ を 並 べ て 表 示 す る こ と で,隣 り合 うグ ラ フ の 比 較 を 容 易 に して い る.画 面 分 割 に お け る 行 数,列 数 は ユ ー ザ が 自 由 に 調 整 で き る.特 に,行 数 お よび 列 数 を 共 に1に して 開 始 時 間 を 変 化 させ る と,紙 芝 居 の様 に グ ラ フ の 変 化 を 見 る こ と に な る.ま た,ユ ー ザ は 表 示 を 開 始 す る 時 間 を 変 化 させ る こ とで,表 示 され る グ ラ フ の 列 を 時 間 軸 に 沿 っ て ス ラ イ ドさせ る こ とが で き る. 4.3.ノ ー ド ・エ ッ ジ の 発 生 と 消 滅 の 表 現 WebRelievoは,ユ き る よ う,各 各Gt(p)に よ っ て,以 ー ザ が 各 時 間 の グ ラ フか ら前 後 に お け る変 化 を あ る 程 度 把 握 で ノ ー ドお よ び 各 辺 の 発 生 お よ び 消 滅 を 色 で 表 現 し て い る 。 お け る ノ ー ドお よ び 辺 は,Gt-1(p),Gt+1(p)に 存 在 す る か しな い か に 下 の よ う に 色 分 け さ れ て い る. .黒 色:Gt-1(p)お よ びGt+1(p)に 存 在 す る.黒 .赤 色:Gt-1(p)に 存 在 せ ず,Gt+1(p)に .灰 色:Gt-1(p)に は 存 在 す る が,Gt+1(p)に で 安 定 性 を 示 す. は 存 在 す る.tに お け る発 生 を 赤 で 示 す ． は 存 在 し な い.t+1に お け る 消 滅 を灰 色 で 表 現 す る. .薄 赤 色:Gt-1(p)に 存 在 せ ず,Gt+1(P)に も 存 在 し な い.tに お い て 発 生 し,す ぐ消 滅 す る こ と を 薄 赤 色 で 示 す. こ の よ う な 色 の 表 現 に よ っ て,時 系 列 間 で の ノ ー ド ・エ ッ ジ の 発 生 ・消 滅 の 把 握 を 容 易 に 行 う こ と が で き る. ―21―