什麼聚類算法可以考慮圖？

Question

假設我有一個無向加權連通圖。我想將具有最高邊緣值的頂點組合在一起（頂點度數）。使用聚類算法是一種方法。我可以考慮哪些聚類算法來完成這項任務？我希望這是清楚的;任何澄清問題，請詢問。謝謝。

Answer 1

主要有兩種方法 - 給你的圖作爲輸入到現有的工具，或使用你對這個圖（以及其領域），以創建一個代表，然後在將其應用於機器學習方法的專業知識。

我會用第二種方法啓動：

如果只有節點和邊（每個節點沒有進一步的數據），你首先需要考慮每個節點\邊的表示。我將解釋有關節點，但它應該在邊緣情況下應該類似。

的最簡單的方法就是將表示每個節點n作爲連接向量：

每個節點將被表示爲n=(Ia(n),Ib(n),Ic(n),Id(n),Ie(n))，其中Ii(n)=1萬一節點n是的「朋友」（鄰居）節點i，否則爲0。 （例如a=(0,1,1,0,1)）

注意，您可以決定一個節點是其自身的朋友。

第二種方法，這是相當類似於第一個，是使用邊緣的權重向量：

n=(W(a,n),W(b,n),W(c,n),W(d,n),W(e,n))，其中W(i,n)是邊緣(i,n)的重量。

有一些更多的方法來表示節點，但這是不夠的，以在其上運行一些計算。

後，你有這樣的表現，你就可以開始在其應用一些聚類算法。

kmeans是完成這個任務，並考慮sklearn has a great implementation很大。它有一些參數可以（也應該）配置（即距離度量）。

kmeans的乘積是k不同的不相交節點組。

如果您想將圖表傳遞給算法並獲得一些度量，則可以應用更多高級算法。 community detection用於在圖表中查找社區。再次，在networkx包中有一個很好的python implementation。