10 億人のユーザーがいるソーシャル ネットワークがあるとします。各ユーザーのページで、そのユーザーの友達、友達の友達などの数を 5 度まで表示する必要があります。友情は互角です。カウントはすぐに更新する必要はありませんが、正確である必要があります。
グラフを読みましたが、この問題に対するスケーラブルなアプローチを示唆するものは見つかりませんでした。私が考えることができるものはどれも、あまりにも多くの時間、あまりにも多くのスペース、またはその両方を必要とする. これは私を夢中にさせています！
1463 次
2 に答える
4
興味深いアプローチの 1 つは、フレンド グラフを隣接行列に変換し、その行列を 5 乗することです。これにより、各ノード間の長さ 5 のパスの数を含む隣接行列が得られます。
最初の数レベルでは友人の隣接行列が疎になる可能性が高いため、疎行列を利用できる行列乗算アルゴリズムが必要になることに注意してください。幸運なことに、巨大な行列 (特にスパース行列) を効率的に乗算する方法について多くの研究が行われています。
これは、Twitter の Oscar Boykin が、 Twitter でフォロワーのフォロワーを計算するためのこのアプローチについて言及しているビデオです。
于 2013-08-14T01:46:12.947 に答える