0

グラフでいくつかの類似性メトリックをテストしています。グラフを処理するためにJUNGAPIを使用しています。私は、一般的な隣人や優先的な愛着のような基本的なメトリックを計算することができました。ここで、次のようなkatzメトリックを計算します。katz（v1、v2）= B.paths_1（v1、v2）+ B ^ 2.paths_2（v1、v2）+ ... + B ^ n.paths_n（ v1、v2）ここで、paths_n（v1、v2）は、v1とv2の間の長さ「n」のパスの数です。Bはスカラーです。nを4に制限しているので、最終的なカッツ行列は次のように簡単に計算できます。BA +（BA）^ 2 + ... +（BA）^ 4ここで、Aはグラフの隣接行列です。問題は、私が使用しているグラフが非常に巨大であり、katz行列全体をメモリに格納できないことです。また、ノードのペアを数個しかテストしないため、すべてのスコアが必要になるわけではありません。私は出来ます' ただし、グラフ上をウォークすることなく、個々のスコアを計算する効率的な方法を見つけてください。何か案は？

4

1 に答える 1

1

個々のスコアを計算するketz(v1,v2)には、v1 または v2 から 4 未満の距離内にある頂点のみを含む隣接サブマトリックスを考慮する必要があります。

これらの頂点は、v1 と v2 の息優先検索を使用して見つけることができます。

ただし、v1 から BFS を実行しているときに #paths を直接カウントすると、実際にははるかにうまくいく可能性があります。v1 からの距離を記憶し、各頂点で v2 に到達したかどうかを確認するだけで済みます。その場合は、適切なカウンターをインクリメントします。

そのようなもの（疑似コード）：

Queue q = new Queue();
q.enqueue((v1, 0));
int[] counts = new int[] { 0,0,0,0,0 };

while (!q.empty()) {
    (v, dist) = q.dequeue();
    for(Vertex w : v.Neighbors()) {
        if(dist < 3)
            q.enqueue((w, dist+1));

        if(dist < 4 && w == v2)
            counts[dist+1]++;
    }
}

したがって、これを実行すると、counts[n] = paths_n(v1,v2)for n =1,2,3,4 になります

于 2011-10-12T04:17:57.967 に答える