在圖表中獲取次最近鄰居的最佳方式是什麼？

我需要某種計算，其值由下面的inneficient僞Python代碼給出：在圖表中獲取次最近鄰居的最佳方式是什麼？

def foo(a,b): 
    tmp = 0 
    for i in graph.nodes(): 
     for j in graph.nodes(): 
      tmp += c 
      if (i and j are neighbors): 
       tmp += a - c 
      elif (i and j are next-neighbors): 
       tmp += b - c 
    return tmp

換言之，給出的所有的節點對，FOO = A *（E =邊的數量）+ B *（EE =不是鄰居但具有共同鄰居的對的數量）+ c *（N（N-1）/ 2 -EE-E）。

我試着想在某種廣度上先搜索，但我不能。

編輯：更多信息

圖不是靜態的。我經常添加和刪除邊緣，所以我不能只計算一次。我必須不斷更新「下一個鄰居列表」。
我將圖存儲爲一個鄰接矩陣。

來源

2011-07-12 Rafael S. Calsaverini

圖表如何存儲？ – Patrick

鄰接矩陣。 –

頂點數是否不變？ – Szabolcs

這是一個粗略的想法。但首先，一些假設：1.無向圖2.恆定頂點數

您的圖形不斷變化。所以你需要保持鄰居（邊緣）和第二鄰居的數量得到有效更新。第一個是微不足道的，所以我們來看看第二個鄰居。

Per @ Patrick的建議，讓我們使用A^2，讓我們看看如何有效地更新它，而不必每次重新從頭開始重新計算它。 A^2_ij是從i到j的長度 - 兩條路徑的數量，請記住它也會有對角條目，因爲從頂點到它自身總是有一條長度爲兩條的路徑。如果您有A^2，則可以很容易地計算次鄰居的數量，因此讓我們在圖表更改時保持A^2在內存中的更新。

如何更新A^2有效：

當您添加/刪除邊緣，你這是隻有兩個條目的矩陣B改變A。假設我們正在添加（而不是刪除）邊緣。然後(A+B)^2 = A^2 + AB + BA + B^2。

假設加入的邊緣是(i,j)。

B^2很簡單：(B^2)_ii = (B^2)_jj = 1，其餘爲0。
AB = transpose(BA)所以我們只需要計算兩個中的一個，說BA。結果是BA的行i是A的行j和BA的行j是行i的A，其餘爲零。所以再次，計算速度很快。

刪除邊緣將類似。

你只需要計數的第二鄰居，所以不是計數A^2在每個步驟中有多少非零非對角線元素，有一些額外的工作，你可以通過非數量多少算當您添加AB + BA時，A^2中的零條目更改。

編輯

這整個事情在不同的語言解釋：

讓我們跟蹤任意兩個頂點之間的長度，兩條路徑的數量在矩陣M。當我們添加（刪除）i和j之間的邊沿時，長度爲2的路徑的數量將在i與所有鄰居j以及j和所有鄰居i之間增加（減少）一個，因此M很容易更新在每次更改圖後的O(n)時間。

來源

2011-07-13 09:36:06 Szabolcs

太棒了！這正是我所需要的，謝謝。每次更改O（1）查找圖的O（N）更新!!!完美。 –

如果存儲在Adjacency MatrixA上圖可以發現所有長度由矩陣本身（A^2）乘2路，如果這是你在問什麼。

這將花費O（n^3）時間進行預處理，但是您可以在同一時間內執行對鄰居和「下一個鄰居」的查找。

來源

2011-07-12 15:44:04 Patrick

問題是我的圖形不是靜態的。我不斷添加和刪除邊緣。 –

請注意，一個節點也有一個長度爲*本身的路徑（'1 - > 2 - > 1'），所以如果使用方矩陣來計算下一個鄰居，則需要對此進行更正。 – Szabolcs

「長度*兩*的路徑」，我的意思是。錯字。 – Szabolcs

獲取節點的鄰居列表（node_main）。拜訪每個鄰居。將它的每個鄰居添加到鄰居鄰居列表，除非它是node_main的鄰居之一（或者是node_main本身）。我錯過了什麼嗎？

來源

2011-07-12 15:51:30

我的圖是一個鄰接矩陣。這將是O（N^2）。我想也許有一個O（N.log（N））的方式來做到這一點。如果我這樣做，我相信會兩次訪問每一對鄰居，並且每一對鄰居都會超過兩次。 –

原諒我，我的圖論是大約10歲。獲取當前鄰居列表並訪問每個列表（一次）似乎很簡單，就像在任何廣度優先搜索中一樣。從那裏你只是檢查節點鄰居是否在你的鄰居列表中，其中包括你正在計算的原始節點。您也可以訪問每個鄰居並將其所有鄰居添加到列表中。使結果列表唯一併刪除主節點及其直接鄰居，你有你的列表。性能由連通性決定，其中完全連通的圖是最壞的情況，仍然是O（N^2），對嗎？ –

但是，如果我使用鄰接矩陣，我必須總是檢查所有節點以確定鄰居列表，因此得到鄰居總是O（N），並且鄰居的鄰居總是O（N^2），無論圖的連通性。我猜我被O（N^2）卡住了。 :( –

在圖表中獲取次最近鄰居的最佳方式是什麼？

回答

相關問題