第 7 章 リンク解析 111
7.4 スパムの抽出方法
図7.3 リンクスパム
7.4 スパムの抽出方法
本節では提案しているリンク構造に基づいたWebスパム抽出アルゴリズムを説明する. 全体のフレー ムワークを述べた後，メインの３つのパートについて説明する．
7.4.1 フレームワーク
本アプローチは次の３つの方法で構成されている．
• Webgraphの蝶ネクタイ構造の解析によるリンクが高密なサブグラフを抽出する．
• サポートベクトルマシン（SVM）によるサブグラフのスパム判定を行い，ホスト単位の推定結果 をまとめる．
• ホストグラフでのトラストとアンチトラストを連鎖する偏向ページランクによる幅広いスパムを発 見する．
これらの方法を組み合わせて，平行にページのwebgraphとホストのwebgraphに適用する．一方，従 来手法ではどちらかが推定対象になっている．我々が両方のグラフを推定対象にしている理由は，スパム ページ同士はリンクを付け合うことがあるが，サイト内の全ページで同じことを行う保証がないからであ る．一方でスパムサイトが他のスパムサイトにリンクを付け合う傾向があるからである．
スパム判定の流れを図 7.4に示す．まず，平行にページのwebgraphとホストのwebgraphに対して，
蝶ネクタイ構造を得る．Webgraphの核以外のサブグラフを抽出する．また，核内に対して，KCoreア ルゴリズムに基づき，全ノード毎のcorenessを計算し，高密なリンクを持つサブグラフを抽出する．
次は，各サブグラフ毎にいくつかのフィーチャーを計算し，SVMの分類器によるサブグラフのスパム 判定を行う．ページのグラフに対して，スパム判定されたページ集合からホスト単位の判定を予測する．
これはページのラベルをホストのラベルにし，矛盾した場合（スパムページと非スパムページを持つホス ト）ラベルを付けない．投票により決定することが可能である．
全ての結果をまとめ，ホストの偏向ページランクを計算する．最後に，指定した閾値による最終的な判 定を行う．最終的な判定はSVMではなく偏向ページランクで行う．SVMの誤りを緩和するためである
（特にページのグラフの場合）．
ページランク 蝶ネクタイ構造の分析
強連結成分毎の フィーチャーベクトル作成
強連結成分毎の フィーチャーベクトル作成
最大Kcoreによる 非スパムの抽出
ページ単位の予測から ホスト単位の推定
ホスト単位の推定 のまとめ
ホスト単位の 最終的推定
最大強連結成分 に対するKcore分析 蝶ネクタイ構造の分析
ホストのウェブグラフ ページのウェブグラフ
SVMによるスパム判定 SVMによるスパム判定
図7.4 スパム判定の流れ
7.4 スパムの抽出方法 117
7.4.2 密な接続を持つサブグラフ
我々はスパムと非スパムサブグラフを識別するため，密な接続を持つサブグラフに着目した．その動機 は，非スパムノードは滅多にスパムノードにリンクせず，他の非スパムにリンクすることが多く，同じよ うにスパムノードのほとんどが他のスパムノードからリンクを受けるというものである．
密な接続を持つサブグラフを抽出するために，２つのアプローチを利用している．（１）Webgraphの 蝶ネクタイ構造の解析，（２）KCoreにより，webgraphの核内の密な接続を持つサブグラフを抽出する．
7.4.3 蝶ネクタイ理論
Webgraphの強連結成分を抽出し，蝶ネクタイの構造を得る [5]（図 7.5）．強連結成分とはグラフ上の
任意の2点間に有向路が存在する極大なサブグラフである．Webのマクロな構造に関するページ間の結 合関係を分析し，Webは蝶ネクタイ構造であると主張したBroderら[5]の研究が有名である．
蝶ネクタイ構造は，有向グラフに対して強連結成分の抽出を行っており，グラフ全体を流れに従っ て，７種類に分割したものである(図7.5)．これらの位置関係の形状が蝶ネクタイに似ていることから
「Bow-Tie」（蝶ネクタイ）理論と呼ばれている．
最大強連結成分である中心（CORE）にはリンクをたどってお互いに行き来できる核のような部分であ り，ユーザにとって見つかりやすいページ，特に評判が良いサイトを含まれている．スパマーはここに Webスパムページを挿入することによってページのページランクをさらに高める．
核へ到達できるが逆は不可のIN（起点）では新しく未だに参照されていないページを含む．逆に，核 から到達できるが逆は不可のOUT（終端）ではサイト内のリンクしかない企業やデータベース（ディー プWeb）を含む．さらに起点や終端に接続している「TENDRILS」，核にアクセスせずにINからOUT に接続されている「TUBE」，それ以外の「ISOLATED」の7つの部分から構成されている．
ホストのwebgraphの核以外の比較的に大きい強連結成分がスパムである可能性が高いことが斉藤
ら[22]によって報告された．
この事実によって，蝶ネクタイ構造を利用し，IN,OUT,TENDRILLS と TUBE の強連結成分を分 析する．ホストのwebgraphに対して，全ての強連結成分を利用することによって，ページのwebgraph の特定のページを超える強連結成分を利用する（実験では１００）．全てのサブグラフの判定にはSVN の分類器を用いた．
グラフの核に対して，次の節で説明するアプローチを利用した．
7.4.4 KCORE
Webgraphの核は最大のノード集合を持ち，核内の密な接続を持つサブグラフを得るため異なるアプ
ローチを取る．我々はSeidman [23]が提案したKCoreの概念を利用する．KCoreはサブグラフで，全 てのノードがサブグラフ内の他のｋノード以上と接続するものである．
ノードのcorenessは所属しているKCoreの最大のkである．その指標を計算するにはBatageljら [2]
が提案したアルゴリズムを採用している（O(m)；mはリンク数）．
KCoreの定義は元々は無向グラフに対するものであったが，有向グラフに適応する際に，KCoreの各
Core
#SCC : 1
#Pages : 28.3M 28.6%
In
#SCC : 18.7M
#Pages : 34.2M
34.5%
Out
#SCC : 2.9M
#Pages : 6.5M
6.6%
Tube
#SCC : 0.3M , #Pages : 0.7M
0.6%
Tendrils-In
#SCC : 0.3M , #Pages : 4.0M
4%
Tendrils-Out
#SCC : 5.0M , #Pages : 7.1M
7.2%
Total
#SCC : 44M, #Pages : 100M
Isolated
#SCC : 14.6M , #Pages : 18.2M
18.4%
図7.5 蝶ネクタイ
ノードはk以上のアウトリンク数，被リンク数，あるいはアウトリンク数＋被リンク数という３つの基準 を利用している．
KCore内のノード間は密な接続で結ばれており，KCoreはランダムなリンクの削除に対して基本構造
に影響が少ないため，非常にローバストなサブグラフである．特定の閾値を設定することで，密な接続を 持つサブグラフを抽出できる．これらのサブグラフを解析することでスパムサイトか非スパムのサイトを 含むサブグラフを識別可能になる．
実験結果により，ホストのwebgraphに対して，比較的に高い閾値では重要な非スパムサイトを発見で きることが分かった．ここで，非スパムのシードを獲得するために利用する．
7.4.4.1 フィーチャーベクトル
サブグラフのスパム判定を行うために，線形のサポートベクトルマシンを利用している．従来手法がホ スト単位で判定を行うという点で異なっている．
各サブグラフに対し，次のフィーチャーをまとめる．
■URLベースのフィーチャー
• URLの長さに関する基本的な統計情報
• パースの深さに関する基本的な統計情報
• ホスト名の長さに関する基本的な統計情報
• ホスト名の深さに関する基本的な統計情報
■リンクベースのフィーチャー
• 蝶ネクタイの構造分類タイプ