Community Detection

本文結(jié)構(gòu)安排

  • 圖聚類簡(jiǎn)介

  • 正則化割

  • Louvain

  • 非負(fù)矩陣分解（NMF）

  • 其他常見方法

  • 圖(graph):是一種由點(diǎn)和邊集構(gòu)成的結(jié)構(gòu)G=(V,E)

  • 圖聚類(graph clustering) : 將點(diǎn)劃分為不同的簇，使得簇內(nèi)的邊盡量多，簇之間的邊盡量少。也稱為圖劃分(partitioning)，社區(qū)檢查(community detection)

應(yīng)用Louvain算法產(chǎn)生的社區(qū)檢測(cè)圖示

community.png

Normalized cut

正則化割的基本原理是使各簇之間的割最小，但不是算其最小割，因?yàn)檫@會(huì)使相對(duì)孤立的邊緣點(diǎn)“自成一團(tuán)”，造成社區(qū)大小的不均衡。算法的基本過程的前半部分類似于譜聚類，先由度矩陣和鄰接矩陣，計(jì)算出拉普拉斯矩陣，得到第二小到K+1小的特征向量，對(duì)其進(jìn)行K-means聚類，預(yù)處理得到k’個(gè)簇。之后，計(jì)算兩兩簇合并之后，計(jì)算其正則化割，選擇正則化割最小的兩個(gè)簇合并。每次合并減小一個(gè)簇，直到減小到K個(gè)簇。

k-路劃分：

（1）計(jì)算相似度矩陣W和度矩陣D

（2）計(jì)算標(biāo)準(zhǔn)化拉普拉斯矩陣D^{-\frac{1}{2}}(D?W)D^{-\frac{1}{2}}

（3）從第二小的特征值開始找k’個(gè)最小的特征值對(duì)應(yīng)的特征向量構(gòu)造n \cdot k′維度的特征矩陣F

（4）對(duì)特征矩陣F按行進(jìn)行標(biāo)準(zhǔn)化后，進(jìn)行Kmeans聚類得到k’簇

（5）在這k’個(gè)簇中，每次選取兩個(gè)簇進(jìn)行合并，直到最后剩下k個(gè)簇，選取的策略是最小化Ncut時(shí)的合并組合

Ncut.png

Louvain

Louvain算法的基本原理也是采用合并的策略，但是它合并的標(biāo)準(zhǔn)是模塊度增益。首先將每個(gè)節(jié)點(diǎn)初始化為不同社區(qū)，計(jì)算將節(jié)點(diǎn)加入其鄰居社區(qū)的模塊度增益△Q，選擇使模塊度增益最大的鄰居進(jìn)行合并，合并后的社區(qū)看做一個(gè)新的節(jié)點(diǎn)，直到兩兩社區(qū)合并的模塊度增益都不大于0，則停止合并。

deltaQ.png

Louvain算法步驟如下：

（1）初始化每個(gè)數(shù)據(jù)點(diǎn)為一個(gè)社區(qū)；

（2）對(duì)每個(gè)數(shù)據(jù)點(diǎn)，嘗試加入其鄰居所在的社區(qū)，計(jì)算比較加入前后的模塊度增益ΔQ，選出增益最大的那個(gè)鄰居社區(qū)，若其對(duì)應(yīng)的增益ΔQ>0，則該數(shù)據(jù)點(diǎn)加入這個(gè)社區(qū)，否則不改變其原來社區(qū)劃分；

（3）將得到的社區(qū)視為一個(gè)節(jié)點(diǎn)，社區(qū)內(nèi)節(jié)點(diǎn)之間邊權(quán)重轉(zhuǎn)化為新節(jié)點(diǎn)環(huán)的權(quán)重，社區(qū)間的邊權(quán)重轉(zhuǎn)化為新節(jié)點(diǎn)間的邊權(quán)重；

（4）重復(fù)（2）（3）步驟，直至滿足收斂條件。

收斂條件可以是迭代了一定的次數(shù)，亦或是模塊度不再增加。

NMF

nmf_pic.png

NMF的基本原理是將原始矩陣分解得到社區(qū)指示矩陣和基矩陣，隨機(jī)初始化這兩個(gè)矩陣的元素，迭代更新這兩個(gè)矩陣，更新規(guī)則如下：

最小化目標(biāo)函數(shù)：

||A-UV^{T}||_{F}^{2}

NMF.png

停止條件是目標(biāo)函數(shù)收斂，即上一個(gè)計(jì)算的目標(biāo)函數(shù)值，與本次目標(biāo)函數(shù)值的差小于一個(gè)設(shè)定的閾值。

而對(duì)于目標(biāo)函數(shù)收斂后得到的U，我們可以根據(jù)其每行（對(duì)應(yīng)每個(gè)數(shù)據(jù)點(diǎn)）的最大值對(duì)應(yīng)的列數(shù)，得到該數(shù)據(jù)點(diǎn)對(duì)應(yīng)的類標(biāo)（即將它分配給這個(gè)社區(qū)），故而可以得到如下NMF算法的算法步驟：

（1）初始化U、V矩陣（非負(fù)）

（2）根據(jù)U、V的更新公式異步迭代更新

（3）滿足終止條件后終止更新U、V

（4）找到U中每個(gè)數(shù)據(jù)點(diǎn)最大值對(duì)應(yīng)的列數(shù)，分配其作為類標(biāo)

LPA

標(biāo)簽傳播算法（LPA）的做法比較簡(jiǎn)單：

第一步: 為所有節(jié)點(diǎn)指定一個(gè)唯一的標(biāo)簽；

第二步: 逐輪刷新所有節(jié)點(diǎn)的標(biāo)簽，直到達(dá)到收斂要求為止。對(duì)于每一輪刷新，節(jié)點(diǎn)標(biāo)簽刷新的規(guī)則如下:

對(duì)于某一個(gè)節(jié)點(diǎn)，考察其所有鄰居節(jié)點(diǎn)的標(biāo)簽，并進(jìn)行統(tǒng)計(jì)，將出現(xiàn)個(gè)數(shù)最多的那個(gè)標(biāo)簽賦給當(dāng)前節(jié)點(diǎn)。當(dāng)個(gè)數(shù)最多的標(biāo)簽不唯一時(shí)，隨機(jī)選一個(gè)。

KeyCode

Normalized cut
構(gòu)建相似度矩陣W和計(jì)算度矩陣D；由于有每個(gè)節(jié)點(diǎn)的特征向量feature vector，故而節(jié)點(diǎn)之間的相似性可以通過對(duì)應(yīng)特征向量的余弦距離度量出來,由于數(shù)據(jù)集是.mat文件，所以我使用matlab生成相似度矩陣和高斯距離矩陣后再作為Java Code的輸入。

 = zeros(length(A),length(A));
for i = 1:length(A)
   for j = 1:i-1
       W(i,j) = 1-pdist2(F(i,:),F(j,:),'cosine');
       W(j,i) = W(i,j);
   end
end

public void calculateW(){
    this.W=DenseMatrix.Factory.zeros(nsamples, nsamples);
    for (int p=0;p<nsamples;p++){
        for (int q=0;q<nsamples;q++){
            this.W.getAsDouble(CosineSimilarity(p,q));
        }
    }
}

計(jì)算標(biāo)準(zhǔn)化拉普拉斯矩陣，由度矩陣D和相似度矩陣W可得拉普拉斯矩陣L再D^{-\frac{1}{2}}LD^{-\frac{1}{2}}進(jìn)行標(biāo)準(zhǔn)化

Matrix I = DenseMatrix.Factory.eye(this.nsamples,this.nsamples);
Matrix D = DenseMatrix.Factory.eye(this.nsamples,this.nsamples);
for (int i=0;i<this.nsamples;i++){
    Double wij = 0.0;
    for (int j=0;j<this.nsamples;j++)
    {
        wij+=this.W.getAsDouble(i,j);
    }
    D.setAsDouble(wij,i,i);
}
this.L = D.minus(this.W);

構(gòu)建特征矩陣；計(jì)算標(biāo)準(zhǔn)化拉普拉斯矩陣的特征值和特征向量，從第二小的特征值開始選取k′個(gè)最小的特征值對(duì)應(yīng)的特征向量組成特征矩陣：

Matrix[] eigenValueDecompostion = this.L.eig();
Matrix eigenVector = eigenValueDecompostion[0];
Matrix eigenValue = eigenValueDecompostion[1];
List<Matrix> res = eigenVector.getColumnList();
List<Matrix> NCutResult=new ArrayList<>();
for (int i=1;i<this.k+1;i++){
    NCutResult.add(res.get(i));
}

對(duì)特征矩陣進(jìn)行聚類,不斷選取兩個(gè)簇合并直至剩下k個(gè)簇，選取哪兩個(gè)簇進(jìn)行合并取決于 此時(shí)哪兩個(gè)簇合并得到的Ncut值最小.

KMeans NCutkMeans = new KMeans(this.k,NCut);
NCutkMeans.clustering();

Louvain

初始化每個(gè)數(shù)據(jù)點(diǎn)為一個(gè)社區(qū)：

initSingletonClusters(); 

public void initSingletonClusters()
{
    int i;
    clustercount = nodecount;
    cluster = new int[nodecount];
    for (i= 0; i < nodecount; i++)
        cluster[i] = i;
}

對(duì)每個(gè)數(shù)據(jù)點(diǎn)，嘗試加入其鄰居所在的社區(qū)，計(jì)算比較加入前后的模塊度增益ΔQ，記錄最大的模塊度增益max和它對(duì)應(yīng)的社區(qū)max_cluster，若最大增益max>0，則將該數(shù)據(jù)點(diǎn)加入對(duì)應(yīng)的社區(qū)max_cluster：特別地，這里的數(shù)據(jù)點(diǎn)既指單個(gè)節(jié)點(diǎn)，也指一個(gè)社區(qū)，故統(tǒng)一按社區(qū)視為數(shù)據(jù)點(diǎn)來處理，只是單個(gè)數(shù)據(jù)點(diǎn)算只有一個(gè)節(jié)點(diǎn)的社區(qū)。

public void communityDetection(){
    boolean update=true;
    Set<Integer> cur_set = new TreeSet<>();
    for (int i=0;i<diGraph.getV();i++){
        cur_set.add(diGraph.adjList.get(i).getCluserlabel());
    }
    String current = "";
    String last_set = "";

    for (int i=0;i<diGraph.getV();i++){
        current+=String.valueOf(diGraph.adjList.get(i).getCluserlabel());
    }

    while (update){
        for (Integer i:cur_set){
            double bestdeltaQ=Double.NEGATIVE_INFINITY;
            int bestcluster = i;//initial
            for (Integer j:cur_set){
                if (i!=j){
                    Set<Integer> c1 = diGraph.getClusterList(i);//Cluster C1 vertex_id_set
                    Set<Integer> c2 = diGraph.getClusterList(j);//Cluster C2 vertex_id_set
                    if (c1.size()!=0 && c2.size()!=0) {
                        double deltaQ = calculateDeltaQ(c1, c2, i, j);//calculate DeltaQ
                        if (deltaQ > bestdeltaQ) {
                            bestdeltaQ = deltaQ;
                            bestcluster = j;
                        }
                    }
                }
            }
            if (bestdeltaQ > 0){
                diGraph.adjList.get(i).setCluserlabel(bestcluster);//change clusterlabel
            }
            else {
                diGraph.adjList.get(i).setCluserlabel(i);//keep clusterlabel
            }


            diGraph.clearVisited();//clear all
        }

        last_set = current;//judge algorithm converge or not
        cur_set.clear();
        current="";
        for (int i=0;i<this.diGraph.getV();i++){
            cur_set.add(this.diGraph.adjList.get(i).getCluserlabel());
        }
        for (int i=0;i<diGraph.getV();i++){
            current+=String.valueOf(diGraph.adjList.get(i).getCluserlabel());
        }

        if (current.equals(last_set)){
            update = false;
        }
    }
    String filePath = "D:\\DataMining\\lab2\\"+this.name+"_Louvain.csv";
    FileReaderFunc.writeListToFile(filePath,CommunityLabel);
}

計(jì)算模塊度增益的函數(shù)

deltaQ.png
public double calculateDeltaQ(Set<Integer> c1,Set<Integer> c2,int startlabel,int endlabel) {

    double m=((double) diGraph.getE());
    
    double k_i_in = diGraph.getClusterWeightIn(c1,c2,startlabel,endlabel);
    double sigma_in = diGraph.getIn(c2);
    double total = diGraph.getClusterWeightTotal(endlabel);
    double k_i = diGraph.getClusterWeightTotal(startlabel);
    double tmp1 = (sigma_in+k_i_in)/(2.0*m);
    double tmp2 = (total+k_i)/(2.0*m);
    double tmp3 = sigma_in/(2.0*m);
    double tmp4 = total/(2.0*m);
    double tmp5 = k_i/(2.0*m);
    double deltaQ=tmp1-tmp2*tmp2-tmp3+tmp4*tmp4+tmp5*tmp5;

    return deltaQ;
}

NMF
根據(jù)迭代更新公式寫代碼：

NMF.png

public void communityDetection() {
    Matrix fenzi = DenseMatrix.Factory.zeros(this.N,this.K);
    Matrix fenmu = DenseMatrix.Factory.zeros(this.N,this.K);
    Matrix DU = DenseMatrix.Factory.zeros(this.N,this.K);
    Matrix DV = DenseMatrix.Factory.zeros(this.N,this.K);

    Matrix Tmp = this.U.mtimes(this.V.transpose());
    Matrix E = this.A.minus(Tmp);
    double cur_error = E.norm2();
    double last_error = 0.0;
    for (int it = 0; it < this.maxiterator ; it++){
        fenzi = this.A.mtimes(this.V);
        fenmu = this.U.mtimes(this.V.transpose());
        fenmu = fenmu.mtimes(this.V);

        DU = fenzi.divide(fenmu);
        this.U = this.U.times(DU);


        fenzi = this.A.transpose().mtimes(this.U);
        fenmu = this.V.mtimes(this.U.transpose());
        fenmu = fenmu.mtimes(this.U);

        fenmu = fenmu.plus(this.lambda);
        DV = fenzi.divide(fenmu);
        this.V = this.V.times(DV);

        last_error=cur_error;
        Matrix Tmp1 = this.U.mtimes(this.V.transpose());
        Matrix E1 = this.A.minus(Tmp1);
        cur_error = E1.norm2();
        if (Math.abs(cur_error-last_error)<0.00001){
            break;
        }
    }
}

Experiments on Datasets

說明：相似度矩陣使用屬性矩陣構(gòu)造的余弦相似度
cos_{X,Y} = \frac{\sum_{i=1}^{n}(x_{i} * y_{i})}{\sqrt{\sum_{i=1}^{n}x_{i}^{2}} * \sqrt{\sum_{i=1}^{n}y_{i}^{2}}}

高斯距離矩陣使用全連接度量模式下的高斯核函數(shù)

w_{ij} = e ^{-\frac{cosine}{2\sigma^{2}}}

image1.png
image2.png
image3.png
image4.png

Algorithm Comparison and Hyperparameter

Normalized cut

所謂Clustering，就是說聚類，把一堆東西（合理地）分成兩份或者K份。從數(shù)學(xué)上來說，
聚類的問題就相當(dāng)于Graph Partition的問題，即給定一個(gè)圖G = (V, E)，如何把它的頂點(diǎn)集劃分為不相交的子集，
使得這種劃分最好。譜聚類算法的主要優(yōu)點(diǎn)有：譜聚類只需要數(shù)據(jù)之間的相似度矩陣，因此對(duì)于處理稀疏數(shù)據(jù)的聚類很有效。這點(diǎn)傳統(tǒng)聚類算法比如K-Means很難做到。由于使用了降維，因此在處理高維數(shù)據(jù)聚類時(shí)的復(fù)雜度比傳統(tǒng)聚類算法好。譜聚類算法的主要缺點(diǎn)有：如果最終聚類的維度非常高，則由于降維的幅度不夠，譜聚類的運(yùn)行速度和最后的聚類效果均不好。聚類效果依賴于相似矩陣，不同的相似矩陣得到的最終聚類效果可能很不同。

Louvain

Louvain算法是一種基于多層次優(yōu)化Modularity的算法，它的優(yōu)點(diǎn)是快速、準(zhǔn)確，是性能最好的社區(qū)發(fā)現(xiàn)算法之一。Modularity函數(shù)最初被用于衡量社區(qū)發(fā)現(xiàn)算法結(jié)果的質(zhì)量，它能夠刻畫發(fā)現(xiàn)的社區(qū)的緊密程度。那么既然能刻畫社區(qū)的緊密程度，也就能夠被用來當(dāng)作一個(gè)優(yōu)化函數(shù)，即將結(jié)點(diǎn)加入它的某個(gè)鄰居所在的社區(qū)中，如果能夠提升當(dāng)前社區(qū)結(jié)構(gòu)的modularity。Louvain不斷地遍歷網(wǎng)絡(luò)中的結(jié)點(diǎn)，嘗試將單個(gè)結(jié)點(diǎn)加入能夠使modularity提升最大的社區(qū)中，直到所有結(jié)點(diǎn)都不再變化，并且將一個(gè)個(gè)小的社區(qū)歸并為一個(gè)超結(jié)點(diǎn)來重新構(gòu)造網(wǎng)絡(luò)，這時(shí)邊的權(quán)重為兩個(gè)結(jié)點(diǎn)內(nèi)所有原始結(jié)點(diǎn)的邊權(quán)重之和。一直迭代直至算法穩(wěn)定。Louvain可以利用modularity的特性，決定是否進(jìn)行合并，相比于譜聚類——無論是否合理都進(jìn)行分割，Louvain的使用更加靈活，算法進(jìn)行時(shí)不需要設(shè)置具體的社區(qū)個(gè)數(shù)，社區(qū)的個(gè)數(shù)由社區(qū)自己的性質(zhì)決定。但是也可以在合并的過程中加入終止條件或者是別的約束，以滿足固定的社區(qū)個(gè)數(shù)。

NMF

NMF（非負(fù)矩陣分解）對(duì)原始矩陣的重構(gòu)誤差最小化，且原始數(shù)據(jù)的統(tǒng)計(jì)信息也可以得到保持。NMF在處理聚類問題上有以下幾個(gè)方面的優(yōu)勢(shì)：

  1. 非負(fù)性，由于NMF中分解得到的簇劃分子矩陣具有非負(fù)性，只需要找到數(shù)據(jù)在哪個(gè)簇中的值最大就可以確定該數(shù)據(jù)的簇標(biāo)簽。非負(fù)矩陣分解的非負(fù)約束性使其能夠清晰的指出數(shù)據(jù)點(diǎn)的簇標(biāo)簽。
  2. 易構(gòu)性，根據(jù)不同的數(shù)據(jù)和目標(biāo)，可以構(gòu)造與之匹配的非負(fù)矩陣分解方法。只需要根據(jù)原始數(shù)據(jù)構(gòu)造出原始矩陣，接著只需要加入具體的約束即可開始訓(xùn)練。
  3. 易于優(yōu)化，因?yàn)榉秦?fù)矩陣分解的方法目標(biāo)公式類似，所有優(yōu)化的方式比較容易套用。

劣勢(shì)：由于非負(fù)矩陣分解處理輸入和輸出全是矩陣形式的，當(dāng)數(shù)據(jù)量過大時(shí)，很容易出現(xiàn)內(nèi)存消耗過大甚至超出運(yùn)行內(nèi)存報(bào)錯(cuò)的情況，可以往這幾個(gè)方面解決。采取縮減方案——多層圖劃分，采取劃分方案——主成分分析或k均值預(yù)聚類，遞增方案——隨機(jī)優(yōu)化非負(fù)矩陣分解方法，采取分布式并行實(shí)施方案。

LPA

標(biāo)簽傳播算法是不重疊社區(qū)發(fā)現(xiàn)的經(jīng)典算法，其基本思想是：將一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的標(biāo)簽中數(shù)量最多的標(biāo)簽作為該節(jié)點(diǎn)自身的標(biāo)簽。給每個(gè)節(jié)點(diǎn)添加標(biāo)簽（label）以代表它所屬的社區(qū)，并通過標(biāo)簽的“傳播”形成同一標(biāo)簽的“社區(qū)”結(jié)構(gòu)。給每個(gè)節(jié)點(diǎn)添加標(biāo)簽（label）以代表它所屬的社區(qū)，并通過標(biāo)簽的“傳播”形成同一標(biāo)簽的“社區(qū)”結(jié)構(gòu)。一個(gè)節(jié)點(diǎn)的標(biāo)簽取決于它鄰居節(jié)點(diǎn)的標(biāo)簽：假設(shè)節(jié)點(diǎn)z的鄰居節(jié)點(diǎn)有z1至zk，那么哪個(gè)社區(qū)包含z的鄰居節(jié)點(diǎn)最多z就屬于那個(gè)社區(qū)（或者說z的鄰居中包含哪個(gè)社區(qū)的標(biāo)簽最多，z就屬于哪個(gè)社區(qū)）。優(yōu)點(diǎn)是收斂周期短，無需任何先驗(yàn)參數(shù)(不需事先指定社區(qū)個(gè)數(shù)和大小)，算法執(zhí)行過程中不需要計(jì)算任何社區(qū)指標(biāo)。

時(shí)間復(fù)雜度接近線性：對(duì)頂點(diǎn)分配標(biāo)簽的復(fù)雜度為O(n)，每次迭代時(shí)間為O(m)，找出所有社區(qū)的復(fù)雜度為O(n+m)，但迭代次數(shù)難以估計(jì)。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 越發(fā)的覺得做銷售是我的長(zhǎng)處，在挖掘客戶，找合適的房子，跟客戶像朋友一樣聊天，找他（她）的需求點(diǎn)，忘我的想幫助...
    徐麗紅閱讀 240評(píng)論 0贊 1
  • 今天聽到最多的爆炸性的消息就是出游。 今天是朋友從大連回來了，而我明日也要回趟家鄉(xiāng)，去參加表妹的婚禮。另外，同專業(yè)...
    beyound20閱讀 183評(píng)論 2贊 0
  • 1.使用逗號(hào)運(yùn)算符可以在一條語句中執(zhí)行多個(gè)操作 可用于聲明多個(gè)變量： 逗號(hào)運(yùn)算符總會(huì)返回表達(dá)式中的最后一項(xiàng) 常用于...
    寒o_0閱讀 693評(píng)論 0贊 0
  • 是選擇在北上廣，被擠得像沙丁魚，還是選擇在老家躺在當(dāng)死咸魚？每個(gè)人有每個(gè)人的價(jià)值觀。雖然，多多少少也會(huì)被外界影響。...
    逗號(hào)君閱讀 317評(píng)論 0贊 2

友情鏈接更多精彩內(nèi)容