Label propagation是基于标傳播的一種社群劃分算法。Label Propagation Algorithm簡稱LPA算法，也可以是說是一種劃分小團體的算法。這種社群劃分的方法有很多，LPA隻是一種最簡單的一種。比如，以微網誌為例，使用者在微網誌上可以關注感興趣的人，同樣也會被其他人關注，這樣使用者和使用者之間就存在了關系，使用LPA就可以對使用者進行聚類操作，相同興趣點的使用者可以聚類在一起，劃分一起之後就可以統一進行推薦了，這樣就可以用LPA。
社群劃分
社群結構指的就是在網絡中由一些節點構成的特定分組，在同一個分組内的節點通過節點，之間的連接配接邊緊密的連接配接在一起，而在分組和分組之間，其連接配接比較松散，稱每一個分組就是一個社群。由上就可以知道社群是網絡中節點的集合，這些節點内部連接配接較為緊密而外部連接配接較為稀疏。
在一個社群網絡中每一個使用者其實就是一個節點，使用者之間通過互相關注關系構成了使用者之間的社交關系，使用者之間通過轉發感興趣的東西，進而就構成了使用者之間的興趣關系。通過将不同使用者劃分到不同的社群，使得每一個社群是都有不同的屬性，比如興趣，領域等等。而在兩個興趣之間的關系相對來說就比較弱一些的就被分成了兩個社群，這兩個社群之間的相對連接配接會較為稀疏。比如：
黑圈裡面的相對連接配接比較稠密，是以可以作為一個社群。可以看到整個網絡被分成了3個圈，各個社群之間的聯系就比較稠密。
社群劃分算法
假設在一個網絡裡面，每一個樣本隻能是屬于一個社群的，那麼這樣的問題就稱為非重疊社群劃分。在非重疊社群劃分算法裡面，有很多的方法：①基于子產品度優化的社群劃分。②基于譜分析的社群劃分算法。③基于資訊論的社群劃分算法。④基于标簽傳播的社群劃分算法。比較經典的應該算是基于子產品度優化的社群劃分算法了，其基本思想是将社群劃分問題轉換成了子產品度函數的優化，而子產品度是對社群劃分算法結果的一個很重要的衡量标準。在實際求解的過程中是不能直接求解的，是以通常是采用近似解法，根據求解方法不同可以分為以下幾種方法：①凝聚方法，通過不斷合并不同社群，實作對整個網絡的社群劃分，典型的方法有Newman快速算法，CNM算法和MSG-MV算法。②分裂方法，通過不斷的删除網絡的邊來實作對整個網絡的社群劃分，典型的方法有GN算法。③直接近似求解子產品度函數，通過優化算法直接對子產品度函數進行求解，典型的方法有EO算法。
社群劃分的評價标準
按照不同的劃分算法，社群劃分的結果可能會存在很多種，是以每一種社群劃分的品質都是不一樣的，為了可以度量社群劃分的品質，于是便使用了子產品度的衡量标準。子產品度是在
區間上的一個實數，通過比較每一個社群内部的連接配接密度和社群與社群直接的連接配接密度，去度量社群劃分的品質。若将連接配接比較稠密的點劃分在一個社群中，這樣子產品度的值就會變大。最後子產品度最大的一種劃分方法就是最優的劃分方法。
Label Propagation Algorithm
LPA是一種基于标簽傳播的局部社群劃分。對于網絡中的每一個節點，在初始階段，Label Propagation算法對于每一個節點都會初始化一個唯一的一個标簽。每一次疊代都會根據與自己相連的節點所屬的标簽改變自己的标簽，更改的原則是選擇與其相連的節點中所屬标簽最多的社群标簽為自己的社群标簽，這就是标簽傳播的含義了。随着社群标簽不斷傳播。最終，連接配接緊密的節點将有共同的标簽。
LPA算法的最大的優點就是算法的邏輯非常簡單，相對于優化子產品度算法的過程是非常快的。LPA算法利用自身的網絡的結構指導标簽傳播，這個過程是無需任何的任何的優化函數，而且算法初始化之前是不需要知道社群的個數的，随着算法疊代最後可以自己知道最終由多少個社群。
假設對于一個節點
，其相鄰節點為
，對于每一個節點，都有其對應的标簽，标簽代表的是該節點所屬的社群。在算法疊代的過程中，節點
根據其鄰居節點更新所屬的社群。比如：
一開始c選擇了a，因為大家的社群标簽都是一樣的，是以随機選擇了一個，d也根據自己周圍的鄰居節點來确定标簽數，最多的是a，是以就是d為a了，以此類推，最後就全部都是a了。
标簽傳播
和上訴的更新過程是類似的，标簽傳播也分兩種傳播方式，同步更新，異步更新。
同步更新：對于節點
，在第t代時，根據其是以節點在第t-1代的标簽進行更新。也就是
其中
表示的就是節點
在第t代時的社群标簽。函數
表示的就是取參數節點中社群标簽最多的。但是問題來了，這種同步更新的方法會存在一個問題，會出現标簽震蕩。
雖然結果影響不是非常大，但是對于這種不斷的震蕩終歸是不好的。而且很難停止，因為停止的條件就是當社群标簽不再變化的時候終止。
異步更新：對于異步更新方式
這個算法就不會出現剛剛的标簽震蕩的情況了。
對于他們之間的權重關系，其實就是他們之間的重要程度，也就是使用者之間通信的頻繁程度，比如密友和陌生人之間權重肯定不一樣，還有他們之間的互動程度也不一樣。是以如果沒有給定權重，那就隻能強算了。
使用高斯距離來得到權重。之後就是權重相加，看看哪一個權重大了。
算法疊代終止條件
當網絡中的每一個節點所屬的社群不再改變的時候疊代就可以停止了，對于每一個節點，在其所有的鄰居節點所屬目前社群中，其所屬的社群标簽是最大的，即：如果用
來表示社群标簽，
表示節點i所有鄰居節點中社群标簽為
的個數，則算法終止條件為：對于每一個節點
，如果節點i的社群标簽為
，則：
這樣就可以獲得最終的社群。但是社群不是唯一的。
代碼實作
前面兩個是連接配接的點，最後一個是權重。
def loadData(filePath):
f = open(filePath)
vector_dict = {}
edge_dict = {}
for line in f.readlines():
lines = line.strip().split(" ")
for i in range(2):
if lines[i] not in vector_dict:
vector_dict[lines[i]] = int(lines[i])
edge_list = []
if len(lines) == 3:
edge_list.append(lines[1 - i] + ":" + lines[2])
else:
edge_list.append(lines[1 - i] + ":" + "1")
edge_dict[lines[i]] = edge_list
else:
edge_list = edge_dict[lines[i]]
if len(lines) == 3:
edge_list.append(lines[1 - i] + ":" + lines[2])
else:
edge_list.append(lines[1 - i] + ":" + "1")
edge_dict[lines[i]] = edge_list
return vector_dict, edge_dict
一開始标簽都是唯一的，第二條是邊。
def get_max_community_label(vector_dict, adjacency_node_list):
label_dict = {}
for node in adjacency_node_list:
node_id_weight = node.strip().split(":")
node_id = node_id_weight[0]
node_weight = int(node_id_weight[1])
if vector_dict[node_id] not in label_dict:
label_dict[vector_dict[node_id]] = node_weight
else:
label_dict[vector_dict[node_id]] += node_weight
sort_list = sorted(label_dict.items(), key=lambda d: d[1], reverse=True)
return sort_list[0][0]
得到鄰居節點最多的社群标簽數。
def get_max_community_label(vector_dict, adjacency_node_list):
label_dict = {}
for node in adjacency_node_list:
node_id_weight = node.strip().split(":")
node_id = node_id_weight[0]
node_weight = int(node_id_weight[1])
if vector_dict[node_id] not in label_dict:
label_dict[vector_dict[node_id]] = node_weight
else:
label_dict[vector_dict[node_id]] += node_weight
sort_list = sorted(label_dict.items(), key=lambda d: d[1], reverse=True)
return sort_list[0][0]
檢查是否到結束條件了。
def check(vector_dict, edge_dict):
for node in vector_dict.keys():
adjacency_node_list = edge_dict[node]
node_label = vector_dict[node]
label = get_max_community_label(vector_dict, adjacency_node_list)
if node_label >= label:
continue
else:
return 0
return 1
主函數。
def label_propagation(vector_dict, edge_dict):
t = 0
print('First Label: ')
while True:
if (check(vector_dict, edge_dict) == 0):
t = t + 1
print('iteration: ', t)
for node in vector_dict.keys():
adjacency_node_list = edge_dict[node]
vector_dict[node] = get_max_community_label(vector_dict, adjacency_node_list)
else:
break
return vector_dict
最後效果：
附上GitHub代碼： https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/Label%20Propagation