DEIM Forum 2014 D6-4

部分グラフに基づく効率的な PageRank 推定
坂倉

悠太†

山口

祐人†

天笠

俊之††

北川

博之††

† 筑波大学大学院システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1–1–1†† 筑波大学システム情報系情報工学域 〒 305–8573 茨城県つくば市天王台 1–1–1
E-mail: †{yuuta,yutoymgc}@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp
あらましPageRank はグラフ上のノードの重要度を評価するリンク構造解析手法であり，様々な分野で用いられている．しかし，PageRank には計算コストが大きいという問題がある． 一方で，一部のノードの重要度だけが必要とされる場合が多い．そのため，グラフ全体の情報を用いずに特定のノードの PageRank 値を推定する手法がいくつか提案されている．具体的には，Chen らの手法は特定のノードを含む部分グラフを作成し，その PageRank 値を推定する．しかし，部分グラフを作成するために反復計算を何度も繰り返すため，その計算コストはまだ大きい．本稿では，反復計算を行わずに再帰的な計算を用いることで，効率的に部分グラフを作成する手法を提案する．評価実験により，提案手法は推定精度を維持しながら効率的に PageRank 値を推定できることを示した．
キーワード

PageRank，推定，リンク構造解析，データマイニング，情報検索

Yuta SAKAKURA† , Yuto YAMAGUCHI† , Toshiyuki AMAGASA†† , and Hiroyuki KITAGAWA††† Graduate School of Systems and Information Engineering, University of Tsukuba
1–1–1 Tennodai, Tsukuba, Ibaraki, 305–8573, Japan†† Faculty of Engineering, Information and Systems, University of Tsukuba
1–1–1 Tennodai, Tsukuba, Ibaraki, 305–8573, Japan
E-mail: †{yuuta,yutoymgc}@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp

1. は じ め にの時間的な変化を調べたい場合や，特定のコミュニティ内における重要なノードを調べたい場合などが挙げられる．このようPageRank [13] はリンク構造解析手法の一つであり，グラフ上な場合，注目しているノード（群）以外の重要度は必要ではなのノードの重要度を評価する手法である．PageRank は，Webい．そのため，必要なノードの重要度だけを高速に計算できる

検索 [6] やソーシャルネットワーク分析 [15]，バイオインフォと理想的である．

マティクス [12] などの様々な分野に用いられている．しかし，この問題に対して，グラフ全体の情報を用いずに特定のノー

PageRank は様々な分野に応用されている反面，計算コストがド（対象ノード）の PageRank 値を計算する手法 [4], [5], [8] が大きいという問題がある．そのため，巨大なグラフに対して提案されている．Chen ら [8] は初めてこの問題に取り組んだ．

PageRank を計算すると，計算コストが膨大になってしまう．

Chen らは，ユーザがノード v の ID を与えると，ノード v の

この問題に対して，PageRank の計算の高速化についての研究

子ノードと親ノードを取得できる fetch 操作によってノードのがされている [2], [10], [11]．

情報を取得する環境を想定した．fetch 操作の回数が小さいほさらに，PageRank の計算にはグラフ全体の情報が必要であ

ど，取得するノードの情報が少ないため，fetch 操作の回数をるが，この点が問題になることがある．すなわち，グラフ全体最小にすることを目指した．Chen らの手法では，対象ノードの情報を取得することが困難な場合がある．例えば，検索エンを含む部分グラフを作成し，その部分グラフを用いて対象ノー

ジンが Web ページをクロールする場合，クロールされたデードの PageRank 値を推定する．Chen らは，あるノードが与え

タは複数のデータセンターに分割して保存される．それゆえ，る対象ノードの PageRank 値への影響（影響力）を考慮しなが膨大なデータ量とデータの転送コストのため，データ全体につら部分グラフを作成した．部分グラフの作成後，部分グラフ内

いての分析を行うことは困難である．

で PageRank を計算することで，対象ノードの PageRank 値

また，ユーザは全てのノードではなく一部のノードの重要度を推定する．しかし，部分グラフの作成する過程において，各だけを必要とすることが多い．例えば，特定のノードの重要度

ノードの影響力を計算するために何度も反復計算を行うため，

Chen らの手法はまだ時間がかかる．そのため，部分グラフサ

グラフに含まれていないノード群を一つのノードに凝集した．

イズは PageRank 値の推定精度に影響を与える一方で，部分グ

対象部分グラフと凝集されたノードから構成されるグラフを用

ラフの作成時間にも影響を与える．

いて，PageRank 値を推定した．Xue ら [17] は，対象部分グラ

本稿では，対象ノードの PageRank 値をより効率的に推定す

フとユーザのアクセスパターンを用いて新しい部分グラフを作る手法を提案する．具体的には，Chen らの手法を参考にしな成し，その部分グラフを用いて PageRank 値を推定した．これ

がら，より効率的に部分グラフを作成する．あるノードの影響

らの研究は部分グラフについて注目しているが，本研究は特定

力はそのノードがエッジを張っているノードの影響力を用いてのノードに注目している点が異なる．

再帰的に計算することができる．この特徴を用いることで，反グラフ中の全てのノードの PageRank 値を推定する手法も提復計算を行わずに部分グラフを作成することができる．これに案されている [7]．Broder ら [7] は，グラフ凝集を用いた PageR-より，提案手法は PageRank 値の推定精度を維持したまま，効ank 値の推定手法を提案した．Broder らは，ホストが同じ Web

率的に対象ノードの PageRank 値を推定することができる．

ページを一つのノードに凝集することで，ホストグラフと呼ば提案手法の性能を評価するために Twitter（注 1）と Web グラフ

れる，グラフ全体の概略のグラフを作成した．そして，ホストのデータセットを用いて評価実験を行った．実験結果より，提案

グラフを用いて，全てのノードの PageRank 値を推定した．

手法は推定精度を維持しながら，高速に対象ノードの PageRank
値を推定できることが分かった．具体的には，Chen らの手法

3. Chen らの PageRank 推定手法と比較して，提案手法は精度を維持したまま，最大で約 3.2 倍

3. 1 概高速に PageRank 値を推定することができた．

Chen らの手法 [8] は，特定のノードの PageRank 値の推定

本稿の構成は以下の通りである．2. 節で関連研究について説要を目的とした手法である．Chen らの手法では，PageRank 値

明し，3. 節で Chen らの手法について説明する．4. 節で影響力を推定したいノード（対象ノード）と対象ノードの周囲のノーを定義し，5. 節で提案手法について説明する．6. 節で評価実験

ド，これらのノードと繋がっているエッジから構成される部分を行い，7. 節でまとめを述べる．

グラフ（局所グラフ）を構成する．その後，構成した局所グラ

2. 関 連 研 究Chen ら [8] は，部分グラフを用いて対象ノードの PageRank 値を推定する手法を提案した．Chen らは，対象ノードのフを用いて対象ノードの PageRank 値を推定する．

Chen らは，fetch 操作によってノードの情報を取得する環境を想定した．fetch 操作では，ノード v の ID が与えられると，
以下の情報を取得することができる．

PageRank 値の推定に必要なノードを部分グラフに追加してい•ノード v から出ているエッジとその接続先のノード ID

くことで，部分グラフを作成した．作成した部分グラフ内で•ノード v に入っているエッジとその接続元のノード ID

PageRank を計算することで，対象ノードの PageRank 値を推

また，ノード v と繋がっているエッジを取得することができ定した．詳細は 3. 節で説明する．本研究とは，部分グラフの作るため，ノード v の入次数と出次数を計算することもできる．

成方法が異なる．

Chen らは，fetch 操作の回数を計算コストの指標として用いた．

Bar-Yossef ら [4] は，部分グラフを作成せずに対象ノードのChen らの手法は，“局所グラフの作成” と “PageRank 値のPageRank 値を推定する手法を提案した．Bar-Yossef らは，対推定” の二つの処理に分かれている．それぞれの処理について，

象ノードからエッジを逆方向にたどりながら，そのノードが対象

3. 2 節と 3. 3 節で説明する．

ノードに与える PageRank 値を計算した．計算した PageRank

3. 2 局所グラフの作成

値を加算していくことで，対象ノードの PageRank 値を推定

まず，対象ノードからエッジを逆方向にたどっていくことでした．しかし，Bar-Yossef らは推定精度に関する評価を行って部分グラフを拡大し，局所グラフを作成する．初期部分グラフ

いなかった．また，Bressan [5] らは，推定した PageRank 値

は対象ノードだけを含む部分グラフである．まず，対象ノードに基づいて k 個のノードをランキングするという問題についに対して fetch 操作を行い，対象ノードの情報を取得する．そて調査した．Bressan らは Bar-Yossef ら [4] の手法を改善した

して，対象ノードに入っているエッジの接続元のノードを部分手法を用いて評価実験を行った．しかし，Bressan らは他の関グラフに追加する．この操作をノードの展開と呼ぶ．次に，新連手法との比較を行わなかった．本研究は部分グラフを用いてしく部分グラフに追加されたノードに対して fetch 操作を行い，PageRank 値を推定している点が，これらの研究とは異なる．

それらのノードが展開の基準を満たしているかを判定する．そまた，特定の部分グラフ（対象部分グラフ）内のノード

して，展開の基準を満たしているノードだけを展開する．このの PageRank 値に注目した研究も行われている [9], [16], [17]．

時，各ノードにおいて展開の判定は一度しか行われない．そのDavis ら [9] は，対象部分グラフにエッジを張っているノードをため，一度展開をしないと判定されたノードは，以降の部分グ追加することで，対象部分グラフを拡大した．拡大した対象部

ラフを拡大する過程において，再び展開の判定をされることは分グラフ内で PageRank を計算することで，対象部分グラフ内ない．展開の基準を満たすノードが無くなるまで，再帰的に追のノードの PageRank 値を推定した．Wu ら [16] は，対象部分加されたノードを展開していことで部分グラフを拡大し，局所グラフを作成する．

（注 1）：http://twitter.com/

局所グラフ作成の例を図 1 に示す．この例では，対象ノード

OPICアプローチの閾値：0.6
5

4
1

6

2

5

4

3

1

0

5

4
1

2

6

(2)

3

1

2

1

2

6

fetch

0

(3)

6

1

0

2
0

(1)

5

4

3

5

4

3

0

1

0
(5)

5

4

3

5

4

0
(4)

2
0

対象ノード

(1)

6

2

0

6 1
3 0

5

4
0

1

0.25

2
0

0

(2)

6 0

0.25
0.25 3 0.25
0

6
3

5

4

0

0

(6)

1

0.25

2
0

図 1 Chen らの手法を用いた局所グラフ作成の例

(3)

6 0

0.25 3 0.25
0

5

4
0

1

0.25

2
0

(4)

6 0

0.25 3 00.125

図 2 OPIC アプローチを用いた影響力推定の例

0 から部分グラフを拡大することで局所グラフを作成する．初期の部分グラフは対象ノード 0 だけを含む（図 1 の（1））．まず，対象ノード 0 に fetch 操作を行い，これを展開することで，影響力を入次数で割った値（影響力/入次数）を展開の基準とし

ノード 1, 2, 3 が部分グラフに追加される．
（図 1 の（2））．次に，て用いた．影響力/入次数が閾値以上であるノードを展開した．

ノード 1, 2, 3 に対して fetch 操作を行い，展開の基準を満たし

影響力の正確な計算は計算コストが大きいため，Chen らているかどうかを判定する．ここでは，ノード 2, 3 だけが展開

は OPIC アプローチ [1] を用いて，以下の手順で影響力を推定の基準を満たしたとする（図 1 の（3））．ノード 2, 3 を展開すした．

ることで，ノード 5, 6 が新しく部分グラフに追加される（図 1（ 1 ） 影響力を推定したいノード v にスコア 1 を与える．

の（4））．そして，ノード 5, 6 が展開の基準を満たしているか（ 2 ） ノード v のスコアを，ノード v から出ているエッジにどうかを判定する．ここでは，ノード 5, 6 の両方が展開の基準

よって遷移させる．この時，出力エッジによって局所グラフのを満たさなかったとする（図 1 の（5））．展開の基準を満たす

外部へ遷移するスコアは無視する．

ノードが無くなったため，部分グラフ部分グラフの拡大を終了（ 3 ） 対象ノードを除いた，最大のスコアを持つノードをラする．結果として，図 1 の（6）の局所グラフが作成される．

ンダムに 1 つ選択し，そのノードのスコアを操作 2 と同様に遷局所グラフは三種類のノードとエッジを含んでいる．一つ目

移させる．

のエッジは入力エッジと呼ばれる局所グラフ外から局所グラフ（ 4 ） 対象ノード以外のノードが持つスコアの合計が閾値未内へ入ってくるエッジ，二つ目のエッジは出力エッジと呼ばれ満になるまで操作 3 を繰り返す．

る局所グラフ内から局所グラフ外へ出ていくエッジ，三つ目の（ 5 ） 終了時の対象ノードのスコアをノード v の対象ノード

エッジは内部エッジと呼ばれる局所グラフ内から局所グラフ内に対する影響力とする．

へのエッジである．また，入力エッジを張られているエッジを

OPIC アプローチでは，終了条件である閾値が変化すると，影境界ノードと呼ぶ．対象ノードと境界ノードを除く，局所グラ

響力の推定精度と計算時間が変化する．閾値が小さくなるほど，

フ内のノードを内部ノードと呼ぶ．図 1 の（6）の局所グラフ

影響力の推定精度が良くなるが，計算時間が長くなる．

は，7 本の出力エッジ（点線）と 4 本の入力エッジ（破線），11

OPIC アプローチを用いた影響力推定の例を図 2 に示す．図本の内部エッジ（実線）を持つ．また，対象ノードは 1 個，内1 の（5）のグラフにおいて，ノード 6 の影響力を推定する場

部ノードは 2 個，境界ノードは 3 個である．

合を考える．また，OPIC アプローチの閾値を 0.6 とする．ま展開の基準．Chen らは，効率的に部分グラフを拡大するた

ノード 6 のスコアを遷移させると，スコアは図 2 の（2）のよめに，ノードの対象ノードに対する影響力を考慮した．あるうに遷移する．この時，ノード 6 のスコアはノード 2, 3, 5 だけノードの対象ノードに対する影響力とは，そのノードが持つに遷移し，出力エッジによって遷移するスコアは無視する．そPageRank 値のうち，ランダムジャンプを除いて，最終的に対して，対象ノードを除く，最大のスコアを持つノードを選択し象ノードに到達する PageRank 値の割合のことである．影響力て，そのスコアを遷移させる．ここでは，ノード 2, 3, 5 のスコが大きいノードは対象ノードの PageRank 値の推定精度へのアが同じ（0.25）であるため，その中の一つをランダムに選択影響が大きい．また，影響力が大きいノードに対してエッジをする．ここでは，ノード 3 が選択されたとする（図 2 の（3））．

張っているノードも大きな影響力を持つと考えられる．さらに，

ノード 3 のスコアを遷移させると，スコアは図 2 の（4）のよう

Chen らは fetch 操作の回数を計算コストの指標として用いた．

に遷移する．ここで，対象ノード以外のノードのスコアの合計

そのため，入次数が大きなノードを展開すると，多くのノード（0.5 = 0.25 + 0.25）が閾値（0.6）未満であるため，OPIC アが新たに追加されるため，計算コストが大きくなる．そのため，プローチの処理を中止する．対象ノードのスコアが 0.125 であChen らは，計算コストと推定精度の両方を考慮するために，るため，ノード 6 の対象ノードに対する影響力は 0.125 とする．

ず，ノード 6 に対してスコア 1 を与える（図 2 の（1））．次に，

3. 3 PageRank 値の推定1

対象ノードの PageRank 値を推定する前に，境界ノードのPageRank 値を推定する．境界ノードは局所グラフ内からだけ

2ではなく，局所グラフ外からもエッジ（入力エッジ）を張られている．そのため，境界ノードの PageRank 値を直接計算す30

ることはできず，その PageRank 値を推定する必要がある．また，対象ノードの PageRank 値の推定精度は，境界ノードの影

図3

4
5

影響力の計算例

響力と境界ノードの PageRank 値の推定精度に影響される．そ


∑

1



inf (w, u)outdeg(v)

w∈Nv



のため，境界ノードの PageRank 値を精度良く推定することが重要である．Chen らは，ヒューリスティックな方法を用いて，境界ノードの PageRank 値を推定した．具体的には，境界ノードに入っている入力エッジから，PageRank 値 d/E が遷移してinf (v, u) =くると仮定した．ここで，d は PageRank におけるダンピング
ファクター，E はグラフ全体におけるエッジの総数である．ラ



0







1

v から u への
パスがある

(1)
v から u への
パスが無い
v=u

ンダムジャンプと局所グラフ内のノードから境界ノードに遷移

ここで，outdeg(v) はノード v の出次数，Nv はノード v がエッする PageRank 値は計算することができる．これにより，境界ジを張っているノードの集合である．すなわち，ノード v のノーノードの PageRank 値を計算することができる．

ド u に対する影響力は，ノード v がエッジを張っているノード

最後に，局所グラフ内で PageRank を計算することで対象

w のノード u に対する影響力の平均である．ただし，ノード v

ノードの PageRank 値を推定する．PageRank の計算の繰り返

からノード u へのパスが無い場合，ノード v の PageRank 値

しごとに，以下の操作を行う．

はノード u には到達できないため，ノード v のノード u に対す•推定した PageRank 値（d/E ）が入力エッジから境界ノードに遷移する．

•

ランダムジャンプと出力エッジによって局所グラフ外に遷移する PageRank 値を無視する．

PageRank の計算終了後の対象ノードの PageRank 値を，推定した対象ノードの PageRank 値とする．

3. 4 考察Chen らの手法では，局所グラフの作成における計算コストの方が PageRank 値の推定における計算コストよりも大きい．
なぜなら，局所グラフを作成する過程において，各境界ノードを展開するかどうかを判定するために，各境界ノードの影響

る影響力は 0 である．
図 3 を用いて，影響力の計算例を示す．ノード 1 のノード 0に対する影響力 inf (1, 0) を計算すると，

1(inf (3, 0) + inf (4, 0))2
1 1
1= · (inf (2, 0) + inf (0, 0) + inf (4, 0)) + · 0
2 3
2
1 1
1
1
1
= · inf (0, 0) + · 1 + · 0 =
6 1
6
6
3

inf (1, 0) =5. 提 案 手 法
5. 1 ア イ デ ア

力を一つずつ OPIC アプローチを用いて計算するためである．

4. 節の定義より，あるノードの影響力はそのノードがエッジ

そのため，局所グラフのサイズが大きくなるほど，計算コストを張っているノードの影響力を用いて計算することができる．

は大きくなる．さらに，局所グラフのサイズは対象ノードのそのため，再帰的に影響力を計算することで，反復計算を用い

PageRank 値の推定精度に影響を与える．それゆえ，局所グラずにノードの影響力を計算することができる．しかし，局所グフの作成における計算コストを小さくすることで，より効率的ラフを作成する過程において，あるノードがエッジを張っていに PageRank 値を推定することができると考えられる．

る全てのノードが局所グラフに追加されているとは限らない．

また，OPIC アプローチでは，ノードの影響力を推定する時そのため，提案手法では，局所グラフに追加されているノードに，すでに推定した影響力を用いていない．展開の判定を行っの影響力だけを用いてノードの影響力を推定する．例えば，図たノードの影響力はすでに推定されている．しかし，OPIC ア

1 の（5）を考える．この時，ノード 1, 2, 3 の影響力はすでにプローチでは，すでに推定した影響力を用いずに，反復計算に推定されている．そのため，ノード 5，6 の影響力は，ノードよって境界ノードの影響力を推定する．そのため，すでに推定

1，2，3 の影響力を用いて計算することができる．

した影響力を用いることで，より効率的に影響力を推定することができると考えられる．

4. 影響力の定義

しかし，影響力を推定したい境界ノードが複数あり，それらの境界ノード間にエッジが張られている場合に問題がある．な
ぜなら，それらの境界ノードの影響力はまだ推定されていないためである．例えば，図 1 の（5）では，ノード 5（6）の影響

ノード v のノード u に対する影響力とは，ノード v の PageR-

力を計算するために，ノード 6（5）の影響力が必要である．こank 値のうち，ランダムジャンプを除いて，ノード u に到達すのような場合，未知の影響力を変数とする連立一次方程式を用る PageRank 値の割合である．本稿では，ノード v のノード u

いて，ノードの影響力を表現する．そして，この連立一次方程に対する影響力 inf (v, u) を以下のように定義する．

式を解くことで，ノードの影響力を推定する．

5. 2 影響力の推定手法

では，ノード 0 を対象ノード，影響力の閾値を 0.5 とする（図 4

提案手法では，あるノードがエッジを張っている，局所グラフの（1））．

内のノードの影響力を用いて，そのノードの影響力を推定する．

まず，対象ノード 0 に fetch 操作を行い，対象ノード 0 にエッグラフ全体を G = (V, E)，対象ノードを vt ∈ V とする．また，ジを張っているノード 1，2，3 を局所グラフに追加する（図 4

現在の局所グラフを GS = (VS , ES )．さらに，C = {vi | これの（2））．そして，ノード 1，2，3 に fetch 操作を行ってノーから影響力を推定する境界ノード vi ∈ VS }，すでに影響力を推

ドの情報を取得し，これらのノードの影響力を計算する．ここ

定したノードの集合を W = VS − C とする．ノード vi ∈ C ので，C = {1, 2, 3}，W = {0} であり，各ノードについて以下の対象ノード vt ∈ W に対する影響力 αi は以下のように定義さことが分かる．

れる．

αi =





∑
∑
1

αj +
βk 
outdeg (vi ) v ∈C
v ∈W
j

i

k

(2)

i

βt = 1.0(3)

ノード

outdeg(i)

Ci

Wi

1

5

{2}

{0}

2

1

∅

{0}

3

2

∅

{0}

この表より，以下の連立一次方程式が得られる．
ここで，outdeg(vi ) はノード vi の出次数，Ci （Wi ）はノード

vi がエッジを張っている集合 C （W ）に含まれるノード集合，
αj （βk ）はノード vj ∈ C （vk ∈ W ）の影響力を表している．
式（2）では，ノード vi がエッジを張っている，局所グラフ
内のノード（Ci , Wi ）の影響力の合計をノード vi の出次数で割

1.0(α2 + 1.0)5
α2 = 1.0 · 1.0
1.0
α3 =
· 1.0
2

(4)

α1 =

(5)
(6)

ることで, ノード vi の対象ノード vt に対する影響力を計算しこの連立一次方程式を解くことで，各ノードの影響力 α1 = 0.4ている．これは，局所グラフ外のノードの影響力を合計してい（= β1 ），α2 = 1.0（= β2 ），α3 = 0.5（= β3 ）が得られる．影ない点を除けば，影響力の定義（式（1））と同義である．

響力の閾値は 0.5 であるため，閾値以上の影響力を持つノード

ノード vi が他の境界ノード vj ∈ Ci にエッジを張っている

2，3 を展開する（図 4 の（3））．

場合，ノード vi の影響力 αi についての式は未知数 αj を含む．

次に，ノード 2，3 を展開することで，ノード 5，6 が局所グ

そのため，影響力 αi を計算するために未知数 αj を計算する

ラフに追加される（図 4 の（4））．そして，ノード 5，6 に fetch必要がある．ここで，影響力についての式の数は未知数の数と操作を行ってノードの情報を取得し，これらのノードの影響力

同じ（|C| 個）であり，影響力についての式はグラフの位相をを計算する．ここで，C = {5, 6}，W = {0, 1, 2, 3} であり，各反映しているため線形独立である．すなわち，影響力について

ノードについて以下のことが分かる．

の式が線型従属になるような，グラフの接続関係のパターン

ノード

outdeg(i)CiWiは存在しない．そのため，各境界ノード vi ∈ C の影響力 αi

5

5

{6}

{1, 2, 3}

についての式を連立一次方程式として解くことで，影響力 αi

6

4

{5}

{2, 3}（i = 1, 2, ..., |C|）を計算することができる．
提案手法では，以下の手順で局所グラフを作成する．
（ 1 ） 対象ノード vt の影響力を 1 として，境界ノード集合

C を作成する．
（ 2 ） 集合 C 内の境界ノードの影響力についての式を連立

この表より，以下の連立一次方程式が得られる．

1.0(α6 + 0.4 + 1.0 + 0.5)
5
1.0
α6 =
(α5 + 1.0 + 0.5)
4
α5 =

(7)
(8)

一次方程式として解き，各境界ノードの影響力を計算する．

この連立一次方程式を解くことで，各ノードの影響力 α5 = 0.479（ 3 ） 各境界ノードの影響力と閾値を比較し，閾値以上の影（= β5 ），α6 = 0.495（= β6 ）が得られる（図 4 の（5））．閾

響力を持つ境界ノードを展開する．新しく局所グラフに追加さ値（0.5）以上の影響力を持つノードが無いため，局所グラフのれたノードを次の境界ノードとする．

作成を終了する．結果として，図 4 の（6）の局所グラフが得（ 4 ） 展開されるノードが無くなるまで，操作 2，3 を繰り

られる．

返す．

5. 4 考ここで，3. 節で説明した Chen らの手法とは異なり，展開の基

一般に連立一次方程式を解くための計算量は大きいため，提準として “影響力” を用いている．これは，評価実験において，案手法の計算コストも大きいと考えるかもしれない．連立一次“影響力/入次数” を用いたところ，全ての比較手法（詳細は 6. 1方程式をシンプルに解く場合の計算量は O(N 3 )（N は方程式の節）の性能が非常に悪かったためである．6. 節の評価実験にお数）である．しかし，展開の各ステップにおいて追加される境

いても，展開の基準として “影響力” を用いる．また，提案手

界ノードの数はあまり多くない．そのため，提案手法は OPIC

法と Chen らの手法では，影響力の推定方法が異なっているたアプローチよりも効率的に影響力を推定できると考えられる．

め，最終的に作成される局所グラフは異なる．

察

6. 評 価 実 験

5. 3 提案手法を用いた局所グラフの作成例
図 4 に提案手法を用いた局所グラフの作成例を示す．この例

本実験では，提案手法と Chen らの手法を比較し，提案手法

影響⼒の閾値：0.5
5

4

6

2

1

0
(1)

3

2

1

1

対象ノード

5

4

5

4

6

2

法と Chen らの手法に対して，展開の最大ステップ数 s の制限

6

5

4

3

1

0

3

(3)

5

4
1

0

2

6

5

4

3

(5)

•

対象ノードに対する影響力が閾値以上である．

•

対象ノードまでの距離が s 未満である．

対象ノードまでの距離が s 未満であるノードを展開すること

2

1

0

(4)

以下の二つの条件を満たすノードを展開する．

0

(2)

3

2

を設定した．具体的には，提案手法と Chen らの手法において，

6

で，対象ノードまでの距離が最大で s 以下であるノードを含む

6局所グラフが作成される．これにより，Naive な手法と比較して，提案手法と Chen らの手法は，精度を維持しながら，どの3くらい局所グラフサイズを小さくすることができるかを評価す

0(6)

ることができる．

6. 1. 4 実 験 方 法

図 4 提案手法を用いた局所グラフの作成例

まず，グラフ全体に対して PageRank を計算し，各ノードのが精度を維持しながら高速に PageRank を推定できることを検正確な PageRank 値を求めた．次に，PageRank 値を推定する

証する．

対象ノードをサンプリングした．本実験では，PageRank 値の6. 1 実 験 設 定

上位 1, 000 ノードから 100 ノードを対象ノードとしてランダ

6. 1. 1 データセット

ムサンプリングした．そして，各比較手法を用いて，サンプリ

本実験では，以下の二つのデータセットを用いる．

ングされた各対象ノードの PageRank 値を推定した．本実験で•Twitter ソーシャルグラフ（TSG）：TSG は，我々がは，Chen らの手法を参考にして，入力エッジから評価値 d/E

Twitter をクローリングして作成したデータセットである．一が遷移してくるとした．また，ダンピングファクター d の値を人のユーザをシードユーザとして選択し，シードユーザがフォ

0.85 に設定した．

ローしているユーザを幅優先探索で収集した．収集したユー

6. 1. 5 評 価 指 標

ザ数が 2, 500, 000 になったら収集を終了した．その後，収集さ本実験では，推定精度と計算コストの観点から比較手法を評れていないユーザへのエッジを削除した．TSG はノード数が価した．ノードの PageRank 値そのものよりもノードのランキ

2, 500, 000，エッジ数が 28, 810, 947 である．

ングの方に興味があるため，推定した PageRank 値に基づく•

Web グラフ（WG）：WG は Stanford Network Anal-ysis Platform (SNAP) が提供している Google の Web グラ
（注 2）

フ

のデータセットである．WG には，Web ページの ID と

Web ページ間に張られているリンクの情報が含まれている．
WG はノード数が 875, 713，エッジ数が 5, 105, 039 である．
6. 1. 2 実 験 環 境
本実験では，比較手法（6. 1. 3 節）を Python で実装した．連ノードのランキングについて評価する．
推定精度の評価指標として，スピアマンの順位相関係数 [14]を用いた．スピアマンの順位相関係数 ρ は以下のように定義さ
れる．

ρ=1−

6ΣD2
N3 − N(9)

ここで，D は正確な PageRank 値に基づくサンプリングしたを100 個の対象ノードのランキングと推定した PageRank 値に基用いた．また，実験に用いたコンピュータは，OS が Ubuntu

づくサンプリングした 100 個の対象ノードのランキングにおけ

13.04，CPU が Intel Core i7-3770 (3.40GHz)，メモリが 32GB

る同一ノードの順位差，N はノード数（本実験では 100）であであった．さらに，各手法においてグラフデータをメモリ上にる．順位相関係数 ρ の値が 1 に近いほど，推定した PageRank

読み込むように実装した．

値に基づくランキングは精度良く推定できていることを示して（注 3）

立一次方程式を解く時には，Python のライブラリ Scipy

6. 1. 3 比 較 手 法
本実験では，以下の三つの手法を比較した．

いる．
また，計算コストを評価するために，局所グラフサイズ，局•提案手法：5. 節で説明した提案手法．

所グラフの作成時間，PageRank 値の推定時間を用いた．局所•

Chen らの手法：3. 節で説明した Chen らの手法．ただグラフに追加されたノードだけに fetch 操作を行うので，局所

し，展開の基準として “影響力” を用いる．

•

Naive な手法：対象ノードまでの距離が s 以下であるノードを全て含む局所グラフを作成する手法．すなわち，全ての境界ノードを展開する．
また，本実験では，Naive な手法と比較するために，提案手

グラフサイズは fetch 操作の回数と同じである．また，各比較手法における局所グラフの作成にかかる時間と PageRank 値の推定にかかる時間を比較する．

6. 2 提案手法と Chen らの手法の比較
予備実験によって，ステップ数 s と Chen らの手法における OPIC アプローチの閾値を決定した．具体的には，TSG では，ステップ数は 4，OPIC アプローチの閾値は 0.5 を用いた．

（注 2）：https://snap.stanford.edu/data/web-Google.html

WG では，ステップ数は 3，OPIC アプローチの閾値は 0.9 を（注 3）：http://www.scipy.org/

用いた．

1

30

順 0.8
位 0.6
相
関 0.4
係
数 0.2

合 25
計
平 20
均 15
時
間（ 10
秒） 5

0

図5

提案手法
Chenらの手法
0

5000

10000

15000

平均局所グラフサイズ

20000

25000

提案手法
Chenらの手法

0

0

5000

10000

15000

平均局所グラフサイズ

20000

25000

提案手法，Chen らの手法：順位相関係数と平均局所グラフサイ図7

ズの比較（TSG ）提案手法，Chen らの手法：合計平均時間と平均局所グラフサイズの比較（TSG ）

1
25

順 0.8
位 0.6
相
関 0.4
係
数 0.2
0

図6

平
均 局 20
作 所 15成グ
時 ラ 10間（ フ秒） の 5

提案手法
Chenらの手法

0

1000

2000

3000

4000

平均局所グラフサイズ

5000

0

6000

提案手法，Chen らの手法：順位相関係数と平均局所グラフサイ

提案手法
Chenらの手法

図8

ズの比較（WG ）

0

5000

10000

15000

20000

平均局所グラフサイズ

25000

提案手法，Chen らの手法：局所グラフの平均作成時間と平均局
所グラフサイズの比較（TSG ）
10

平
均 8
推評 6
定価
時値 4
間（ の
秒） 2

推定精度．図 5，6 は，TSG と WG を用いた実験における，提案手法と Chen らの手法の順位相関係数と平均局所グラフサ
イズの比較結果を示している．縦軸は順位相関係数，横軸は平均局所グラフサイズを示している．グラフ上の各点は，各手法の各閾値における結果に対応している．
図 5，6 より，平均局所グラフサイズが同程度の時，提案手法

0と Chen らの手法の順位相関係数が同程度であることが分かっ

提案手法
Chenらの手法
0

5000

10000

15000

20000

平均局所グラフサイズ

25000

た．図 5 より，TSG を用いた実験では，平均局所グラフサイズが大きくなるほど，順位相関係数が向上した．また，図 6 よ図9

提案手法，Chen らの手法：評価値の平均推定時間と平均局所グ
ラフサイズの比較（TSG ）り，WG を用いた実験では，順位相関係数は平均局所グラフサ
イズにかかわらずほぼ同じであった．

1.6

提案手法
Chenらの手法

合 1.4
計 1.2
平 1
均 0.8
時
間（ 0.6
0.4秒） 0.2

計算コスト．図 7 – 12 は，TSG と WG を用いた実験における，提案手法と Chen らの手法の計算時間と平均局所グラフサ
イズの比較結果を示している．縦軸は，局所グラフの平均作成
時間，評価値の平均推定時間，合計平均時間のいずれか，横軸は平均局所グラフサイズを表している．合計平均時間は局所グ

0

ラフの平均作成時間と評価値の平均推定時間の合計である．グ

0

1000

ラフ上の各点は，各手法の各閾値における結果に対応している．
図 7，10 より，平均局所グラフサイズが同程度の時，提案手法の方が効率的に PageRank 値を推定できることが分かった．

図 10

2000

3000

4000

平均局所グラフサイズ

5000

6000

提案手法，Chen らの手法：合計平均時間と平均局所グラフサ
イズの比較（WG ）具体的には，図 8，11 より，平均局所グラフサイズが同程度の時，提案手法の方が局所グラフの平均作成時間が非常に小さかった．これは，提案手法は，反復計算ではなく再帰的な計算によって影響力を計算しているため，より高速に局所グラフを作成することができたためである．また，図 9，12 より，平均局所グラフサイズが同程度の時，提案手法と Chen らの手法の評価値の平均推定時間は同程度であった．

6. 3 提案手法と Naive な手法の比較
表 1 は，提案手法と Naive な手法の順位相関係数と平均局所グラフサイズの比較結果を示している．提案手法の影響力の閾値は，性能が最も良かった時の閾値を用いた．具体的には，

1.2に決定することができれば，推定精度を向上させることができ

平 1
均局
作 所 0.8
成グ
時 ラ 0.6間（ フ 0.4秒） の 0.20

図 11ると考えられる．さらに，提案手法について理論的な分析を行提案手法
Chenらの手法

いたいと考えている．
謝辞 本研究の一部は，共同研究（富士通研究所 CPE25149），

JSPS 科研費（25330124）による．
文
0

1000

2000

3000

4000

平均局所グラフサイズ

5000

6000

提案手法，Chen らの手法：局所グラフの平均作成時間と平均局所グラフサイズの比較（WG ）
0.6

評
価 0.5
値
の 0.4
平
均 0.3
推
定 0.2
時
間（ 0.1
秒） 0

図 12

提案手法
Chenらの手法

0

1000

2000

3000

4000

平均局所グラフサイズ

5000

6000

提案手法，Chen らの手法：評価値の平均推定時間と平均局所グラフサイズの比較（WG ）表 1 提案手法と Naive な手法の比較

TSG

WG

Naive 提案手法 Naive 提案手法
順位相関係数平均局所グラフサイズ

1.000
57, 247

0.993

0.983

23, 578 5, 029

0.998

3, 055

TSG では 0.0001，WG では 0.05 である．表 1 より，Naive な手法と比較して，提案手法は順位相関係数は同程度であるが，平均局所グラフサイズが非常に小さいことが分かった．これは，提案手法は影響力を考慮しながら展開するノードを選択しているため，PageRank 値の推定に不要なノードを局所グラフに追加していないためである．

7. まとめと今後の課題
本稿では，局所グラフを用いて特定のノードの PageRank 値を効率的に推定する手法を提案した．提案手法では，境界ノードとその隣接ノードの接続関係に基づいて作られる連立一次方程式を解くことで，ノードの影響力を推定した．これにより，反復計算を行わないため，提案手法は高速に影響力を推定することができた．評価実験により，Chen らの手法と比較して，提案手法は推定精度を維持しながら，効率的に PageRank 値を推定できることを示した．具体的には，提案手法は，最大で約3.2 倍高速に PageRank 値を推定することができた．
今後の課題として，ObjectRank [3] などの他のランキング手
法に提案手法を適用することが挙げられる．また，影響力の閾
値は推定精度にとって重要な要素であり，適切な閾値はデータセットの性質によって異なる．そのため，適切な閾値を自動的

献[1] Serge Abiteboul, Mihai Preda, and Gregory Cobena. Adaptive on-line page importance computation. In World Wide
Web Conference Series, pages 280–290, 2003.
[2] Arvind Arasu, Jasmine Novak, Andrew Tomkins, and John
Tomlin. PageRank Computation and the Structure of the
Web: Experiments and Algorithms. In World Wide Web
Conference Series, 2002.
[3] Andrey Balmin, Vagelis Hristidis, and Yannis Papakonstantinou. ObjectRank: Authority-Based Keyword Searchin Databases. In Very Large Data Bases, pages 564–575,
2004.
[4] Ziv Bar-yossef and Li tal Mashiach. Local approximationof pagerank and reverse pagerank. In International Conference on Information and Knowledge Management, pages
279–288, 2008.
[5] Marco Bressan and Luca Pretto. Local computation ofPageRank: the ranking side. In International Conferenceon Information and Knowledge Management, pages 631–
640, 2011.
[6] Sergey Brin and Lawrence Page. The anatomy of a largescale hypertextual Web search engine. Computer Networks
and Isdn Systems, 30:107–117, 1998.
[7] Andrei Z. Broder, Ronny Lempel, Farzin Maghoul, andJan O. Pedersen. Eﬃcient PageRank approximation via
graph aggregation. Information Retrieval, 9:123–138, 2006.
[8] Yen-Yu Chen, Qingqing Gan, and Torsten Suel. Local methods for estimating pagerank values. In International Conference on Information and Knowledge Management, pages
381–389, 2004.
[9] Jason V. Davis and Inderjit S. Dhillon. Estimating the
global pagerank of web communities. In Knowledge Discovery and Data Mining, pages 116–125, 2006.
[10] T.H. Haveliwala. Eﬃcient computation of pagerank. Technical report, Stanford InfoLab, October 1999.
[11] Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D.
Manning, and Gene H. Golub. Extrapolation methods foraccelerating PageRank computations. In World Wide Web
Conference Series, pages 261–270, 2003.
[12] Julie L. Morrison, Rainer Breitling, Desmond J. Higham,and David R. Gilbert. GeneRank: Using search engine technology for the analysis of microarray experiments. BMC
Bioinformatics, 6, 2005.
[13] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
Winograd. The pagerank citation ranking: Bringing orderto the web. Technical Report 1999-66, Stanford InfoLab,
November 1999.
[14] Charles Spearman.
FOOTRULE FOR MEASURING
CORRELATION. British Journal of Psychology, 2:89–108,
1906.
[15] Jianshu Weng, Ee-Peng Lim, Jing Jiang, and Qi He. TwitterRank: ﬁnding topic-sensitive inﬂuential twitterers. In
Web Search and Data Mining, pages 261–270, 2010.
[16] Yao Wu and Louiqa Raschid. ApproxRank: Estimating
Rank for a Subgraph,. In International Conference on Data
Engineering, pages 54–65, 2009.
[17] Gui-Rong Xue, Hua-Jun Zeng, Zheng Chen, Wei-Ying Ma,
Hong-Jiang Zhang, and Chao-Jun Lu. Implicit link analysis for small web search. In Research and Development inInformation Retrieval, pages 56–63, 2003.