Facebookの詐欺行為と戦う方法を学び、CopyCatchアルゴリズムがLockstepをどのように解決するかを見てみましょう

[51CTO.com クイック翻訳] インターネットが誕生して以来、あらゆる種類のジャンク情報や悪意のある情報がインターネット上に流通してきました。あらゆる種類のスパム、不正行為、さらには詐欺的な情報への対処は、すべてのインターネット企業が解決しなければならない問題となっています。特に、さまざまなソーシャル ネットワーキング サイトの台頭により、不正行為防止とインターネット セキュリティは、研究コミュニティと業界コミュニティの両方が直面する課題となっています。大手インターネット企業は、毎日発生する不正行為対策に対処するために、専用の不正行為対策チームを設立しています。

[[204459]]

不正行為防止で最も一般的に使用される技術の 1 つはグラフ理論アルゴリズムであり、不正行為防止の問題は多くの場合グラフ理論の問題に還元できます。たとえば、SVD 法を使用してグラフの隣接行列を分解したり、グラフ トラバーサル アルゴリズムを使用して不正行為を検出したりできます。特に金融分野では、グラフ理論アルゴリズムはリスク管理や接触損失の修復に使用できます。

Facebookは世界最大のソーシャルメディアサイトとして、サイト上の詐欺や不正行為に積極的に対処しようと努めてきました。 CopyCatch は、2013 年に有名な国際会議 WWW で Facebook が発表した不正行為防止に関する論文です。この論文では、Lockstep と呼ばれる不正行為に対処するために Facebook が使用するアルゴリズムについて説明しています。

ロックステップ動作とは、短期間に多数のユーザーがページを「いいね！」した状態を指します。ロックステップ動作を検出するには、そのようなユーザーとページのコレクションを検出することが問題になります。 Facebook が不正行為防止アルゴリズムをどのように設計しているかを見てみましょう。

まず、二部グラフを構築します。二部グラフには 2 種類のノードがあります。1 つはユーザー、もう 1 つは Facebook ページです。 Facebook ユーザーがページに「いいね！」すると、ユーザーを表すノードとページを表すノードの間にエッジが構築されます。ロックステップ動作は数学的に次のように記述できます。

この問題自体は、二部グラフ内の二部コアを検出する問題に変換できます。二部コアを検出する問題自体は NP 困難な問題であるため、この問題を解決するための近似アルゴリズムを設計する必要があります。 Facebook はこの問題を *** 問題として位置付けました。

まず、問題の説明を再定義します。

この問題は、次の最大化問題に簡略化できます。

ここで、L はページ上のユーザークリックの時間行列を表し、c は不正ユーザーの不正行為の中心ベクトル、P' は不正ページのセットです。この最大化問題の本質は、クラスターの中心 c とページのサブスペース P' を選択して、クラスター内の特定の時間ウィンドウ内でのユーザー数とユーザーのような動作を最大化することです。この問題を解決するために反復アルゴリズムが使用されます。アルゴリズムの最初のステップはクラスター中心 c を選択することであり、アルゴリズムの 2 番目のステップは c に基づいて P' を選択することです。アルゴリズムのフレームワークは次のとおりです。

UpdateCenter 機能のプロセスは次のとおりです。

UpdateCenter 関数の基本的な考え方は、現在のクラスター センターの範囲内でクラスター センターを再選択して、新しいクラスター センターがより多くのユーザーとより多くのいいねをカバーできるようにすることです。

FindUsers 関数のフローは次のとおりです。

FindCenter 関数のフローは次のとおりです。

FindCenter 機能の基本的な考え方は、ページに関連付けられたユーザーを、そのページを「いいね！」した時間に従って二部グラフで並べ替え、指定された時間枠内でのユーザー サブセットの「いいね！」行動の最大値を調べることです。新しいクラスターの中心点をユーザー サブセットの中心に設定します。

UpdateSubspace 関数のフローは次のとおりです。

UpdateSubspace 関数の基本的な考え方は、現在の不正ページ サブセットの外側のページを調べて、不正の可能性が高いページがあるかどうか (つまり、関連付けられている不正ユーザーが現在の不正ページに対応するユーザーのスーパーセットであるかどうか) を確認することです。不正の可能性がある場合は、現在のページを新しいページに置き換えます。

著者は Map-Reduce バージョンを次のように提供しています。

CopyCatch アルゴリズムは非常に速く収束します。Facebook データセットでは、アルゴリズムは約 10 回の反復で収束します。

FacebookのCopyCatchアルゴリズムは概念と実装が比較的シンプルで、オンライン操作を通じてオンライン要件を満たすことが確認されており、優れたアルゴリズムです。このアルゴリズムはしばらく前に公開されましたが、今でも実用的な参考価値を持っています。

CopyCatch アルゴリズムはグラフ理論の関連知識を使用します。現在、グラフ理論は詐欺防止・不正行為防止・情報セキュリティなどの分野で広く利用されています。グラフ理論を熟知することは、ビッグデータや人工知能の実践者にとって不可欠なスキルとなっています。この記事がインターネット業界の関連実務者に貴重な経験を提供できることを願っています。

元のタイトル: CopyCatch: ソーシャル ネットワークでのロックステップ行動を検出してグループ攻撃を阻止する

著者: Alex Beutel、Wanhong Xu、Venkatesan Guruswami、Christopher Palow、Christos Faloutsos

[51CTOによる翻訳。パートナーサイトに転載する場合は、元の翻訳者と出典を51CTO.comとして明記してください]