java - ユンググラフ、使えますか？

Question

無向で加重された RageRank アルゴリズムを使用しようとしていますが、JUNG で UndirectedSparseGraph.java および UndirectedSparseMultigraph.java クラスを見つけました。どちらも変更を必要とせずに目的を果たしているようですが、どちらを選択すればよいかわかりません。だから私の質問は

1: それらの違いは何ですか? どちらを使用すればよいですか?

2: 私の実験データには数百万の「ページ」が含まれています。大規模なデータ セットでの JUNG のメモリ/速度パフォーマンスはどのくらいですか?

ありがとう、

Answer 1

USGraph は、指定された 2 つの頂点間のエッジを 1 つだけ許可します。USMultigraph は、2 つの頂点間に複数の平行なエッジを許可します。要件に合ったものを使用してください。

PageRank はパスごとに O(E) 時間を必要とします。通常、収束に達するまでに数十回の反復しか必要ありません。メモリは、どのグラフ実装を選択するか、および保存するその他の関連データによって大きく左右されます。