MapReduceによる2段階PageRank

DEIM Forum 2015 E5-4
MapReduce による 2 段階 PageRank
武井
良太†
新美
礼彦††
† 公立はこだて未来大学システム情報科学研究科 〒 041–8655 北海道函館市亀田中野町 116 番地 2
†† 公立はこだて未来大学システム情報科学部 〒 041–8655 北海道函館市亀田中野町 116 番地 2
E-mail: †{g2114020,niimi}@fun.ac.jp
あらまし
ウェブグラフを再構築することで, ランキングアルゴリズムを実行する際に必要となる解析時間を短縮する
ことが可能である. 再構築手法に関しては,LittleWeb と呼ばれる再構築手法が提案されており, エッジ数とノード数を
削減し PageRank の解析時間を短縮することに成功している. これに対し本研究では, エッジ数とノード数の削減だけ
でなく, ウェブグラフを PageRank の解析が並列分散処理可能なグラフへ再構築を行い,PageRank の解析を行う際に
並列分散処理を用いることで, 解析に必要な時間を短縮する手法を提案する. 本提案手法では, ウェブグラフのノード
を SCAN により Cluster と Hub,Outlier に分別し,Cluster と Hub で構成されるグラフと Cluster に属するノードで構
成されるグラフにウェブグラフを再構築する.Cluster に属するノードで構成されるグラフを解析する際, 各 Cluster は
関係性が無いため並列分散処理が可能になり,PageRank の解析時間が短縮できる. 本稿では, 提案手法を MapReduce
で実装し解析時間と PageRank 値の差の考察を行った.
キーワード
グラフマイニング, MapReduce, Hadoop, PageRank
1. は じ め に
重要度の低いウェブページであるとみなし, 再構築対象から外
す.Cluster に属するノードのランキングを求める際,Cluster 外
ウェブグラフとはウェブをグラフ構造化したものであり, ノー
に接続されているエッジは無視するため, 各 Cluster 間には関
ドをウェブページ, エッジをリンクで表現したものである. ウェ
係性が無くなり, 並列分散処理が可能となる. 提案手法により,
ブグラフを解析することで知見を導出することが盛んに行われ
ランキング上重要でないノードである Outlier をランキング
ている. 近年では, ノード数とエッジ数が数億個になるグラフが
算出対象から外すことで, 計算対象となるノード数とエッジ数
存在している. 例えば Netcraft は 2014 年 10 月の時点で, 全世界
の削減に成功した. 更に,Cluster に属するノードのランキング
で少なくとも 10 億ページ以上存在すると報告している [1]. ウェ
を求める際,PageRank 値の算出に並列分散処理を用いること
ブグラフは大規模になっており, 解析にかかる時間は膨大にな
ができ, 解析時間の高速化が可能になる. 本稿では, 提案手法を
る. そのため, 大規模なグラフに対して解析時間を短縮する手法
MapReduce で実装し解析時間と PageRank 値の誤差の考察を
が必要とされている. 解析時間を短縮する手法 [2], [3], [4], [5], [6]
行った.
は複数あるが, その内の 1 つとしてウェブグラフを再構築し
解析時間を短縮する手法が挙げられる. 本研究では, ランキン
2. 先 行 研 究
グアルゴリズムである PageRank の解析時間の短縮を目標と
大規模なウェブグラフを再構築することは, ウェブグラフを
し,PageRank の解析を並列分散化出来るような形状にグラフを
用いる解析手法において重要な技術である. ウェブグラフの再
再構築, 解析に必要な時間を短縮する手法を提案する. 本提案手
構築は大きく分けると, 符号化による手法と構造改良による手
法は, ウェブグラフをグラフの密構造部分を切り出したクラス
法の 2 種類に分かれる.
タに属するノードで構成されるグラフと, 各クラスタがエッジ
2. 1 符 号 化
を多く集めるハブを介してつながりを持つグラフに再構築する
符号化による手法は既存のデータ圧縮を使用するか, ウェブ
ことで, 並列分散処理が可能となる. クラスタリング手法は,Xu
グラフの特徴を用いる手法である.P. Boldi らはウェブグラフの
らが提案した SCAN [7] を用いる.SCAN は構造的類似度に基
特徴と WebGraph [8] という名の手法を提案した. ウェブグラ
づいたグラフクラスタリング手法の 1 つであり, ウェブグラフ
フの特徴として, 局所性と類似性, 連続性を挙げている.
のノードを Cluster と Hub,Outlier に分別する. 構造類似度の
・局所性
下限値を示す閾値と,Cluster の最小ノード数を示す閾値を用い
多くのウェブページは同じホスト内のページに誘導するための
て Cluster を作成する.Cluster に属さなかったノードを 2 つ以
リンクを含んでいる. 例えば,“home”,“next”,“previous”,“up”
上の Cluster とつながりがあるノードを Hub とし,1 つのみの
などのリンクが挙げられる. 例で上げたリンクは同じホスト内
Cluster とつながりがあるノードを Outlier と分別する.SCAN
でリンクされることが多い. つまり, リンク元とリンク先のウェ
の結果を用いてウェブグラフを Cluster と Hub で構成される
ブページの URL を比較すると先頭文字列 (ホスト名) が一致し
グラフと,Cluster に属するノードで構成されるグラフにウェブ
やすく, 局所性が現れる.
グラフを再構築する. 再構築する際,Outlier であったノードは
・類似性
成功している. 構造改良による手法は, ノード数とエッジ数を削
同じホストのウェブページは似たようなウェブページにリン
減することが出来かつ,PageRank の解析時間を短縮することが
クを持つ傾向がある. 例えば, 共通のテンプレートで作成される
可能である. よって本研究では,PageRank の解析時間の短縮を
ページなどが挙げられる. 例で上げたページは同じ構造のペー
目標としているため構造改良による手法を用いる.
ジがたくさんあるため同じウェブページにリンクを貼ることが
2. 3 提案手法と関連研究の違いと特徴
多い. つまり, 同一ホスト名のウェブページのリンクの URL を
提案手法と関連研究の違いと特徴について述べる. 違いとし
比較すると URL が一致しやすく, 類似性が現れる.
て, 関連研究で取り上げた従来手法はエッジ数やノード数を削減
・連続性
し,PageRank の解析時間を短縮することに成功している. これ
ウェブページに含まれるリンクの URL は一定の固まりで現
に対し本研究では, エッジ数やノード数の削減だけでなく, ウェ
れる傾向がある. 例えば, 大量の写真を掲載しているページが挙
ブグラフを PageRank の解析が並列分散処理可能なグラフへ再
げられる. 例で上げたページはある一定の連続したリンクの固
構築を行い,PageRank の解析を行う際に並列分散処理を用いる
まりが存在する. つまり,URL を辞書順に整列し順に ID を割り
ことで, 解析に必要な時間を短縮する手法を提案する.
当てると数字が連続し, 連続性が現れる.
特徴として,Outlier であったノードをランキング対象から外
P. Boldi らは上記の特徴を用いて, 連続性を利用した差分符
している点と,Cluster に属するノードのランキングを求める時
号化と, 局所性と類似性を利用したランレングス圧縮を用いた手
に並列分散処理可能な点である. ウェブグラフを再構築する際,
法を提案している. これにより,1 リンクあたり 3.08bit に抑える
ランキング上重要でないノードである Outlier をランキング算
ことに成功している.S. Tei らは WebGraph の差分符号化の後
出対象から外すことで, 計算対象となるノード数とエッジ数の
算術符号を用いることで, ウェブグラフの情報量を WebGraph
削減に成功した. 更に,Cluster に属するノードのランキングを
よりも 2 割ほど多く削減することに成功している [9]. しかし, 符
求める際,PageRank 値の算出に並列分散処理を用いることがで
号化による手法では情報量を削減することは出来るが, ノード
き, 解析時間の高速化が可能になる.
数とエッジ数を削減出来ない. また, 解析する際復号化する必要
がありかえって PageRank の解析時間が増加してしまう. よっ
3. SCAN
提案手法で用いるクラスタリング手法の SCAN [7] について説
て本研究では, 符号化による手法は用いない.
2. 2 構 造 改 良
明する.SCAN はクラスタリング対象とするグラフ G = (V, E)
構造改良はウェブグラフの構造を一部組み替えることでノー
を解析し, 構造類似度の下限値を示す閾値 ε と,Cluster の最小
ド数やエッジ数を削減する手法である.G. Buehrer らは Virtual
ノード数を示す閾値μに応じた structure-connected cluster を
Node Miner [2] と呼ばれる, 架空のノード (以下,VN) をウェブ
作成する.Cluster に属さなかったノードは Hub か Outlier の分
グラフに挿入することでエッジ数を削減する手法を提案した.VN
別が行われる.
は図 1 のような完全 2 部グラフの中間に図 2 のように挿入する.
最初にすべてのノードに対して unclassfied のラベルを与え
これによって, リンクを集約しノードを削減している.Virtual
る.SCAN は unclassfied のラベルが付いているノードに対して,
Node Miner は完全 2 部グラフの探査に最小値独立置換族を利
そのノードが core であるかどうかの判定を行う.core ノードは
用している. これにより, ノード数約 7800 万, エッジ数約 3 億
Cluster の中心となるノードである.core であるか判断するため
のウェブグラフに対して, 約 1700 万の VN を挿入しエッジ数を
には, 対象となる unclassfied なノードの構造的隣接ノード集合
1/7 に削減出来たとしている.
を定め, 構造的類似度を計算, 閾値 ε を用いて ε-neighborhood
を算出することで core かどうか判断することが出来る. 以下に
構造的隣接ノード集合と構造的類似度,ε-neighborhood の定義
を記述する.
・構造的隣接ノード集合
v ∈ V であるとき, 構造的隣接ノード集合はノード v にエッジ
で接続するノードと, ノード v 自らで構成される集合 Γ(v) で表
される.
図1 圧
縮
前
図2 圧 縮
後
Γ(v) = {v ∈ V | {v, w} ∈ E} ∪ {v}
・構造的類似度
片瀬らは LittleWeb [3] と呼ばれる, 類似ノード集約による
ウェブグラフ圧縮手法を提案した.LittleWeb は集約対象となる
ノードを探査するためのクラスタリング処理と, クラスタリン
グ結果を用いた構造改良の 2 ステップでウェブグラフを再構築
している. これにより, ノードを 67.3 ％, エッジを 56.3 ％削減
している. 更に,PageRank の解析時間を 67 ％短縮することに
|Γ(v)| が隣接ノード集合に含まれるノード数とすると, ノード
v, w 間の構造的類似度は σ(v, w) で表される.
|Γ(v) ∩ Γ(w)|
σ(v, w) = !
|Γ(v)||Γ(w)|
・ε-neighborhood
構 造 類 似 度 の 下 限 値 を 示 す 閾 値 ε を 用 い る こ と で,ε-
neighborhood と表される.
Nε (v) = {w ∈ Γ(v)|σ(v, w) >
= ε}
4. 提 案 手 法
本研究では, ウェブグラフを PageRank の解析が並列分散処
・Core
理可能なグラフへ再構築を行い,PageRank の解析を行う際に並
ε ∈ R,µ ∈ N,v ∈ V ,|Nε (v)| をノード v の ε-neighborhood の
列分散処理を用いることで, 解析に必要な時間を短縮する手法
ノード数とすると,core は COREε,µ (v) で表される.
を提案する. 提案手法によるウェブグラフ解析は,3 つのステッ
プで行われる.
COREε,µ (v) ⇔ |Nε (v)| ! µ
SCAN の判定によりノードが core であった時, この core ノード
にユニーク ID である clusterID のラベルを与え,core ノードを
中心に structure-connected cluster を作成する. ノードが core
でなかった時, そのノードに non-menber のラベルを与える.
SCAN は core ノードと判定されたノードから,structure
reachability で到達可能なノードが所属する Cluster に clusterID のラベルを与える. 最初に, キュー Q へ core ノードの
ε-neighborhood に含まれるすべてのノードを挿入する. 次に,
キュー Q へ挿入されたノードに対して,direct structure reach-
ability となるノードの集合である R を求める. 以下に direct
structure reachability と structure reachability の定義を記述
する.
・Direct structure reachability
ノード v とノード w における direct structure reachability は
Step 1
SCAN を用いて Web graph をクラスタリングし Cluster と
Hub,Outlier にノード分別する.
Step 2
PageRank の解析が並列分散処理可能にするため,Cluster
と Hub をノードに見立てた Compression graph と Cluster
に属するノードを用いたウェブグラフである Cluster graph
の 2 種類のグラフを作成し,Web graph を再構築する.
Step 3
Compression graph の PageRank 値を算出し,Cluster と
Hub によるランキングを作成する. その後,Cluster graph の
PageRank 値を算出し,Cluster 内のノードによるランキン
グを作成し, それぞれのランキングをマージする.
図 3 は提案手法の流れを図示したものである. 以降, それぞれ
のステップを詳しく説明する.
DirREACHε,µ (v, w) で表される.
DirREACHε,µ (v, w) ⇔ COREε,µ (v) ∧ Nε (v)
・Structure reachability
ε ∈ R,µ ∈ N,v ∈ V とすると, ノード v とノード w における
Structure reachability は REACHε,µ (v, w) で表される.
REACHε,µ (v, w) ⇔
∃1 , ...vn ∈ V : v1 = v ∧ vn = w ∧
∀i ∈ {1, ..., n − 1} : DirREACHε,µ (vi , vi+1 )
ノード集合 R を求めるには, キュー Q に含まれる全てのノー
ドの構造的隣接ノード集合に対して, 構造的類似度を計算する.
最後にノード集合 R に含まれるノードの所属する Cluster が
unclassfied の時, ノードをキュー Q へ挿入する. ノード集合 R
に含まれるノードが unclassfied, または non-menber の時, 作成
した clusterID のラベルを与える. 一連の処理をキュー Q がな
くなるまで行い,structure-connected cluster を作成し続ける.
structure-connected cluster の 作 成 が 終 了 し た ら,non-
menber のラベルが付いたノードに対して Hub と Outlier の分
別を行う.non-menber のラベルが付いたノードが 2 つ以上の異
なる Cluster と接続している場合, そのノードに対して Hub の
ラベルを与える.1 つのみの Cluster と接続している場合, その
ノードに対して Outlier のラベルを与える.
以上より, 全てのノードに対してラベルが付け終わり SCAN
によるクラスタリングは完了する.
図3
提案手法の流れ
4. 1 クラスタリング
4. 3 PageRank
SCAN を用いてクラスタリングを行う. 構造的類似度の下
PageRank での解析ステップは 3 つのステップに分かれてい
限値を表す閾値 ε と Cluster の最小ノード数を表す閾値μに
る.1 つ目のステップは Compression graph の解析,2 つ目のス
応じた Cluster を作成する.Cluster に属さなかったノードに対
テップは Cluster graph の解析,3 つ目のステップはランキング
して 2 つ以上の Cluster とエッジで接続されているノードは
のマージである.2 つ目の Cluster graph の解析は並列分散処理
Hub とし,1 つのみの Cluster とエッジで接続されているノード
を用いる. 最初にノードに見立てた Cluster と Hub で構成さ
は Outlier と分別する. クラスタリング処理の例である図 4 は
れたウェブグラフである Compression graph の PageRank 値
上段の Web graph に対して SCAN を実行し, 下段はノードを
を算出し,Cluster と Hub に対するランキングを求める. この
Cluster と Hub,Outlier に分別した後のグラフである.
時, 異なる 2 つの Cluster に属するノード間のエッジのみを考
慮し,Cluster に属するノード間のエッジは無視する. また, 異な
る Cluster 間や Cluster と Hub 間のエッジが 2 つ以上存在す
る場合, エッジに対して本数分の重みをつける. 次に Cluster に
属するノードのウェブグラフである Cluster graph の PageR-
ank 値を算出し,Cluster に属するノードのランキングを求め
る. この時,Cluster 外に接続されているエッジは無視する. 最後
に, それぞれの解析結果であるランキングのマージ処理である
が,Compression graph のランキングを元に Cluster 部分に対
応する Cluster graph のランキングを挿入し, ウェブグラフの
ランキングを作成する. 解析のステップの例である図 6 は, 初め
に Compression graph を PageRank を用いてランキングを作
成. 次に,Cluster graph を PageRank を用いてランキングを作
図 4 クラスタリングの流れ
成. この時,Hub に関しては特に操作は行わない. 最後に, それぞ
れの解析結果であるランキングをマージしている.
4. 2 再 構 築
SCAN の結果を用いて Web graph を再構築する.Cluster
と Hub をノードに見立てたウェブグラフである Compression
graph と,Cluster に属するノードで構成されたウェブグラフで
ある Cluster graph の 2 種類を作成する. 再構築する際, ランキ
ング上重要でないノードである Outlier をランキング算出対象
から外す. 再構築の例である図 5 は 4.1 で SCAN を用いてノー
ドを分別した上段のグラフより, ノードに見立てた Cluster と
Hub のみで構成される Compression graph と,Cluster に属す
るノードで構成される Cluster graph に再構築したものを下段
に示す.
4. 4 MapReduce による提案手法の並列分散化
本提案手法はノード数が億単位以上のウェブグラフが解析対
象となるため, クラスタリング処理と PageRank による解析は
MapReduce を用いた並列分散処理を行う方針を取る.MapReduce は大規模データを並列分散処理するためのフレームワー
クである.Map 処理でデータを定義した手法で分割を行い,Re-
duce 処理で定義した手法で分割したデータを収集し, 処理を
行う.SCAN に関しては PSCAN [10] で,PageRank に関しては
Data-intensive text processing with MapReduce [11] で既に
MapReduce で定義されているため,Web graph の再構築であ
る Cluster graph と Compression graph に関して MapReduce
での処理を考える. 表 1 にて本章で使用する用語の定義を示す.
表1
用語
Label
用語の定義
定義
SCAN によって与えられたノードに付いている
Cluster ID や Hub ID, Outlier
Node ID
各ノードに固有で与えられいる ID
Cluster ID 各クラスタに固有で与えられいる ID
Hub ID
Outdegree
各ハブに固有で与えられいる ID
ノードから出ているリンク先の Node ID の集合
ま ず,Cluster graph に お け る MapReduce に つ い て 述 べ
る.Key/Value は表 2 に示すものを用いる.Cluster graph に
おける MapReduce は, まず Map 処理として, 入力で Label を
Key とし, それぞれの Label 対応する Node ID を Value に挿入
図 5 再構築の流れ
する. 出力で, 入力の Value で読み込んだ Node ID に対応する
Outdegree を追加する. 次に Reduce 処理として, 入力で Key は
図 6 解析の流れ
Cluster ID を収集する. 出力で,Value に格納されている Node
は 0.20.205 である.m1.small のスペックは CPU が Intel Xeon
ID を Key に上書きする.Reduce 処理を Cluster ID ごとに繰り
E5430 x 1core, メモリが 1.7GB である. 用いたグラフデータ
返し, 全ての Cluster graph を作成する.
はノード数 27, エッジ数 106 のグラフである. 以下の図 7 は用
表 2 Cluster graph における Key/Value
Map
Key
Value
入力
Label
Node ID
出力
Label
Node ID, Outdegree
入力
Reduce 出力
Cluster ID Node ID, Outdegree
Node ID
いたグラフデータである. このグラフデータを用いた理由とし
て,SCAN で Cluster が殆ど作成されないグラフデータでは, 本
提案手法の検証が難しいためである. そのため,Cluster が作成
されやすい本グラフデータが, 本提案手法を検証する上で適し
ているためである.
Outdegree
次に,Compression graph における MapReduce について述
べる.Key/Value は表 3 に示すものを用いる.Map 処理に関し
ては Cluster graph と同じ処理を行う.Reduce 処理として, 入
力で Key から Hub ID を収集する. 収集後,Value の Outdegree
から, どのクラスタと接続しているか調べ, 接続しているクラ
スタの Cluster ID を出力の Value に追加する.Reduce 処理を
Hub ID ごとに繰り返し,Compression graph を作成する.
表 3 Compression graph における Key/Value
Key
Map
入力
Label
Node ID
出力
Label
Node ID, Outdegree
入力
Hub ID Node ID, Outdegree
Reduce 出力 Hub ID
5. 実
Value
Cluster ID
図7
験
グラフデータに対して提案手法による解析を行い, 並列分散
使用グラフ
5. 1 解 析 時 間
処理による PageRank 算出が可能であるかどうか検証する. ま
グラフデータに対して提案手法を行った際に掛かった PageR-
た,PageRank 値の誤差より提案手法の有用性を考察した.SCAN
ank 値算出時間と, 標準的な PageRank による PageRank 値算
の閾値は ε = 0.7, μ = 2 を用いた. 実験環境は,Amazon Web
出時間を比較する. 比較結果は表 4 に示す. 比較より両手法の解
Services の Amazon Elastic MapReduce を利用した. 用いた
析時間に差は殆ど無く, 提案手法による解析は有効であると示
インスタンスは m1.small,Hadoop のディストリビューション
した.
表 4 処理時間比較結果
Hub 間のエッジが 2 つ以上存在する場合エッジに対して本数分
処理時間
の重みをつけている. そこで重みの下限値の閾値を設定し, ハブ
PageRank 5 分 12 秒
とのエッジが少ないクラスタは重要なページではないとみなし,
提案手法
5 分 00 秒
閾値に満たない重み付きエッジを所有しているクラスタを切り
落とすことで, 更にノードとエッジが削減でき PageRank の解
5. 2 PageRank 値の差
析が高速化出来ると考える.
本提案手法を PageRank 値の誤差より提案手法の有用性を考
3 つ目の考察はクラスタリングに関する考察である. 提案手法
察する. 各ノードの PageRank 値誤差を図 8 に示す. 実験結果
は,PageRank によるウェブグラフの解析に前処理となるウェブ
から切断されたエッジが無いノードは PageRank 値が上昇して
グラフのクラスタリング作業があるため, 単純に PageRank に
おり, 切断されたエッジがあるノードは PageRank 値が降下し
よる解析よりも処理数が多くなっている. そのため, クラスタリ
ている. 特に Outlier のタグが付いたノードとエッジがあった
ング処理は短時間で終わることが望ましい. 実装する際,SCAN
ノードに関しては,PageRank 値の降下が顕著であった. これよ
の処理を MapReduce に対応させた PSCAN [10] や, クラスタ
り, 切断されたエッジが無いノードと, 切断されたエッジがある
係数が大きい現実のグラフ構造に対してクラスタリング処理時
ノードの PageRank 値の差を縮める課題がある. また,Outlier
間を短縮できる改良型 SCAN [12] があり, これらを用いること
のタグが付いたノードとエッジがあったノードに対しても対策
でより処理時間を短縮することが可能になるのではないかと推
の必要がある.
測される. さらに, 並列分散処理に適したクラスタリング方法を
用いることでも処理時間を短縮することが可能であると考える.
また, 現在ウェブグラフをクラスタリングするために SCAN を
用いているが, 他のクラスタリング手法でも提案手法が実現可
能であれば, 本提案手法を一般化することが可能となる. 可能に
なれば, ウェブグラフの性質に適したクラスタリング手法を適
用することが出来る.
7. お わ り に
本研究では, ウェブグラフを PageRank の解析が並列分散処
理可能なグラフへ再構築を行い,PageRank の解析を行う際に
並列分散処理を用いることで, 解析に必要な時間を短縮する手
法を提案した. 提案手法によるウェブグラフ解析手法は,3 つの
ステップで行われる.1 つ目のステップは,SCAN を用いて Web
graph をクラスタリングし Cluster と Hub,Outlier にノード分
別する.2 つ目のステップは,PageRank の解析が並列分散処理
可能にするため,Cluster と Hub を用いた Compression graph
図8
PageRank 値の誤差
と Cluster に属するウェブグラフである Cluster graph の 2 種
類のグラフを作成,Web graph を再構築する.3 つ目のステッ
6. 考
察
提案手法に対して 4 つの考察すべき点がある.
プは,Compression graph の PageRank 値を算出し,Cluster と
Hub によるランキングを作成する. その後,Cluster graph の
PageRank 値を算出し,Cluster 内のノードによるランキング
1 つ目の考察は解析対象となりうるウェブグラフを考え
を作成, マージする.Cluster に属するノードのランキングを求
る.SCAN は相互に密な関係性, すなわち相互に密なエッジがあ
める際,Cluster 外に接続されているエッジは無視するため, 各
る部分を Cluster として抜き出す. よって, 解析対象とするウェ
Cluster 間には関係性が無くなり, 並列分散処理が可能となる.
ブグラフには全体に粗密が存在するグラフである必要性がある
提案手法により, ランキング上重要でないノードである Outlier
と考える. 具体的な解析対象となるウェブグラフは, ウェブを普
をランキング算出対象から外すことで, 計算対象となるノード
遍的にクローリングしたグラフであることが望ましい. 提案手
数とエッジ数の削減に成功した. 更に,Cluster に属するノード
法で PageRank 解析の高速化が望めないウェブグラフは, 単一
のランキングを求める際,PageRank 値の算出に並列分散処理
ドメインを対象としたグラフやブログサイトをクローリングし
を用いることができ, 解析時間の高速化が可能になる. 本稿で
たグラフは, クラスタが作成されにくく解析時間が短縮しづら
は, 提案手法を MapReduce で実装し解析時間と PageRank 値
いと考えられる.
の誤差の考察を行った. 解析時間に関しては, 提案手法による
2 つ目の考察はエッジの扱いに関する考察である. 現在は
PageRank と標準的な PageRank では殆ど無く提案手法によ
SCAN の手法を使用し,Cluster とのエッジに注目して Hub と
る解析は有効であると示した. また,PageRank 値の差に関して
Outlier の分別を行っており, 異なる Cluster 間や Cluster と
は,Outlier であるノードとエッジがあったノードは差が大きく,
解析時に対策の必要がある.
今後はウェブグラフの実データに対して提案手法で PageRank
値を算出し, 本提案手法が有用的であるかどうか実験を行う予
定である. また, 並列分散処理に適したクラスタリング方法を用
いることで, より処理時間を短縮することが可能であると思わ
れるため, 追加で実験を行う予定である.
文
献
[1] Netcraft: October 2014 Web Server Survey.
[2] Buehrer, G. and Chellapilla, K.: A scalable pattern mining approach to web graph compression with communities,
Proceedings of the 2008 International Conference on Web
Search and Data Mining, ACM, pp. 95–106 (2008).
[3] 片瀬弘晶，上田高徳，山名早人：LittleWeb 類似ノード集約による
Web グラフ圧縮手法，The 2nd Forum on Data Engineering
and Information Management, DBSJ, pp. E1–4 (2010).
[4] Kohlschütter, C., Chirita, P.-A. and Nejdl, W.: Efficient
parallel computation of pagerank, Advances in information
retrieval, Springer, pp. 241–252 (2006).
[5] Wicks, J. and Greenwald, A.: Parallelizing the computation
of pagerank, Algorithms and Models for the Web-Graph,
Springer, pp. 202–208 (2007).
[6] Kamvar, S., Haveliwala, T., Manning, C. and Golub, G.:
Exploiting the block structure of the web for computing
pagerank, Stanford University Technical Report (2003).
[7] Xu, X., Yuruk, N., Feng, Z. and Schweiger, T. A.: Scan:
a structural clustering algorithm for networks, Proceedings
of the 13th ACM SIGKDD international conference on
Knowledge discovery and data mining, ACM, pp. 824–833
(2007).
[8] Boldi, P. and Vigna, S.: The webgraph framework I: compression techniques, Proceedings of the 13th international
conference on World Wide Web, ACM, pp. 595–602 (2004).
[9] シュウテイ， 片山薫：算術符号を用いたウェブグラフ表現の
ための圧縮方法，The 6nd Forum on Data Engineering and
Information Management, DBSJ, pp. D6–1 (2014).
[10] Zhao, W., Martha, V. and Xu, X.: PSCAN: A Parallel Structural Clustering Algorithm for Big Networks in
MapReduce, Advanced Information Networking and Applications (AINA), 2013 IEEE 27th International Conference
on, IEEE, pp. 862–869 (2013).
[11] Lin, J. and Dyer, C.: Data-intensive text processing with
MapReduce, Synthesis Lectures on Human Language Technologies, Vol. 3, No. 1, pp. 1–177 (2010).
[12] 塩川浩昭，藤原靖宏，鬼塚 真：構造的類似度に基づくグラフク
ラスタリングの高速化，The 6th Forum on Data Engineering
and Information Management, DBSJ, pp. D6–2 (2014).