如何使用MATLAB對一個稀疏鄰接矩陣進行聚類

Question

我有一個40000 * 40000的稀疏連接矩陣，它代表我的圖形，並且我使用了歸一化切割算法來聚類此圖。聚類後​​，我得到每個節點的分區標記爲40000 * 1數組。

什麼是最好的方式來表示這個矩陣作爲一個聚類矩陣，其中每個（i，j）的值即聚類之間的連接將被表示。基本上，如果我有20個羣集，我需要一個20 * 20的矩陣，其中每個元素是羣集之間的連接總數。

Answer 1

從集羣查找連接數量a到集羣b應該是相當簡單：

cluster_connections(a,b) = nnz(connectivity_matrix(tags==a, tags==b)); 

下面是一個使用全矩陣僅用於可讀性的例子。稀疏矩陣的行爲方式相同。

>> connectivity_matrix = randi([0 1],10) 
connectivity_matrix = 

    1 1 0 0 0 1 1 0 1 1 
    0 0 1 0 1 1 1 1 0 1 
    0 1 0 1 1 1 0 0 0 1 
    0 1 0 0 1 1 1 1 1 1 
    1 1 0 0 0 1 1 0 0 1 
    1 0 0 0 0 1 0 1 1 1 
    1 1 0 1 0 0 0 1 0 1 
    0 0 1 0 1 0 0 1 0 1 
    1 0 0 0 0 1 0 1 1 1 
    1 1 0 0 1 0 0 0 0 1 

>> tags = [1 2 3 2 3 1 2 3 3 1] 
tags = 

    1 2 3 2 3 1 2 3 3 1 


>> connectivity_matrix(tags==2, tags==3) 
ans = 

    1 1 1 0 
    0 1 1 1 
    0 0 1 0 

>> cluster_connections = nnz(connectivity_matrix(tags==2, tags==3)) 
cluster_connections = 7