読んだ：Unsupervised Social Network Spam Detection（CIKM2013)
Unsupervised Social Network Spam Detection
http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-13-6.pdf
若干読みきれてないが・・・
intro
ソーシャルネットワーク上でのスパムアカウントが増加している。
スパムアカウント抽出に関して、教師付きの学習コストを抑える
観点から、教師なしの手法が望ましい。
まず、SD2という、ソーシャルネットワーク上の関係を織り込んだ
スパム検出の手法を提案する。さらに、より高いレベルのスパム攻撃に
大して高い頑健性を持たせるために、UNIKという教師なしスパム抽出
手法を提案する。
2:データに関して
2009年のあるソーシャルブログサイトの10ヶ月分のユーザのつながりと投稿を収集
一度以上URL付きポストをしたユーザは176000人。合計で200万のURL付き
ポストがあった。
スパマーに関しては教師あり学習によって誤差1-2%程度に抽出できているらしい。
新規スパマーの増加数は極めて小さいが、投稿数は裾野広いロングテールに
なる傾向。
2.3AutoREの適用
まずはemailのスパマー検出手法を適用してみる(AutoRE)。
この手法は、URL付きのメールのポストがバーストした日数をしきい値
にしてスパマーを抽出するもの。
しきい値を小さくすると、スパマーでない人を抽出してしまい、逆に
大きくするとスパマーをうまく抽出できない。
要因として、スパマーがバースト性を持たなくなりつつあるのが原因そう。
2.4FBClusterの適用
ソーシャルネットワーク上のスパムクラスタを抽出する。
同じURLや投稿内容の類似度グラフを作成する。
この手法の場合、スパマーはうまく抽出できるが、スパマーでないひとを
スパマーだと判定してしまう結果となった。
原因として、スパマーの投稿URLの中にスパムURL以外のものを混ぜ込んで
いることがあるようだ。
3:Sylib defenseアルゴリズムの適用
Sybil attack...SNS上で大量のアカウントを作って不正行為を行うこと
3.1 SD2の提案
FBClusterがうまくいかなかったのは、スパマーがスパマーでない人と
つながってしまっているのが問題だった。これは、SybilAttackの特徴
と非常に似ている。
とはいえ、SybilDefenseの手法をそのまま適用するにはいくつが問題
がある。それは、ソーシャルネットワークがないといけないことと、
スパマーがネットワーク上に存在しているとは限らないということで
ある（なぜなら、スパマーはスパマーでない人と友達になるのは難しいから）。
そこで、SD2を提案する。これは、ソーシャルネットワークとURLの共有
関係で構築されたユーザリンクグラフを利用したものである。
・SD2のながれ
1.ソーシャルネットワーク作成
2.URLの共起で結ばれたユーザ間エッジを1に追加
3.次数３以下のノードを前処理として取り除く
4.sybilノードを低順位になるようにするために、sybil defenseを基盤とした
コミュニティ抽出法を適用する
5.sybilノードをセパレートするために、順位付けされたノードをカットする
ここで重要なのは5のカットポイントを決定することなので、今回はコンダクタンス
を基盤とした指標を使う。
あるコミュニティをAとし、その差集合をBとしたとき、コンダクタンスをA,B
間のエッジ数とする。0のとき、コミュニティA内のつながりが強く、1のとき
A内のつながりが弱いことになる。
このアルゴリズムは、スパマーでないnodeから始まり、コンダクタンスを最小化するように隣接ノードから一つ選び追加していく。
今回の方法だと最適なカットポイントが解析的に得られないのでデータから発見する。
あるノードを選んだときのコンダクタンスに対してその次のノードを選んだときのコンダクタンスの比をとると、ある程度のところまではなだらかに下がっていき、その後鋭く振動する部分が見つかるので、そこを分割点とする。
SD2は非常に高パフォーマンスをたたき出す。理由として、ソーシャルグラフの
コミュニティからスパマートそうでない人をうまく分離でき、ソーシャルグラフ
にはいなくてユーサリンクグラフにいるスパマーを抽出できているからだといえる。
しかし、SD2はsybil attackが増加するとパフォーマンスが低下する。実際に10%
のスパマーでない人をスパマーと入れ替えるとスパマーなのにスパマーと判定
できないユーザが10%増加する。
4.UNIKの提案
UNsupervised socIal networK span detection
ソーシャルグラフとユーザリンクグラフを個別に探索することでSD2の課題を
解決する。
・流れ
1.URLの共起によって作成されたユーザリンクグラフとソーシャルグラフを作成
2.ソーシャルグラフにSD2を適用し、スパマーでない人を検出する。さらに、
そのユーザらが共有するURLをホワイトリストとして登録する
3.ユーザリンクグラフをホワイトリストでトリミングし、その後残った高次数
ユーザがスパマーとなる
・ホワイトリスト作成
あるURLがあったとき、ホワイトリスト内でシェアしたユーザ数が全体のユーザ数の半数をこしていればホワイトリストに入れる。なるべくドメインやホストで構築する。
※短縮URLはどうするのだろうと思ったら、直近ですぐ解決する方法はないっぽい
・次数のしきい値決定
スパマーの方がURLを活発にシェアしやすい
リンクの重みをURLをシェアしたユーザの半数に設定
重みの設定は少量のスパマとスパマでない人を比較すればわかる。
5.評価
・ホワイトリストの作りかたについて評価。
いくつかのタイプを作ったが、domain、host、host+1path(ホストネームがホワイトリストに入っていたら、ホワイトリスト+一階層下の部分までカット対象とする)が性能が良かった。
・エッジのしきい値について
256で切るのが最も良かった。
・次に手法の性能について評価。
UNIKとSD2は非常にいい性能というかほぼ同じ性能。
ここからはUNIKの頑健性に関する評価
・sybil attackの効果
スパマーを1,2割程ネットワーク内に仕込ませても、UNIKは性能にそれほど影響は出ない。
Whitelistを使う際にHost+1Pathが最も性能がいい。hostだけだと結構性能落ちる。
・スパマーに正常なURLをもっと仕込ませたときの性能チェック
host,host+1pathともにロバストな結果
6.スパマーの分析
スパマーというか、botっぽい連投しまくるタイプのものもいれば、普通のユーザのような行動をしているものもいるように見える。そういうスパマーもうまく抽出できている。
