Mining Persistent Activity in Continually Evolving Networks
イントロ
- ネットワークは時間とともに発展する
- 交通網, コンピュータ間のネットワーク, ソーシャルネットワーク
- 既存手法は各パターンの数に注目し各々の頻度に基づいてネットワークの特性を理解しようとしている
- しかしパターンが短期な場合, 特定の時間帯でカウント数が増大してしまい異常と見做されることがある
- 一方頻度は少ないが連続的かつ定期的に起こる重要な活動もある (ネットワークへの攻撃など)
- ネットワークの理解を深めるため, パターンの持続性 (どれくらい続くか)を考慮する必要がある
- 提案手法ではエッジの変更の系列をネットワークの変化とする
- temporal motifsのアイデアを拡張しnode間のactivityを記述するactivity snippetsを導入
- エッジのactivityを考慮することは様々な応用で重要
- どの交通ルートが持続的に使われているか特定する, 怪しいノードまたはエッジを特定する等
提案手法
- 連続的に変化するネットワークを表すエッジのstreamが与えられた下で各々のactivity snippestの持続性 (持続時間, 頻度, 周期性)を推定
- まず持続性の測度の条件を整理
- 非負
- 時間幅について無限の極限をとると持続性も無限に発散する
- 発生時刻をずらしても測度に影響しない A4 時間幅を縮めると持続性が上がる
- 持続性の測度として幅, 頻度, 速度を定義し, それらの積を持続性の測度として定義
- 積を使って定義しておくと事前に設定した持続性の測度の条件を満たすことができる
- snippestのstramから持続性を保っているものを抽出するアルゴリズムを提案
実験
- 8つのネットワークデータを使って実験 (表2)
- 図4はバイクトリップデータに対する結果
- 最も持続性の高いバイクトリップ (黒)が頻度も高い
- ボストンではMITの前の通りから最寄りの地下鉄駅までのルートからのトリップが最も持続性が高い\(\leftarrow\)通勤ルートを反映
- 図4(a)(b)どちらの図でもオレンジが新しくできたバイクステーションに対応している
- ボストンではMITの目の前に新しいバイクステーションができ, すぐに人気のステーションになった
- 図5はNYCのタクシーデータに対する結果
- オレンジのバーストは台風に対応
- ブルーは立地の都合上台風の影響を免れている or 近くに病院があり台風でもタクシー需要が保たれている地域のため持続性が高い
- 図6はStack overflowにおける二人のユーザ間のコミュニケーションに対する結果
- activityは質問へのコメント, 回答へのコメント, 質問への回答の三種類ある
- 質問へのコメントは図のオレンジ (バースト)に対応, 回答は比較的持続性がある
- 図7は異常検出の結果
- 時刻 tにsnippest xが現れたら頻度と持続性を生成
- その後異常検出手法を適用 (今回はRandom Cut Forestを使用)
- 図7(a)はあるsubredditから別のsubredditへの参照に対する結果
- 特定のユーザが他のsubredditに出張して宣伝する規則的なパターンを異常として検出
- 図7(b)のタクシー乗車データにおいては規則的におこる異常パターンとしてテストドライブを検出
- 表3に異常検知の精度を比較
- Chicagoバイクトリップデータに人工的に生成した50のトリップを混ぜ, それらを検出するタスク
- 提案手法は既存手法に比べ, 連続性のある異常を精度よく検出できている
- この他にスケーラビリティも評価