社群發現算法——标簽傳播算法LPA

轉自：http://blog.csdn.net/cleverlzc/article/details/39494957

另一個好的介紹 網址：http://blog.csdn.net/nwpuwyk/article/details/47426909

标簽傳播算法（LPA）的做法比較簡單：

第一步: 為所有節點指定一個唯一的标簽；

第二步: 逐輪重新整理所有節點的标簽，直到達到收斂要求為止。對于每一輪重新整理，節點标簽重新整理的規則如下:

對于某一個節點，考察其所有鄰居節點的标簽，并進行統計，将出現個數最多的那個标簽賦給目前節點。當個數最多的标簽不唯一時，随機選一個。

注：算法中的記号 N_n^k 表示節點 n 的鄰居中标簽為 k 的所有節點構成的集合。

SLPA 中引入了 Listener 和 Speaker 兩個比較形象的概念，你可以這麼來了解：在重新整理節點标簽的過程中，任意選取一個節點作為 listener，則其所有鄰居節點就是它的 speaker 了，speaker 通常不止一個，一大群 speaker 在七嘴八舌時，listener 到底該聽誰的呢？這時我們就需要制定一個規則。
    在 LPA 中，我們以出現次數最多的标簽來做決斷，其實這就是一種規則。隻不過在 SLPA 架構裡，規則的選取比較多罷了（可以由使用者指定）。
    當然，與 LPA 相比，SLPA 最大的特點在于：它會記錄每一個節點在重新整理疊代過程中的曆史标簽序列（例如疊代 T 次，則每個節點将儲存一個長度為 T 的序列，如上圖所示），當疊代停止後，對每一個節點曆史标簽序列中各（互異）标簽出現的頻率做統計，按照某一給定的閥值過濾掉那些出現頻率小的标簽，剩下的即為該節點的标簽（通常有多個）。
           

SLPA 後來被作者改名為 GANXiS，且軟體包仍在不斷更新中……