php - ユーザーのフォロワーからユーザーの重要性または「Betweenness Centrality」を計算しますか?

Question

他のユーザーとのつながりに基づいて、最も接続されているユーザーや最も価値のあるユーザーなど、ユーザーアカウント間の興味深い関係を見つける方法を知りたいです。

以下に、私が使用する 2 つのテーブルを示します。1 つはすべてのユーザーを保持し、もう 1 つはフォローしているユーザーのキーを保持します。

User
{
    id,
    name
}

Follows {
    user_id -> user.id,
    following_id -> user.id
}

どのタイプのアルゴリズムを探していますか?

重要でない人のフォロワーがほとんどまたはまったくいないと仮定すると、どうすればグラフの中心にいる人を見つけることができますか? 重要な人がフォローしているので、彼らは重要だと思います。

David と Steve が指摘しているように、特定のノードがどれだけ近いか、どのノードがサブコミュニティを形成しているか、どのユーザーが最も接続されているかなどはすべて、このスキーマから引き出すことができる有用なデータの例です。

この「フォロワー」設計は現在多くのサイトで使用されているため、さまざまな人々に役立つ可能性のある堅牢な SQL またはプログラミング言語の実装を取得することを期待して、報奨金を開始しました。

一部のアルゴリズムの結果は魅力的ですが、他のアルゴリズム (関連するノードの検索など) は、サイトのユーザーに推奨できるため、サイトのユーザーにとって価値があることに注意してください。

score 10 · Accepted Answer

リンクだけに集中する場合は、次の一般的な中心性測定を試してください (G がグラフであると仮定します)。

次数: ノードiの次数はki /( N -1)として定義されます。ここで、 kiはノードiへのリンクの数、Nはノードの総数です。高次は重要を意味します。
近さ: ノードiの近さは ( N -1)/(Σ_( j ∈G) dij )として定義されます。ここで、dijはノードiとノードjの間の距離です。これは、ノードからソーシャルネットワーク内の他のすべてのノードまでの距離を強調します。
媒介性: (Σ_( j < k ∈G) njk(i) / njk ) / (( N -1)( N -2)) として定義される媒介性。ここで、njkはノードjとkの間の最短経路の数を表し、njk(i)は、ノードiを通過するこれらのパスの数です。ノードiの媒介性が高いということは、ノードiが、ノードiを通過する必要がある他の 2 つのノード間に多くの接続があることを意味します。

上記の指標は、リンク情報だけで簡単に計算できます。これらの中心性指標の 1 つまたは複数を組み合わせて、ソーシャルネットワーク内の重要なノードを見つけることができます。とにかく、「重要」の定義によると、他のさまざまな対策が必要になる場合があります。

1 に答える 1