0

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

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

于 2011-10-12T04:17:57.967 回答