第 7 章 リンク解析 111
7.5 性能評価
2,965,197,340のハイパーリンク規模である．ラベルは，11,402のWebサイトからなる7,473ホストに 付与された．その内2,725ホストは2人以上からspam，non-spam，borderline，undecidedとう4つの カテゴリに手動でラベルを付けられた．それ以外はOpen Directory Projectに登録されたホストや特定 のドメイン（.ac.uk, .sch.uk, .gov.uk, .mod.uk, .nhs.uk, .police.uk）がnon-spamとして投票された．
分類器の都合でundecidedとborderlineとなっているものは評価対象から除外した（[3, 26]と同様）．
表7.1にラベルの情報を示す．
表7.1 WEBSPAM-UK2006のラベル Set #hosts normal spam training 5622 4948 674
test 1851 1250 601
7.5.2 ベースライン手法
提案手法と比較するため，state-of-the-artの手法であるPage-farms [26]を比較対象とした．
7.5.3 データセットの蝶ネクタイ構造
まず，ホストとページのwebgraphにおいて，それらの強連結成分を抽出し，得られた結果は表7.2と 表7.3に示す．
結果により，クローリングの戦略によるINの部分では大量のページを獲得できたことが分かる．この データセットのシードはOpen Directory Project に登録されたものであり，.ukドメインを限定したク ローリングを行った．そのため，いくつかのホストは.ukドメイン以外のリンクが無視され，非連結なグ ラフが多くなった．
SVMの分類器はホスト単位の判定ではなく，サブグラフ単位でスパム判定を行う．データセットは ホスト単位のラベルが提供されているので，次の基準でホストのラベルからサブグラフのラベルを確定 する．
スパムか非スパムノードを含むサブグラフに対して同じラベルを付ける．しかし，矛盾の場合（スパム と非スパムが同時に同じサブグラフに存在する場合），そのサブグラフにはラベルを付けないことにする．
しかし，投票式の利用が可能である．その結果は表7.2と表 7.3に示す．カテゴリ毎の強連結成分の数も 含む．この情報をSVMの学習と評価に利用する．
7.5.4 KCore とその影響
Webgraphの核を解析するために，核内に存在するノードのcorenessを計算する．KCoreに所属して
いる全ノードがkのアウトリンク，被リンクもしくはアウトリンク＋被リンク以上の他のノートと接続す るという３つの基準を確認する．
核に存在するスパムと非スパムラベルホストのcorenessの分布を図 7.6(a-f)に示す．横軸はノードに 対するcorenessを表し，縦軸は頻度を示す．
ホストのwebgraphの結果に関して（図 7.6 a-b），どのcorenessでもスパムと非スパムホストが含ま
7.5 性能評価 121 れている．しかし，被リンクによるcorenessではスパムが限界があることがわかる（本データセットで は２７）．一方，非スパムホストが高いcorenessを持つこともある．最大coreness(67)を持つホストは教 育関係，政治関係，有名な企業のサイトが集まっている．
ページのwebgraphの場合（図7.6(d-f)）似たような結果が見られる．しかし，corenessが高いスパム ページの集合が存在する．これはスパマーが自分のホスト内にページのリンク構造を簡単に操作できるか らである．このグラフには空白がみられるが，その理由はラベルの対象とするホストの選択基準とクロー リングする際に，ホスト内の最大ページ数が決められているからである．グラフの全ノードのcoreness の分布にはその空白が見られない．
KCoreは密な接続を持つサブグラフであり，重要なホストが多くのホストから被リンクを持ち，その
中に他の被リンクの高いホストが含まれ，非常にロバストなサブグラフであることがわかる．一方，スパ ムホストはcorenessの限界に存在する．簡単な戦略では高いcorenessを得られない．ページ単位は簡単 に操作できるが，ホスト単位の操作がコストが高い．もし，高いcorenessを得られるとしても，クロー リングやフィルタリングの基準により，インデクスされないことが多い．さらにcorenessの高い非連結 なサブグラフを解析することにより，このスパムを発見できるようになることが期待できる．
これは一般化するため，他のデータセット(WEBSPAM-UK2007)にも解析を行った．図 7.6(g-l)に 示すようにスパムホストがcorenessの限界があることがわかる．
この結果により，我々はホストのcorenessが特定の閾値以降の場合，非スパムホストとして判断する．
表7.2 ホストのwebgraphの蝶ネクタイ構造およびラベル
training test
Type #sccs #nodes #spam sccs #non-spam sccs #spam sccs #non-spam sccs
Core 1 7,945 - - -
-In 134 135 - 48 - 5
Out 2,578 3,100 257 568 486 130
Tube 2 2 - - -
-Tendrils-In 49 49 1 10 - 2
Tendrils-Out 13 13 - 3 - 1
Disconnected 158 158 4 45 1 10
表7.3 ページのwebgraphの蝶ネクタイ構造およびラベル
training test
Type #sccs #nodes #spam sccs #non-spam sccs #spam sccs #non-spam sccs
Core 1 49,710,330 - - -
-In 590,418 892,533 61,517 229,863 41,438 17,099
Out 9,313,658 26,098,315 451,216 4,291,541 496,792 445,208
Tube 35,845 57,847 2 1,122 6 30,186
Tendrils-In 87,354 125,824 4,388 28,676 47 616
Tendrils-Out 437,195 495,478 53,648 72,495 49,169 23,307
Disconnected 324,672 360,719 15,198 183,234 362 22,274
0 200 400 600 800 1000 1200 1400 1600 1800
0 50 100 150 200
normal spam
0 500 1000 1500 2000 2500 3000
0 10 20 30 40 50 60
normal spam
0 200 400 600 800 1000 1200 1400 1600 1800
0 10 20 30 40 50 60 70
normal spam
frequency
W EBSPAM-U K2 0 0 6 W EBSPAM-U K2 0 0 7
frequencyfrequencyfrequencyhost webgraph
page webgraph
host webgraph
page webgraph
coreness(k) coreness(k) coreness(k)
(a) (b) (c)
coreness(k) coreness(k) coreness(k)
(d) (e) (f)
coreness(k) coreness(k) coreness(k)
(g) (h) (i)
coreness(k) coreness(k) coreness(k)
(j) (k) (l)
0 500 1000 1500 2000 2500 3000 3500 4000 4500 normal
spam
1 2 3 4 5 6 7 8
1 10 10 10 10 10 10 10 10
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 normal
spam
1 2 3 4 5 6 7 8
1 10 10 10 10 10 10 10 10
0 500 1000 1500 2000 2500 3000 3500 4000 4500 normal
spam
1 2 3 4 5 6 7 8
1 10 10 10 10 10 10 10 10
0 500 1000 1500 2000 2500 3000
0 50 100 150 200 250
normal spam
0 500 1000 1500 2000 2500
0 100 200 300 400 500
normal spam
0 500 1000 1500 2000 2500
0 50 100 150 200 250
normal spam
0 200 400 600 800 1000 1200
normal spam
1 2 3 4 5 6 7
1 10 10 10 10 10 10 10
0 500 1000 1500 2000
normal spam
1 2 3 4 5 6 7
1 10 10 10 10 10 10 10
0 200 400 600 800 1000 1200
normal spam
1 2 3 4 5 6 7
1 10 10 10 10 10 10 10
図7.6 Webgraphの核内にあるラベル付きのノードの最大coreness
この判断はO(m)の計算量のため，実用化可能になる．さらに閾値は動的に変更させることにより，重要 な非スパムホストを得ることができる．
本スパム判定ではcorenessが特定の閾値以上の場合，非スパムホストとして判断する．
7.5.5 スパム判定
提案したスパム判定とそれぞれの要素の評価のため，４つの実験を行う．それぞれのホストの判定は 表7.4に示す．
■実験１（SCC）
まず，webgraphの蝶ネクタイ構造の核外のホストスパムの判定を行った．
最初はホストのwebgraphに対し，核以外すべての強連結成分をSVM分類器に当てた．学習データ
7.6 スパム判定の応用 123