約 10K の頂点と 100K のエッジを含むJUNG グラフがあり、頂点のペア間の類似度を測定したいと考えています。頂点は概念 (例: 犬、家など) を表し、リンクは概念間の関係 (例: related、is_a、is_part_of など) を表します。
頂点は密に相互リンクされているため、最短パス アプローチは良い結果をもたらしません (最短パスは常に非常に短いです)。
頂点間の接続性をランク付けするには、どのようなアプローチをお勧めしますか?
JUNG には頂点の重要度をスコアリングするためのアルゴリズムがいくつかありますが、2 つの頂点間に類似性の尺度があるかどうかはわかりません。 SimPackも有望なようです。
ヒントはありますか？
スコアは、頂点のペアの類似性を測定するのcentralityではなく、一般的なネットワークの単一ノードのある種の (方法に応じて) 中心性を測定します。したがって、このアプローチはおそらくあなたが望むものではありません。
SimPack確かに素晴らしい目標が設定されていますが、グラフの場合は同形ベースの比較を実装します。これは、1 つのグラフのノードのペアではなく、複数のグラフの類似性を比較します。したがって、これは今のところ対象外です。
あなたが求めているのはgraph clustering、グラフ（ネットワーク）を複数のパーティションに分割して、各パーティションのノードが他のノードよりも強く相互接続される、いわゆる方法（ネットワークモジュール決定またはネットワークコミュニティ決定方法とも呼ばれます）です。その他のパーティション。
最も古典的な方法は、類似度の計算にデンドログラムを利用できる Newman & Girvan の媒介中心性クラスタリングであり、JUNGにあります。もちろん、今日ではたくさんの方法があります。ModuLand メソッドを(恥知らずにプラグインして) 試すか、電子補足資料の最後にあるモジュール検出アルゴリズムの詳細な表をお読みください。これはoverlapping graph clusteringメソッドファミリーです。つまり、各ノードの結果は、ネットワークのそれぞれのクラスターに属する強さを含むベクトルです。ペアごとのノードの類似性は、これらのノードからクラスターへのベクトルのペアから簡単に導き出すことができます。
グラフのクラスタリングは自明ではなく、非常に正確なドメイン固有の結果を得るために任意の方法を適応させる必要がある可能性がありますが、それは読者次第です;) 頑張ってください!