Robust PageRank and Locally Computable Spam Detection Features

R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain, V. Mirrokni, S. Teng
Robust PageRank and Locally Computable Spam Detection Features
Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web
2008. Apr.
論文の在処

概要

Webのspamに関連した論文。
局所的に計算できるcontribution vector *1の近似を用いて、前半ではspamの発見方法の提案、後半ではRobust PageRankという文字通りPageRankをspamに対してrobustにしたランキングシステムの提案をしている。
contribution vectorの効率的な近似方法に付いては詳しく触れられていない。

1. INTRODUCTION

web spamはページのコンテンツやリンク構造をうまく使ってそのページのランキングをあげようとするもの。検索結果の劣化や、crawling、indexingの効率を下げ、storageを無駄にする[11]。
web spamを見つけるためのたくさんのアプローチがある。コンテンツを利用したもの、リンク構造を利用したもの、そのコンビネーションだったりする。

成功しているテクニックは、機械学習技術のlink-based featresへの適用[2]、コンテンツの解析[14,13]、TrustRank[9]、Anti-TrustRnk[15]、様々なfeaturesの統計的な解析[6]、transductive（転動的）link spam detection[18]などがある。
成功しているテクニックの一つが、PageRankに特に貢献しているノード（ページ）の集合を見つける方法。spamページは少ないノードを利用して（link farm）大きいPageRankを得ようとするだろうから、この方法は有効。supporting sets（spamページのPageRankのアップに貢献しているページの集合）とPageRankへの貢献の解析がspam発見に使われている。SpamRank algorithm of Benczur et al[3]、Spam Mass algorithm of Gyongyi et al[8]や最近ではZhow[17]など。

supporting setsの考えは、personalized PageRankに基づいてノードuのノードvのPageRankへの貢献を厳密に定義することで正確になる。
ウェブグラフをG = (V, E)とする。
teleportation constant（restart probability）をαとする。
$PRM_\alpha$ をu番目の行がノードuのpersonalized PageRanc vectorを表す行列とする。
uからvへのPageRank contributionは $pr_\alpha(u\rightarrow v)$ とし、 $PRM_\alpha$ の(u,v)成分で定義される。
ノードvのPageRankは $PRM_\alpha$ のv列目の和。つまりノードのPageRankは全ての他のノードからのcontributionの和と考えられる。
ノードvのcontribution vectorは $PRM_\alpha$ のv列目と定義し、それぞれのentriesは他のそれぞれのノードのvに対するcontribution。
ノードvのδ-supporting setは少なくともvのPageRankのδ-fractionの貢献をしているノードの集合。

最近の論文でcurrent authorsが特定の一つのノードに対してcontribution vectorを効率的に近似するアルゴリズムを紹介している[1]。このアルゴリズムはそのノードの近くの少ない数のノードだけ計算することでreasonableな近似を得る。グラフの小さな部分だけを利用してあるノードのpersonalized PageRank vectorを効率的に近似する方法[7,12,4,16]と似ている。それぞれのpersonalized PageRank vectorを近似し、それを列としてPageRank行列の近似を作り、その転置行列の列を取ってきてcontribution vectorの近似とする既存の方法（例えば[3]）と、このアルゴリズムとは違う。

この論文ではlacallyに計算されたsupporting setsの近似に基づいていくつかのspam-detection featuresを定義し、教師あり学習と教師なし学習両方のアプローチで利用する。これらのfeaturesの効果をスパム発見のベンチマークを使って実験し、計算コストの調査に大きなグラフを用いて実験。

この論文では最後にlink spam engneeringに対してrobustなRobust PageRankというものを定義する。Robust PageRankではそれぞれのノードは多くともある量までしか他のノードに貢献できない。Robust PageRankは上記のfeaturesとPageRankをcombineすることで効率的に近似される。このランキングシステムは[2]で研究されている、距離がd以下のノードのcontributionを無視するというTruncated PageRank algorithmに関連している。Robust PageRankでは距離が大きい方がより大きく貢献するので、Truncated PageRankのrefinmentと見なせる。

Organization

Section 2ではPageRank、personalized PageRank、PageRank contribution vectorsといった必要な背景をreviewする。
Section 3で特定のノードのsupporting setsを計算するためのアルゴリズムをreviewする。
Section 4でいくつかのlocallyに計算できるspam detection featuresを定義する。
Section 5で二つの実データでの実験結果を示す。
Section 6でRobust PageRankを定義し、その近似のためのアルゴリズムを説明し、Robust PageRankの使用を正当化するいくつかの実験結果を示す。

2. PRELIMINARIES

このsectionでは実験で用いられるalgorithmic toolsについて説明する。とくにPageRank contribution vectorsを近似するためのアルゴリズム[1]はなるべく簡潔に（証明や解析をしないで）説明する。

webは有向グラフでモデル化されるが、out-edgesのないdangling nodesの問題を扱うために人工的なself-loopを持つノードをグラフに加え、dagnling nodesからこのノードへのedgeを加える。
Aをグラフの隣接行列とし、 $d_{out}(u)$ をuの出次数、 $d_{in}(u)$ を入次数とし、 $D_{out}$ を出次数を対角成分とした対角行列とする。

teleportation constant αに対して、PageRank vector $pr_\alpha$ はBrinとPage[5]により以下の式を満たすものと定義されている。
$pr_\alpha = \alpha \cdot 1 + (1 - \alpha)\cdot pr_\alpha \cdot M$
Mはランダムウォークの遷移行列で、 $M = D_{out}^{-1}A$ で与えられる。1は単位行ベクトル。
ページuのPageRankは $pr_\alpha(u)$ 。
以降では誤解を招かない範囲でαを省略。
$\sum_u pr_\alpha(u) = |V|$ であることに注意。

同様にHaveliwala[10]に定義されたpersonalized PageRnak vector ppr(α,u)は以下の式を満たす。
$ppr(\alpha,u) = \alpha \cdot e_u + (1 - \alpha)\cdot ppr(\alpha,u)\cdot M$
$e_u$ はu番目の要素が1の行ベクトル

$PRM_\alpha$ をu番目の行がpersonalized PageRank vector ppr(α,u)である行列とする。
そして(global) PageRank vector $pr_\alpha$ は $1\cdot PRM_\alpha$ 、つまりpersonalized PageRank vectorsの和。
uからvへのPageRank contributionは $PRM_\alpha$ の(u,v)要素で、 $ppr_\alpha(u \rightarrow v)$ と書く。
vのcontribution vector、cpr(α,v)は $PRM_\alpha$ のv列目の転置。
c = cpr(α,v)のとき、c(S)はSに含まれるノードからvのPageRankへの貢献を表す。
なので $c(V) = pr_\alpha(v)$ で、 $c(u) = ppr_\alpha(u \rightarrow v)$ 。

3. LOCAL APPROXIMATION OF CONTRIBUTION VECTORS

このsectionではノードvのcontribution vector c = cpr(α,v)を近似するためのアルゴリズムを示す。この近似されたcontribution vectorsからspam detection featuresを得る。

定義１： $\tilde c$ はc = cpr(α,v)のε-absolute-approximationで全てのノードuに対して $\tilde c \leq 0$ 、 $c(u) - \varepsilon \leq \tilde c(u) \leq c(u)$ を満たす。

非負vectorである $\tilde c$ のsupportを $Supp(\tilde c)$ とし、 $\tilde c$ 内での要素がstrictly positiveであるようなノードの集合を表す。たとえば $\tilde c$ = (0,0,1,3,0,0)だったら3と4のノード。
vector cはcanonicalなε-absolute-approximationを持つ。 $\bar c-$ を
$\bar c = \bigl\{ {\begin{array}{cc} c(u) \; \; \; if \; c(u) < \varepsilon \\ 0 \; \; \; otherwise \end{array}$
とする。明らかに $\bar c$ はcのsmallest supportであるε-absolute-approximation。
さらに、 $||\bar c||_1 \leq ||c||_1$ なので $|Supp(\bar c)| \leq ||c||_1/\varepsilon$ 。
localのアルゴリズムは $\var c$ のsupport structureとにたようなsupport structureを持つcの近似 $\tilde c$ を見つけようとする。

ターゲットのノードvのcontribution vectorのε-absolute-approximationを計算するためのアルゴリズム、AproxContribを下記に示す。

アルゴリズムでexamineされるノードの数の上限を与える。この数は $pr_\alpha(v)$ 、ε、αに依存するが、グラフのノード数とは独立。
このアルゴリズムはpushback operationsと呼ばれるoperationの連続を行う。それぞれのpushback operationはグラフの一つのノードに対して行われ、そのノードの入次数に比例した時間がかかる。
pushback operationが行われる回数に上限を設け、計算時間を調節する。計算時間はpushback operationが行われたノードの入次数に依存する。
得られた近似contribution vectorのsupportの上限がoperation pushbackの数。

アルゴリズムとその解析の詳細は[1]に書いてある。
この論文では、アルゴリズムをブラックボックスとして扱い、効率的な時間で計算できるとする。
次のsectionではこれらの近似contribution vectorsから得られるspam detection featuresを説明する。

4. LOCALLY COMPUTABLE FEATURES

このsectionではspam detection featuresの計算方法を形式的に定義する。
主にlocalなアルゴリズムを用いてcontribution vectorsを近似する。
まず、ほとんどのfeatureをの定義に役立つ近似contributing setsを定義する。

4.1 Approximate contributing sets

ノードvが与えられたとき、以下のcontributing setを定義する
・δ-significant contributing set
$S_\delta(v) = \{u|ppr_\alpha(u \rightarrow v) > \delta \cdot pr_\alpha(v)\}$
・ρ-supporting set
$ppr_\alpha(S \rightarrow v) \geq \rho \cdot pr_\alpha(v)$

4.2 Unsupervised learning features

いくつかのリンク構造にのみ基づいたfeaturesを定義する。
これらのfeaturesがlocallyに計算できることと、パフォーマンスの実験の結果を示す。
以下がfeaturesのリスト。
1. Size of δ-significant contributing set
ノードvに対して、 $|S_\delta(v)| = |{u|ppr_\alpha(u \rightarrow v) > \delta \cdot pr_\alpha(v)}|$
spamのノードでnon-spamノードに対してこの値が著しく小さくなると考えられる。
2. Contribution from vertice in the δ-significant contributing set
ノードvに対して、 $\sum_{u\in S_\delta(v)} ppr_\alpha(u\rightarrow v)/pr_\alpha(v)$
3. $l_2$ norm of δ-significant contributing vector
ノードvに対して、 $\sum_{u\in S_\delta(v)} (ppr_\alpha(u\rightarrow v)/pr_\alpha(v))^2$
とくにδ=0のとき、L2Normと書き、 $\sum_{u\in V(G)} (ppr_\alpha(u\rightarrow v)/pr_\rightarrow(v))^2$

比較対象として、以下の簡単な教師なしのfeaturesを用いる。
1. ノードの入次数(Indegree)
2. ノードのPageRankのratioとその入次数(PRIndegree)

4.3 Approximate computation of features

上記のfeaturesの近似versionを計算するために、前述のε-approximate contribution vector $\tilde c$ を、 $\varepsilon = \delta \cdot pr_v$ で計算する。
$\tilde S_\delta$ を\tex:\tilde c]で $\delta \cdot pr_v$ 以上の値を持つノードの集合とする。

$\tilde S_\delta$ は1/αδ+1回のpushback operationsを行って計算できる。
この集合は $S_{2\delta}\subseteq \tilde S_\delta \subseteq S_\delta$ という意味では、vのsignificant contributorsの良い近似を与える。
以下にapproximate featuresを定義する。
1. (Approximate) size of the δ-significant contributing set (SuppSizeDelta)
ノードvに対して、 $|\tilde S_\delta| = |\{u|\tilde c(u) > \delta \cdot pr_\alpha(v)\}|$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードの数。
2. (Approximate) contribution from δ-significant contributing set (ContributePercent)
ノードvに対して、 $\sum_{u\in \tilde S_\delta} \tilde c(u)/pr_\alpha(v)$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードの貢献の和をvのPageRankで割って標準化。
3. (Approximate) l_2 norm of contribution vector (L2NormDelta)
ノードvに対して、 $\sum_{u\in V(G)} (\tilde c(u)/pr_\alpha(v))^2$
全てのノードのvに対するPageRank中での貢献の割合を二乗したものの和。極端に割合が大きいノードがあると大きくなる。

4.4 Supervised learning features

教室あり学習では既にラベルの付いたノードの集合をつかって、ラベルを付けられていないノードのラベルを予測する。
同様に $\tilde S_\delta(v)$ を近似supporting setする。
$\tilde T_\delta(v)$ を $\tilde S_\delta(v)$ の中でspamラベルの付いたノードの集合とする。
以下に教師あり学習でのlocallyに計算可能なfeaturesを示す。
1. Fraction of nodes in the supporting set labeled as spam (SupervisedUnweighted)
ノードvに対して、 $|\tilde T_\delta(v)|/|\tilde S_\delta(v)|$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードの内、spamノードの割合。
2. Contribution from nodes in the supporting set labeled as spam(SupervisedWeighted)
ノードvに対して、 ${\sum_{u\in \tilde T_\delta(v)} \tilde c(u)}/{\sum_{u\in \tilde S_\delta(v) \tilde c(u)}$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードのうち、spamノードの貢献の和を、そのようなノードのすべての貢献の和で割った値。

(SupervisedWeighted)は本質的にPageRankをspamラベルのノードを１としたstarting vectorで行うことで得られるfeatureの近似。

比較対象として、以下の基本的なfeatureを使う。
1. (SupervisedIndegree)
入次数と、その中でspamノードからのエッジとのratio

5. EVALUATION OF FEATURES

実験結果のsection。

5.1 Data Sets

Becchettiらが研究した[2]のUK hostグラフ(UKhost)を主に使う。
11402ノードで、平均次数は65。
ほとんど半分のノードが人の手でspamかnon-spamかラベル付けされている。
5750のhostsが人の手でラベル付けされ、いくつかのページを見てリンクファームがhost内にあればそのhostをspamとしている。結果は674のhostsがspamで4974のhostsが普通のhosts。

アルゴリズムの実行時間を計るため、2006年５月にMSN searchにより得られたdomain graph(MSNdom)を用いた。
約55mノードで約500mリンク。
largest strongly connected component（最大強連結成分）は約13m400,000ノード。
largest connected component（最大連結成分）は約44mノード。
最大連結成分に含まれ最大強連結成分には含まれていないノードのうち、21mノードは最大強連結成分からのエッジを持っていて、6m500,000ノードは最大強連結成分へのエッジを持っていた。
最大強連結成分に含まれないノードが多いことは、多くのdmainsが最大強連結成分からのリンクを得ようとしていることを示唆している。（なぜそのような結論に至るのかよくわかりません）

5.2 Running Time

δ-significant contribution setを見つけるアルゴリズム動かしたときのδ-significant contributing setsの平均のサイズと、pushbak operationsが行われた平均の回数と、これらのdata setsに対して行われたすべてのoperationsの平均の回数が示されている。
UKhostではPageRankの高いほうから24%のノード(2800くらい）。MSNdomでは5000のノードをPageRankの高い方から10%のノードの中からランダムに抽出して、それらのノードに対して計算した。

δが与えられたとき、pushback operationの回数は理論的にO(1/αδ)で、トータルの実行時間はpushback operationの行われたノードのindegreeの和に関係するが、実際のデータに対して実行した所、pushback operationsの回数は理論的に最悪な場合の回数に比べるとずっと小さかった。

5.3 Experimental Result

このsectionではUKhostでの紹介したfearuresのパフォーマンスを示す。
spam発見は高いPageRankのノードでより重要なので、高いPageRankのノードの集合でのみの結果を示す。
とくにPageRankが上位24%のノードをhigh PageRankノードと呼ぶことにする。

"spam"をspamとラベル付けされたhigh PageRankノードの集合、"nonspam"をnonspamとラベル付けされたhigh PageRankノードの集合とする。
それぞれのfeature fに基づいて、ノードの部分集合をspam、残りをnonspamとするclassifierを定義する。
このclassifierはclassifierごとの閾値に基づいてそれ以上かそれ以下かでノードを二分する。
classifierにspamと判断されたhigh PageRankノードの集合をreportedspamと呼ぶ。
それぞれのfeature fに対して、以下のパラメータを考える。

1. Average value (f-)
high PageRankノードのこのfeatureの平均値
2. Average value on spam (f-(spam))
reportedspamのこのfeatureの平均値
3. Average value on non-spam (f-(nonspam))
high PageRankノードでnon-spamのこのfeatureの平均値
4. Percentage of false positive (FalsePos)
nonspamなのにspamと判断されてしまった割合(nonspam∩reportedspam)/nonspam
5. Percentage of false negatives or Recall (Rec)（false negativeを間違って使っているような気がします。）
再現率。spamのうちspamと判断できた割合(spam∩reportedspam)/spam
6. Precision (Prec)
精度。spamと判断したうち本当にspamだった割合(spam∩reportedspam)/(nonspam∪spam)∩reportedspam

良いfeatureは小さいFalsePosで大きいRecとPrec。
ノードがspamかそうでないかを検証するのが大変なとき、多くのnon-spamノードをspamと判断するのは嫌である。
明らかにトレードオフがあるが、結果的にはそれぞれの閾値をFalsePosが5%（もしくは2%）以下になるように設定した。
もしもっと小さなFalsePosが求められたときのために、より良いFalsePosを得られる閾値を決められるようfeaturesのうちのいくつかでpercentile chartを示している。（どうやったらこのグラフから閾値を決めろというのかわかりません。）
percentile chartが示されているのは $\delta =10^{-4}$ のSuppSizeDelta、ContributePercentと、 $\delta =10^{-5}$ のSuppSizeDelta、L2NormDelta。
予想通り、教師ありのfeaturesの方がわすがに教師なしよりも良かった。

5.4 Observation

このsectionではいくつかの実験結果のsammarizeをする。
パラメータδでそれぞれのlocallyに計算可能なfeaturesに対して、アルゴリズムの実行時間はpushback operationsの回数かδ-significant contribution setのサイズによる。
UKhostではδ-significant contribution setのサイズは $\delta=10^{-2}, 10^{-3}, 10^{-4}, 10^{-5}$ でだいたい4, 25, 305, 5700だった。
教師なし学習のfeaturesではSuppSizeDeltaとContributePercentがベストだった。
L2NormDeltaもreasonableだったが、明らかに前の二つよりは劣った。
これらのfeaturesは基本的な教師なし学習のfeaturesであるIndegreeとPRIndegreeを著しく圧倒した。
$\delta=10^{-4}$ ではsupporting setはとても小さく（300くらい）、ContributePercentがベストなfeatureだった。
これらの教師なし学習のfeaturesは基本的な教師あり学習のfeaturesであるSupervisedIndegreeよりもわずかに良かった。
予想通り、SupervisedUnweightedがすべての教師なし学習よりもわずかに良かった。
すべての上記のfeaturesでパフォーマンスはパラメータδを小さくした方が良くなった。

最後に、ここで提案された教師なし学習のfeaturesはたかいPageRankをもったノードでしか使えないということを観察した。実際に全てのノードに対して行った所、結果は圧倒的に悪くなった。
例えばFalsePosを0.02と0.05にすると、Recは0.10から0.23、0.05から0.15の間で変化した。
なので、これらの値は記さずに、高いPageRankのノードへの適用を協調した。
高いPageRankのノードは検索結果の高い位置に出てくるであろうことから、そのようなノードに対するspam発見がより重要だということに注意。
この低いPageRankのノードでの悪いパフォーマンスにはそのようなノードの周りのリンク構造がspamminessの情報を予想するのに十分でないことが直感的真実として隠れている。

6. ROBUST PAGERANK

このsectionではcontribution setsのアイディアを使ってRobust PageRankと呼ばれるPageRankの改良版のランキングシステムを構築する。
このシステムはlink spamに対してより信頼できるということを実験結果で示す。

ノードvのPageRankは他のノードからのcontributionの和として以下のように表せる。
$pr_\alpha(v) = \sum_{u\in V(G)} ppr(u,v)$

robust PageRankのアイディアは、最もPageRankに貢献しているノードらの影響を少なくしようというアイディア。
このアイディアを実現するために、閾値δよりも多く貢献していノードのcontributionをδにすることで下記のように定式化する。
$Robustpr^\delta_\alpha(v) = \sum_{u\in V(G)} \min(ppr(u, v),\delta)$

少しの多く影響しているノードの貢献を減らすことで、spamノードのPageRankをnonspamノードよりも小さくすることができる。
次にどうやって近似contribution vectorsから近似robust PageRankを計算するを示し、性能の高さを示す実験結果を示す。

Robust PageRankは以下のように近似する。
まず、Robust PageRankを以下のように書き直す。
$\begin {array}{lll}Robustpr^\delta_\alpha(v) \\ \; \\ \; \end{array} \;\; \begin {array} {lll} = \sum_{u\in V(G)} \min(ppr(u,v), \delta) \\ = \sum_{u\in V(G)} ppr(u,v) - \sum_{u\in S_\delta(v)} min(ppr(u,v) - \delta) \\ = pr_\alpha(v) - \sum_{u\in S_\delta(v)} ppr(u,v) - \delta|S_\delta(v)| \end{array}$

ノードvのRobust PageRankを近似するときは、誤差 $\varepsilon = \delta \cdot pr_\alpha(v)$ としてcontribution vector $\tilde c$ を計算し、PageRanc contribution ppr(u,v)を $\tilde c(u)$ で置き換える。
そして、以下の定義を得る。
$ApproxRobustpr^\delta_\alpha(v) = pr_\alpha(v) - \sum_{u\in \tilde S_\delta(v)} \tilde c(u) - \delta|\tilde S_\delta(v)|$

6.1 Experiments with Robust PageRank

UKhostでPageRank上位24%のノードのPageRankとrobust PageRankのpercentile chartを見比べると明らかにspamの大きな部分がより低いランクにrobust PageRankではなっている。

上記のchartsを補完しPageRankに対してのrobust PageRankの優位性を示すため、ノードのrobust PageRankとPageRankのratioを計算し、featuresとして使った。
$NormalizedRobustPR = ApproxRobustpr^\delta_\alpha(v)/pr_\alpha(v)$

このfeatureの結果からspamノードの方がrobust PageRankの値がPageRankより小さくなっていることがわかる。
他のfeaturesと違い、δを小さくしていってもqualityはあがらず、 $\delta=10^{-3}$ でベストだった。 $\delta=10^{-3}$ ではこのfeatureは他の教師なし、教師あり学習のfeaturesより良かった。

7. CONCLUSION

この論文では近似PageRank contribution vectorsを使ってlocallyに計算できるlink spam detectionのfeaturesを調査した。
ほとんどのfeaturesはcontribution setのdesired approximation factorとしてパラメーターδを持つ。
実行時間とspam発見のパフォーマンスの間の適切なトレードオフを見つけるために、data setに基づきδは計算されるべき。
教師なし学習のfeatureではContributePercent、NormalizedRobustPR、SuppSizeDeltaが良かった。
UKhostではNormalizedRobustPRが $\delta10^{-3}$ で、ContributePercentが $\delta=10^{-4}$ でベストだった。
特にこれらのfeaturesは教師あり学習のSupervisedIndegreeよりも良かった。
教師あり学習のfeatureであるSupervisedUnweightedがすべてのfeaturesの中でベストだった。

8. PREFRENCE

[1] R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, V. Mirrokni, and S. Teng. Local computation of PageRank contributions. In 5th International Workshop of Algorithms and Models for the Web-Graph, 2007.
[2] L. Becchetti, C. Castillo, D. Donato, S. Leonardi, and R. Baeza-Yates. Link-based characterization and detection of web spam. In In Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2006.
[3] A. Benczur, K. Csalogany, T. Sarlos, and M. Uher. Spamrank - fully automatic link spam detection. In First International Workshop on Adversarial Information Retrieval on the Web, 2005.
[4] P. Berkhin. Bookmark-coloring algorithm for personalized PageRank computing. Internet Math., 3(1):41–62, 2006.
[5] S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7):107–117, 1998.
[6] D. Fetterly, M. Manasse, and M. Na jork. Spam, damn spam, and statistics: using statistical analysis to locate spam web pages. In WebDB ’04: Proceedings of the 7th International Workshop on the Web and Databases, pages 1–6, New York, NY, USA, 2004. ACM Press.
[7] D. Fogaras and B. Racz. Towards scaling fully personalized PageRank. In Proceedings of the 3rd Workshop on Algorithms and Models for the Web-Graph (WAW), pages 105–117, October 2004.
[8] Z. Gy¨ongyi, P. Berkhin, H. Garcia-Molina, and J. Pedersen. Link spam detection based on mass estimation. In Proceedings of the 32nd International Conference on Very Large Databases. ACM, 2006.
[9] Z. Gy¨ongyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In VLDB, pages 576–587, 2004.
[10] T. H. Haveliwala. Topic-sensitive PageRank: A context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng., 15(4):784–796, 2003.
[11] M. Henzinger, R. Motwani, and C. Silverstein. Challenges in web search engines. In In: Proc. of the 18th International Joint Conference on Artiﬁcial Intel ligence, pages 1573–1579, 2003.
[12] G. Jeh and J. Widom. Scaling personalized web search. In Proceedings of the 12th World Wide Web Conference (WWW), pages 271–279, 2003.
[13] G. Mishne and D. Carmel. Blocking blog spam with language model disagreement, 2005.
[14] A. Ntoulas, M. Na jork, M. Manasse, and D. Fetterly. Detecting spam web pages through content analysis. In
WWW ’06: Proceedings of the 15th international conference on World Wide Web, pages 83–92, New York, NY, USA, 2006. ACM Press.
[15] R. Ra j and V. Krishnan. Web spam detection with anti-trust rank. In Proc. of the 2nd International Worshop on Adversarial Information Retreival on the Web, pages 381–389, 2006.
[16] T. Sarl´os, A. A. Bencz´ ur, K. Csalog´ any, D. Fogaras, and B. R´acz. To randomize or not to randomize: space optimal
summaries for hyperlink analysis. In WWW, pages 297–306, 2006.
[17] B. Zhou. Mining page farms and its application in link spam detection. Master’s Thesis, Simon Fraser University, 2007.
[18] D. Zhou, C. Burges, and T. Tao. Transductive link spam detection. In AIRWeb, 2007.

*1:本文中でも説明しているが、ノードに対して定義されるvectorでi番目の要素はそのノードからノードiへの貢献（contribution）を表す