HipHop アルゴリズム: マイクロブログの相互作用関係を使用してソーシャル サークルをマイニングする

[[120924]]

Weibo 環境において、Weibo ユーザーのソーシャル サークルや興味サークルを自動的にマイニングする方法は、非常に基本的かつ重要な問題です。ユーザーがWeiboに反映する社会的関係を正確にマイニングできれば、多くの特定のアプリケーションに非常に役立ちます。たとえば、ユーザーの興味をより適切にマイニングしたり、ユーザーがまだフォローしていないソーシャルサークルのメンバーを推奨したり、ソーシャルサークルに応じてユーザーをより正確にパーソナライズしたり、ユーザーのパーソナライズモデルに基づいて他の推奨事項や広告プッシュのための基本的なサービスを提供したりできます。

Weibo関連の研究開発タスクでは、ユーザーのインタラクティブな行動を活用して、ユーザーのさまざまなソーシャルサークルを自動的にマイニングすることを目的としたHipHopアルゴリズムを提案しました。アルゴリズムを設計する際には、サークルマイニングアルゴリズムが以下の条件を同時に満たすことを期待します。

1. Weibo ユーザー A の場合、彼が所属するさまざまなソーシャル サークルを調べることができます。たとえば、このユーザーには同僚のサークルと専門的な関心のサークルの両方があります。

2. 同時に、別のユーザー B は、ユーザー A の異なるソーシャル サークルに属している可能性があります。たとえば、B は A の大学の同級生であり、特定の会社での同僚でもあります。この場合、B はユーザー A の 2 つの異なる興味サークルに同時に表示されることになります。

3. ユーザーのプライバシーデータは使用しないでください。ユーザーのプライバシーを保護するために、アルゴリズムがユーザーの公開行動と情報のみを使用することを望んでいます。そのため、HipHop アルゴリズムは、完全に公開されているインタラクティブな関係などの公開情報のみを使用します。

4. 社会集団は説明可能である、つまり、社会集団の性質や特徴を簡潔に説明できる。現在、社会集団ごとに異なるラベルを付けることによって区別している。

HipHop ソーシャル サークル マイニング アルゴリズムは、上記の指針に基づいて設計および開発されており、上記の制約を同時に満たすことができます。現在、公開されている参考文献には、これらの条件を同時に満たすことができる関連するソーシャル サークル マイニング アルゴリズムはほとんどありません。

関連記事: Weibo の背後にあるビッグデータの原理を探る: Weibo の推奨アルゴリズムの簡単な紹介>>>

一般的なソーシャルサークルマイニングアルゴリズム

ソーシャル サークル マイニングは、現在のソーシャル ネットワーク研究において非常に典型的で人気のある研究タスクであり、「コミュニティの発見」と呼ばれることもあります。学術界もこの問題を解決するための多くのアルゴリズムを提案してきました。一般的に言えば、それらは「単一コミュニティ」方式と「マルチコミュニティ」方式の 2 つのカテゴリに分けられます。いわゆる「単一コミュニティ」方式とは、ネットワーク構造内のノードが特定のコミュニティにのみ属することができ、複数のコミュニティに属することは許可されないことを意味します。 「マルチコミュニティ」方式では、ユーザーは同時に複数のコミュニティに所属できます。以下では、GNアルゴリズムと「最大クリーク構造」を代表として、これら2種類のアルゴリズムの考え方を簡単に紹介します。

GNアルゴリズム

GN アルゴリズムは、グラフ構造におけるコミュニティの自動検出に非常によく使用されるアルゴリズムです。2002 年に Girvan と Newman によって最初に提案され、その有効性から広く使用されてきました。

GN アルゴリズムの基本的な考え方は、グラフ構造において、まず各エッジの「媒介性」を計算し、次に「媒介性」が最大のエッジをグラフから削除し、このサイクルを継続的に繰り返して、現在最大の「媒介性」を持つエッジを繰り返し削除し、最終的に発見されたコミュニティが形成されるというものです。エッジのいわゆる「媒介性」は、グラフ内の任意の 2 つのノード間の最短パスがこのエッジを通過する回数を指します。エッジの「媒介度」が大きいほど、このエッジが 2 つ以上のコミュニティまたはサークルを接続する冗長エッジである可能性が高くなります。したがって、「媒介度」の高いエッジを継続的に削除することで、コミュニティを分離する目的を達成できます。

GN アルゴリズムは効果的なアルゴリズムですが、「単一コミュニティ」の検出方法です。つまり、グラフ内の特定のノードは、固定されたコミュニティにのみ属することができ、同時に複数のコミュニティに属することはできません。これは、実際のアプリケーション シナリオの要件とはまったく異なり、アルゴリズムの制限を形成します。

「最大クリーク構造」アルゴリズム

「最大クリーク」は、「マルチコミュニティ」検出を実行できる一般的なアルゴリズムです。つまり、グラフ内のノードは同時に複数の異なるコミュニティに属することができます。

「最大クリーク構造」は、グラフの位相構造を分析し、「最大クリーク」特性を満たすサブグラフ構造、つまり最大の完全接続サブグラフを見つけます。各「最大クリーク」は、発見されたコミュニティです。

「最大クリーク構造」アルゴリズムは、ノードが複数のコミュニティに属していることを検出でき、「単一コミュニティ」検出方法よりも実用性と適用シナリオが広くなっていますが、このアルゴリズムには制限があります。「最大クリーク構造」では、完全に接続されたサブグラフ、つまりサブグラフ内の任意の 2 つのノードがエッジで接続されていることが必要であり、これは非常に強い制約です。実際のアプリケーション グラフでは、このような強い制約を満たすグラフ構造は小さいか少数であることが多く、その結果、このアルゴリズムのグラフ内の多くのノードを特定のコミュニティに分類できなくなります。

HipHop アルゴリズムも、特定のステップで「最大クリーク構造」という考え方を採用していますが、技術的な手段を通じてこの制約を緩和し、その効果を効果的に向上させています。

ヒップホップアルゴリズムを使用してWeiboのソーシャルサークルを発見する

Hiphop アルゴリズムは、Weibo ユーザー間のインタラクティブな関係を使用して、ユーザーのさまざまなソーシャル サークルを自動的にマイニングします。ここでの「インタラクション」は一般的な用語です。具体的なインタラクションの内容には、Weibo の転送、Weibo へのコメント、他のユーザーへの @ などがあります。ユーザー A とユーザー B が上記のいずれかの行動をとった場合、両者はインタラクション関係にあるとみなされ、その頻度に応じてエッジに異なる強度を与えることができ、これは 2 人のユーザー間の社会的親密度の度合いを表します。

ソーシャルサークルをマイニングするためにソーシャル関係を使用する理由は、次の基本的な仮定に基づいています。Weibo ユーザーとやり取りしたことがあるさまざまな小グループがあり、小グループのメンバー間のやり取りは密接ですが、異なる小グループのメンバー間のやり取りは少ないです。たとえば、大学の同級生は Weibo で互いに交流することが多いですが、同僚と交流することはほとんどありません (図 1 を参照)。これは単なる仮定ですが、実際のマイニング結果は、この仮定がほとんどの場合に有効であることを示しています。

HipHop アルゴリズムの技術的なプロセスは、順番に 3 つのステップに分けられます。

ステップ1: ユーザーが直接やり取りする他のユーザーの中で「最大のグループ構造」を見つける

まず、WeiboユーザーAの場合、Weibo上でユーザーAと直接やり取りしたすべてのユーザーが直接やり取りセットSを形成します。このステップでは、集合 S 内の複数の「最大グループ構造」を見つけようとします。つまり、複数の小グループのコアメンバーをマイニングしようとします。

セット S 内のノードについては、それらの相互の相互作用に基づいてグラフ G を構築することができ、これに基づいて、グラフ G 内の「最大クラスター構造」をマイニングできます。いわゆる「クラスター構造」は、グラフ G に含まれる完全に接続されたサブグラフです。たとえば、グラフ G の 3 つのノード {a、b、c} のうちの任意の 2 つが相互作用関係にある場合、3 つのノードの「クラスター構造」が形成されます。いわゆる「最大クラスター構造」とは、ある「クラスター構造」T に対して、グラフ G 内で他のノード n を見つけることが不可能であることを意味します。n が T に含まれる場合、より大きな「クラスター構造」が形成されます。たとえば、上記の 3 ノードのクラスター構造で、ノード d があり、このノードが a、b、c と対話関係にある場合、{a、b、c、d} は 4 ノードの「クラスター構造」を形成し、{a、b、c} と対話できるノードが見つからない場合は、{a、b、c} は 3 ノードの「最大クラスター構造」になります。

グラフの「クリーク構造」は、グラフ内の任意の 2 つのノードが相互関係を持つことを要求するため、非常に強い制約となります。ステップ 1 で見つかったユーザー A の「最大グループ構造」の物理的な意味は、ユーザー A と密接に関係するユーザーの間で、密接に接続された小さなグループであるということです。

ステップ2：直接相互作用するユーザーの集合における「最大グループ構造」の拡張

ステップ 1 では、ユーザー A と直接やり取りしたセット S 内で形成された「最大グループ構造」を見つけます。これに基づいて、ステップ 2 では、発見された各「最大グループ構造」をセット S の範囲内に拡張し、特定の「最大グループ構造」に属する他のユーザーをさらに見つけます。具体的な拡張方法は以下の通りです。

複数のユーザーを含む特定の「最大グループ構造」T の場合、まず、T 内のユーザーとやり取りしたことがあり、セット S にも含まれる他のユーザーを検索します。このセットを U と呼びます。 U 内のユーザー w については、「最大グループ構造」T に拡張する必要があるかどうかを判断する必要があります。現在の判断基準では、次の式が採用されています。

G は、ユーザー w を最大クリーク T に融合して形成された新しいグラフであると仮定します。式の分子は、新しいグラフ G 内のすべてのノードの内部エッジの重みの合計を表し、分母は、グラフ G 内のすべてのノードとグラフ G の外部のノードによって形成されたすべてのエッジの重みの合計を表します。 Utility(G)関数が、拡張されたノードwのない元のグラフ構造Tのユーティリティ関数Utility(T)よりも大きい場合、ノードwをTに拡張することが合理的であると考えられます。それ以外の場合は、ノードwをグラフTに拡張すべきではありません。この関数を標準として使用すると、セット U 内のどのユーザーをグループ構造 T に拡張し、どのユーザーを破棄するかがわかります。

上記の式を判断基準として採用する理由は、前述のように、社会的なサークルのメンバー間の交流は密接であるが、サークルのメンバーとサークル外のメンバー間の交流はあまり密接ではないという仮定に基づいています。上記の式は、この基本的な仮定を具体的に表現したものです。分子はサークルのメンバー間の関係の親密さを測り、分母はサークルのメンバーとサークル外のメンバー間の関係の親密さを測ります。式からわかるように、サークルのメンバー間の相互作用が多くなり、サークル外のメンバーとの相互作用が少なくなると、効用関数は大きくなり、サークルがより近くなることを意味します。

上記の式を使用して、セット U 内の後続のすべての拡張ユーザーに対して、このユーザーを「最大グループ構造」T に拡張するかどうかの決定を行うように判断および選択すると、T の拡張ラウンドが完了し、新しい拡張セット T' が形成されます。 T' の場合も、上記の拡張方法を採用して、外側に連続的に拡張することができます。 「最大グループ構造」T の拡張の終了条件は、セット U 内のすべてのユーザーに対して拡張しないという決定が下された場合、拡張境界に到達し、拡張を停止して最終的な拡張結果を形成できることです。

ステップ 1 で見つかった「最大クラスター構造」がすべて上記の方法で拡張されると、ステップ 2 のタスクは完了します。上記のプロセスから、ステップ 2 はステップ 1 の拡張段階であることがわかります。

ステップ3: ユーザーと「二次的なインタラクション」関係にある他のユーザーのセットを拡張する

ユーザー A のいわゆる「二次インタラクション」ユーザー セットとは、ユーザー A と直接インタラクションするユーザーを指し、セット S を形成するユーザーと、セット S 内の任意のユーザーとインタラクティブな動作を行う他のすべてのユーザーが二次インタラクション セットを形成します。

ステップ 2 の結果、「最大グループ構造」の拡張が完了し、直接やり取りするユーザーの集合内にさまざまなソーシャル サークルが見つかりました。ステップ 3 では、まず直接インタラクション ユーザー セット S を二次インタラクション ユーザー セットに拡張し、次にステップ 2 と同様の方法を使用して外側に拡張し続けます。これにより、HipHop アルゴリズムの最終結果が形成され、ユーザー A の複数の異なるソーシャル サークルが形成されます。また、他のユーザー B は、同時にユーザー A の複数のソーシャル サークルに属する可能性があります。

上記の 3 つのステップにより、Weibo の相互作用関係を通じてユーザーの社会的関係サークルを自動的にマイニングできます。膨大な数のWeiboユーザーの場合、各ユーザーに対して上記の手順を順番に実行することで最終結果が得られますが、これは大規模な並列コンピューティングを採用することで迅速に達成できます。

以下では、HipHop アルゴリズムを説明するために具体的な例を使用します。 「Kai-Fu Lee」を例に、上記の手順と中間出力結果について説明します。

ステップ 1 では、まず「Kai-Fu Lee」と交流した Weibo メンバーを見つけてセット S を形成し、次にセット S 内の「最大グループ構造」を見つける方法を使用して、最初の 5 つの「最大グループ構造」を取得します。

• 最大グループ1（イノベーションワークス関連）：王昭慧/蔡雪勇/周元/張良/徐磊ライアン
• 最大グループ2（インターネットメディア関連）：ケソはXX/牛力雄/金雷
• 最大グループ3（金融投資関連）：徐小平/愛国者馮軍/潘世宜/楊蘭
• 最大グループ4（イノベーションワークス関連）：Lang Chunhui/Luo Chuan/Yuan Cong iw/AppHui
• 最大グループ5（起業家関連）：曹国偉/江南春/呉正柏/江希臥

ステップ 2 の後、元の 5 つの最大グループがセット S 内で拡張されます。元の最大グループはそれぞれさまざまな程度に拡張され、新しく拡張されたメンバーの数は 3 から 10 の範囲になります。

ステップ 3 では、まず、直接的なインタラクション メンバー セット S を二次的なインタラクション メンバー セットに拡張します。つまり、セット S のメンバーとインタラクションしたマイクロブログ ユーザーの新しい大きなセットを形成します。前述の拡張方法により、当初の 5 つの「最大グループ構造」がさらに拡張され、最終的に 48 ～ 150 人のメンバーからなるさまざまな社交サークルが形成されました。

手動評価の結果、HipHop アルゴリズムによってマイニングされたソーシャル サークルは、社会的結束度が高く、アルゴリズム設計の開始時に設定されたいくつかの制約も満たしているため、非常に実用的です。同時に、多数の事例を分析した結果、Weiboで形成される社会的関係とIMで形成される社会的関係には大きな違いがあることがわかった。ほとんどのユーザーのWeiboでの社会的関係は主に同僚関係と興味関係であるのに対し、IMで形成される社会的関係は主に親戚、友人、同僚、クラスメートなどのオフライン関係である。これはソーシャルメディアと従来のソーシャルネットワークの違いを反映しているのかもしれない。

元のソース: http://blog.csdn.net/malefactor/article/details/9201505