Weiboはどのように実装されていますか? Weiboの背後にあるアルゴリズム

Weiboは多くの人が利用するソーシャルアプリケーションです。毎日Weiboを閲覧する人は、オリジナル、転送、返信、閲覧、フォロー、@などの操作を毎日行っています。このうち、最初の 4 つは短いブログ投稿用で、3 番目の「フォロー」と「@」はユーザー間の関係用です。誰かをフォローすると、その人のファンになり、その人はあなたの友達になります。誰かを「@」すると、その人にあなたの Weibo 情報を見せたいという意味になります。

Weibo は「セルフメディア」、つまり一般の人々が自分に関する「ニュース」を共有する手段であるとみなされています。最近、自己メディアへの影響力を利用して利益を得ようとする人々が数多く報告されています。では、Weibo での個人の影響力はどのように計算されるのでしょうか? Weibo には、目に見えない手のように私たちを管理している他のアルゴリズムはありますか?私たちのそれぞれの行動はアルゴリズムにどのような影響を与えるのでしょうか?

直感的に言えば、Weibo は実際には人間社会の単純な縮図です。Weibo ネットワークのいくつかの特徴は、私たちに実際のソーシャル ネットワークの法則を理解するインスピレーションを与えてくれるかもしれません。ソーシャル ネットワークの爆発的な発展により、「ソーシャル コンピューティング」、特にソーシャル ネットワーク分析がデータ マイニングの新たな寵児となりました。以下では、Weibo ネットワーク分析のアルゴリズムをいくつか簡単に紹介します。そのうちのいくつかは、他のソーシャル アプリケーションにも適用できる可能性があります。

ラベルの伝播

Weiboには膨大な数のユーザーがおり、人によって興味の対象は異なります。各ユーザーの興味を調査することで、より正確な広告やコンテンツの推奨が可能になります。各ユーザーの興味を取得するために、ユーザーにタグを付けることがあります。各タグはユーザーの興味を表し、ユーザーは 1 つ以上のタグを持つことができます。最終的なユーザー ラベルを取得するには、最初の仮定を立てます。

各ユーザーの友人（またはファン）のうち、大多数はユーザーと同じ興味を持っています。

ここで、この記事で紹介する最初のアルゴリズム、ラベル伝播アルゴリズムについて説明します。このアルゴリズムでは、各ユーザーのタグは、そのユーザーの友人やファンの間で最も多くのタグが付けられた 1 つ以上のタグから取得されます。もちろん、友達のタグとファンのタグの両方を考慮することができ、それらを統合する際には、友達のタグとファンのタグに異なる重みを与えることを検討できます。ラベル伝播アルゴリズムのプロセスは次のとおりです。

1) 一部のユーザーに初期ラベルを付与します。

2) 各ユーザーについて、そのユーザーの友人やファンのタグの数を数え、最も多く表示される 1 つ以上のタグをユーザーに割り当てます。

3) ユーザーのラベルが大幅に変化しなくなるまで、手順 2 を繰り返します。

ユーザーの類似度の計算

ラベル伝播アルゴリズムは実装が比較的簡単ですが、その欠点は、仮定が事実と一致しない場合、たとえば、社交上の礼儀として、私たちは通常、親戚や友人をフォロー対象に追加しますが、これらの人々は私たちと同じラベルを持っていない可能性があり、アルゴリズムの結果が非常に悪くなることです。解決策は、ユーザー間の類似性を計算することで、友人やファンのタグがユーザー タグにどの程度貢献しているかを測定することです。そこで、2 番目の仮説が成り立ちます。

友人やファンがユーザーに似ているほど、そのタグがユーザーのタグである可能性が高くなります。

では、ユーザー間の類似性をどのように測定するのでしょうか?これには、転送されたものやオリジナルのものも含め、ユーザーが投稿したWeiboの情報を考慮する必要があります。ここでは、ユーザーのマイクロブログ間の類似性ではなく、ユーザー間の類似性を考慮する必要があります。そのため、実際の計算では、特定のユーザーのマイクロブログ情報をすべてまとめて計算します。オプションの方法として、バッグオブワード法を使用してマイクロブログ情報を単語ベクトルとして表現し、コサイン法などを直接使用して類似度を計算する方法があります。しかし、この方法は単純すぎるため、良い結果を得るのは容易ではありません。ここでは、LDA（潜在ディリクレ配分法）に基づく類似度計算方法を紹介します。

LDA は、テキストを表現するために依然として bag-of-words 方式を使用しますが、中間にトピック レイヤーを追加して、「ドキュメント - トピック - 単語」の 3 層確率モデルを形成します。つまり、各ドキュメントはトピックの確率分布と見なされ、トピックは単語の確率分布と見なされます。 LDA モデルでは、ドキュメントは次のように生成されると考えられます。

1) 各文書について:

2) トピック分布からトピックを抽出する。

3) トピックの単語分布から単語を抽出する。

4) ドキュメント内のすべての単語が生成されるまで、手順 2 と 3 を繰り返します。

LDA モデル パラメータの推定アルゴリズムは、この論文の範囲外です。ここで知っておくべきことは、LDA を使用して各ユーザーの Weibo 情報のトピック分布を取得できることです。次に、コサイン法やKL距離などの類似度計算方法を使用して、ユーザー間のトピック分布の類似度を取得し、これをユーザー間の類似度として使用します。この類似性は、ラベル伝播の重み付けに使用されます。

#p#

時間要因とネットワーク要因

上記のアルゴリズムの欠点は何ですか?

時間が経つにつれて、ユーザーの興味は変化します。ユーザーの類似性を計算する際に、毎回すべてのWeibo情報を集約するのは合理的ではありません。この目的のために、現在の時刻に近い N 個のマイクロブログが選択されます。たとえば、各ユーザーについて、現在の時間に最も近い 50 件のマイクロブログが選択され、LDA トレーニング用にグループ化されます。ここで、N は大きすぎても小さすぎてもいけません。大きすぎると、ユーザーの興味の一時的な変化を反映しにくくなります。小さすぎると、ユーザーがマイクロブログを投稿するランダム性によって、興味のドリフトが起こりやすくなります。効果を最大化するために、固定の N に固執する必要はありません。たとえば、マイクロブログ投稿の時系列に応じて、各ユーザーに対して N の値を調整することを検討できます。

これまでのところ、このアルゴリズムはWeibo関係における返信、転送、@などで構成されるネットワーク情報を考慮していませんでした。転送を例にとると、ユーザーが友人のWeiboを頻繁に転送する場合、ユーザーと友人間の類似度は、ユーザーと他の友人間の類似度よりも高くなるはずです。これは仮定 3 とみなすことができます。

ユーザーが友人のWeiboを転送する頻度が高いほど、ユーザーと友人の興味の類似性が高くなります。

同様に仮説4も得られます。

ユーザーの Weibo でユーザーを @ する頻度が高いほど、ユーザーと友人間の興味の類似性が高くなります。

これは類似性を計算するための別の要素を提供します。従来の類似度計算方法に新たな要素を加える方法は数多くあり、例えば転送頻度を数値として定量化し、類似度測定に重みとして加えることなどが考えられます。
コミュニティの発見

Weiboコミュニティとは、Weibo上で親密な関係にある人々のグループを指します。コミュニティ内の人々は密接につながっていますが、コミュニティ間のつながりは比較的まばらです。ここでの親密な関係には 2 つの意味があります。1 つ目は、コミュニティ内の人々の興味が非常に似ていることです。2 つ目は、コミュニティ内の人々の関係が親密である必要があることです。たとえば、コミュニティ内の 2 人のユーザーは 2 度以上のつながりを持つことはできず、2 度目のつながりは友人の友人を指します。

興味の類似性については上で説明しましたが、関係の類似性はユーザー間の注目関係を利用して計算する必要があります。ユーザーのフォロー関係を一方向のチェーンとして捉えると、すべてのWeiboユーザー間の関係は巨大な有向グラフとして表すことができます。ユーザー間の最短経路の逆数を使用するなど、ユーザー間の関係の類似性を簡単に考慮することができます。しかし、この方法は正確ではありません。現実の世界では6次理論があり、Weiboなどのソーシャルネットワークでは関係がより親密になることが多いことがわかっています。したがって、この単純な関係の類似性は最大で 6 つの離散値しか持てず、明らかに十分な精度ではありません。

より良い結果を得るために、最短パスを明示的なメトリックとして使用するだけでなく、いくつかの暗黙的なメトリックも考慮されます。ここに 2 つの仮説、仮説 5 と仮説 6 があります。

2 人のユーザーが持つ共通の友人の数が多いほど、2 人の友人間の関係は類似していることになります。

ここでは、Jaccard 類似度の計算方法を参照し、これら 2 つの仮説の量子化関数を、共通部分のサイズと和集合のサイズの商として表現することができます。仮説 5 を例にとると、その定量的指標は共方向類似度とも呼ばれ、2 人のユーザーの共通の友人の数を 2 人のユーザーのすべての友人の数で割ることによって定量化されます。仮説6の定量的指標は共方向性類似度と呼ばれ、その計算方法は共方向性類似度と同様である。重要性の点では、これら 2 つの類似性は関係性の尺度であるだけでなく、ある程度、ユーザー間の興味の類似性も測ります。直感的に言えば、2 人のユーザーが共通してフォローしている友達が多いほど、興味の類似性は高くなります。これら 2 種類の類似性には、構造シナリオに基づく類似性計算という専門的な名前もあります。

最短パス類似度、共方向性類似度、共方向性類似度を取得した後、重み付け関数を使用してそれらを組み合わせて、最高の類似度を取得できます。その後、K-Means、DBSCAN などのいくつかのクラスタリング アルゴリズムをクラスタリング操作に使用して、最適なコミュニティ クラスターを取得できます。類似度重み付けラベル伝播アルゴリズムを使用して、同じラベルを持つ人々をコミュニティとして扱うこともできます。
影響計算

コミュニティの発見では、Weibo の関係ネットワークを使用すると、類似度の計算の精度が向上します。しかし、関係ネットワークで実行できることは数多くあり、影響力の計算はより重要なアプリケーションの 1 つです。

影響力の計算に関しては、Web ページのランキングで使用されるアルゴリズムを借用します。ウェブページのランキングで最もよく知られているアルゴリズムは PageRank です。これは Google の創設者であるラリー・ペイジとセルゲイ・ブリンによって発明され、Google の商業的成功とともに有名になりました。このアルゴリズムは、ウェブページ間のリンクに基づいてウェブページのランキングを決定します。その中核となるのは、高品質のウェブページが指し示すウェブページも高品質でなければならないという仮定です。

PageRankの考え方に基づいて、Weiboへの影響についての仮説7が得られます。

影響力の高いユーザーがフォローしているユーザーも、影響力が高いはずです。

ユーザーを PageRank の Web ページと考え、フォローアップ関係を Web ページ内のリンク関係と考えます。したがって、PageRankアルゴリズムのプロセスに従って、Weibo注目度ネットワーク上の影響力計算アルゴリズムを取得できます。

1) すべてのユーザーに同じ影響力の重みを与える。

2) フォローしている人数に応じて各ユーザーの影響力の重みを均等に分配します。

3) 各ユーザーの影響力は、そのユーザーのファンが割り当てた重みの合計に等しくなります。

4) 重みに大きな変化がなくなるまで、手順 2 と 3 を繰り返します。

ウェブページのランキングには、HITS アルゴリズムや HillTop アルゴリズムなど、ネットワーク関係に基づいた他のアルゴリズムもあります。これらのアルゴリズムも影響力の計算に使用できます。

#p#

上記のアルゴリズムの欠点は何ですか?

人間関係のネットワークだけに基づくと、必然的にファン数の多い人が影響力を持つという状況が生まれやすいでしょう。これにより、一部のユーザーは高い影響力を得るためにゾンビファンを購入することになります。このようなアルゴリズムでは、使用されない情報が多すぎるため、実際の状況に対処できないことは明らかです。

ユーザーの影響力は、Weibo での人間関係に加え、ユーザーの活動レベルやマイクロブログ投稿の質など、個人の属性とも密接に関係しています。ユーザーのアクティビティはマイクロブログ投稿の頻度で測定でき、マイクロブログ投稿の品質は再投稿と返信の数で測定できます。これらの値を測定し、上記のアルゴリズムの結果を追加することで、より正確な影響結果を得ることができます。

もちろん、ユーザー間の返信関係、転送関係、@ 関係もすべてネットワークを形成できると考えることもできます。また、それらには対応する仮定、つまり仮定 8、仮定 9、仮定 10 もあります。

ユーザーの影響力が大きければ大きいほど、マイクロブログの返信の影響力も高くなり、マイクロブログの所有者の影響力も高まります。

ユーザーの影響力が大きければ大きいほど、そのユーザーが再投稿するマイクロブログの影響力も大きくなり、マイクロブログの元の投稿者の影響力も高まります。

影響力の高いユーザーは、Weibo の投稿で影響力の高いユーザーを @ する傾向があります。

このようにして、転送ネットワーク、返信ネットワーク、@ ネットワークの 3 つのネットワークが得られます。 PageRank アルゴリズムを参照することで、他の 3 つの影響結果を取得できます。これらを関係ネットワークの影響結果と組み合わせることで、最終的な影響結果を得ることができます。ここでの融合は単純に結果の加重合計として考えることができ、複雑な融合方法はこの論文の範囲を超えています。
トピック要因とドメイン要因

影響力を計算する方法がわかったので、次に何ができるでしょうか?

現在のホットトピックの影響を分析し、Weibo***で現在のホットトピックになっている人についての意見を得ることができます。具体的なアプローチとしては、現在のホットなトピックに関連するマイクロポストを見つけ、次に現在のホットなトピックに関与しているユーザーを見つけることです。現在のホットなトピックに関連するマイクロ記事を見つけるにはどうすればよいでしょうか?言うまでもなく、トピックタグ付きのマイクロポストでも、トピックタグなしのマイクロポストでも、上で紹介した LDA アルゴリズムを使用できます。このアルゴリズムは、ユーザーのすべてのマイクロポストのトピック分布を見つけることができ、マイクロポストのトピック分布を見つけることもできます。一般的に、マイクロポストの単語数は 140 に制限されており、比較的短いため、マイクロポストに含まれるトピックの数はそれほど多くありません。マイクロポストのトピック分布で最も確率の高いトピックをトピックとして取ることができます。

トピックに対応するマイクロポストとユーザーを見つけたら、影響力計算アルゴリズムを実行して、トピックでより大きな影響力を持つユーザーを取得できます。これは世論監視やソーシャルホットスポット監視の一側面でもあります。

ラベル伝播アルゴリズムによって得られた結果に対して、同じラベルの下にあるユーザーに対して影響度計算アルゴリズムを実行し、ラベル下の影響度ランキング、つまり分野内での影響度ランキングを取得します。例えば、李開復のあらゆる分野における影響力は最高ではないかもしれませんが、IT の分野では、彼の影響力は間違いなく最高レベルにあります。
スパムユーザーの識別

影響力の計算では、影響力の計算におけるゾンビユーザーの干渉を避ける必要があると述べられています。アルゴリズムでは、影響力を計算する際にそのようなユーザーを識別して除外できれば、効果が向上するだけでなく、計算量も削減できます。

影響度の計算と同様に、スパム ユーザーの識別では、ユーザー属性とリンク関係の両方を考慮する必要があります。

スパムユーザーには、通常のユーザーとは異なる統計的特性がいくつかあります。たとえば、次の点です。

Ø スパムユーザーは通常、一定の時間的規則性を持ってマイクロブログを投稿します。これはエントロピーを使用して測定できます。エントロピーはランダム性の尺度です。ランダム性が大きいほど、エントロピーは小さくなります。具体的なアプローチとしては、一定の粒度でタイムスライス統計を実行して各タイムスライスのブログ投稿の確率を取得し、その確率に基づいてエントロピー値を計算することです。エントロピー値が大きいほど、ユーザーがマイクロブログを投稿する時間が規則的になり、スパムユーザーである可能性が高くなります。

Ø 一部のスパムユーザーは、マイクロブログで悪意を持って他の人に @ する傾向があるため、一部のスパムユーザーのマイクロブログで使用される @ の割合は、一般ユーザーよりも高くなります。

Ø 一部のスパムユーザーは、広告宣伝のためにマイクロブログに大量の URL を追加します。マイクロブログ内の URL の割合で測定できます。一部のユーザーは、URL のクリックを欺くために、マイクロポストの内容を URL の対応するインターフェースの内容と矛盾させます。この場合、マイクロポストと URL の内容の一貫性の度合いを判断する必要があります。簡単な方法は、バッグオブワード法を使用してマイクロポストと URL の対応するインターフェースを単語ベクトルとして表し、マイクロポスト内の単語が URL の対応する Web ページに表示される頻度を確認することです。

Ø 広告やプロモーションに携わっているユーザーの場合、マイクロポストも広告かどうかを分類して判断できます。ユーザーのマイクロポストのかなりの部分が広告である場合、そのユーザーはスパムユーザーである可能性があります。

Ø スパムユーザーは通常、ランダムにユーザーをフォローするため、ファン数と友達数の比率が通常のユーザーとは異なります。さらに、通常のユーザーは通常、友情を通じて友達を追加するため、注目の三角形が形成されます。たとえば、A が友達 B が C をフォローしているのを見て、A も C をフォローすると、A が B、C をフォローし、B が C をフォローするという三角形が形成されます。一般的に言えば、スパム ユーザーの注目はランダムであるため、その注目三角形の割合は通常のユーザーのそれとは異なります。

もちろん、スパムユーザーと通常のユーザーの違いはこれ以外にもたくさんありますが、この記事ではそれらを一つ一つ列挙することはしません。スパムユーザーの識別は、本質的にはバイナリ分類の問題です。これらの属性を取得したら、この情報をロジスティック回帰 (LR)、決定木、ナイーブベイズなどの機械学習分類モデルに入力して分類することができます。

もちろん、リンク情報はまだ使用されていません。一般的に、スパムユーザーは通常のユーザーをフォローしますが、通常のユーザーはスパムユーザーをフォローしません。これは仮説11です。

通常のユーザーはスパムユーザーをフォローする傾向はありません。

このようにして、PageRank アルゴリズムを再度使用して、ユーザーがスパム ユーザーであるかどうかの確率を計算できます。ここで注目すべきは、アルゴリズムは上記の分類器の結果を使用して初期化され、スパム ユーザーの確率は 1 に設定され、通常のユーザーの確率は 0 に設定されていることです。 PageRank の計算プロセスでは、単純な合計式は使用できません。たとえば、ユーザーが複数のスパム ユーザーをフォローしている場合、合計確率は 1 より大きくなる可能性があります。したがって、確率を更新するには、何らかの正規化方法または指数族関数が必要です。

結論

この記事では、Weibo の一般的な問題に対応するアルゴリズムを簡単に紹介します。実際のアプリケーションでのアルゴリズムは、紹介したものよりもはるかに複雑です。もちろん、この記事では、友人の推奨、ホットスポットの追跡など、すべてのトピックを網羅しているわけではありません。しかし、昔の人は「全体像を垣間見ることで全体像が明らかになる」と言いました。この記事の紹介が、Weibo などのソーシャル ネットワーキング アプリケーションをよりよく理解するのに役立つことを願っています。

本文全体を通して、私たちの直感と一致していると思われる仮定が太字で示されています。これらに基づいて、多くの効果的なアルゴリズムを導き出すことができます。したがって、発見する意欲がある限り、アルゴリズムはあなたのすぐそばにあることがあります。