Katz的相似度 - 矩陣/圖形操作（JAVA + JUNG）

Question

我正在測試圖中的一些相似性度量。我使用JUNG API來處理圖表。我已經設法計算基本度量標準，如普通鄰居和prefferential附件。現在我想計算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矩陣可以通過以下公式容易地計算出來：B .A +（B.A）^ 2 + ... +（B.A）^ 4其中A是圖的鄰接矩陣。問題是我正在使用的圖表非常龐大，我無法將整個katz矩陣存儲在內存中。此外，我不需要所有的分數，因爲我只測試幾對節點。 我無法找到一種有效的方法來計算個人分數，而無需在圖表上散步。 任何想法？

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