java - Katz相似度-矩阵/图运算(JAVA + JUNG)

Question

我正在图表中测试一些相似性指标。我正在使用 JUNG API 来处理图表。我已经成功计算了基本指标，例如共同邻居和优先依恋。现在，我想计算 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，因此最终的 katz 矩阵可以通过以下方式轻松计算:B.A + (B.A)^2 + ... + (B.A)^4 其中 A 是图的邻接矩阵。问题是我正在处理的图表非常巨大，我无法将整个卡茨矩阵存储在内存中。此外，我不需要所有的分数，因为我只测试几对节点。不过，我无法找到一种有效的方法来计算个人分数，而不必在图表上执行步行。有什么想法吗？

Answer 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) n =1,2,3,4