日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Label?Propagation算法原理示例解析_python

作者：zhiyong_will ? 更新時間： 2023-03-29 編程語言

1. 概述

對于社區，沒有一個明確的定義，有很多對社區的定義，如社區是指在一個網絡中，有一組節點，它們彼此都相似，而組內的節點與網絡中的其他節點則不相似。更為一般的可以表述為：社區是指網絡中節點的集合，這些節點內部連接較為緊密而外部連接較為稀疏。

基于上述的形象的表示，出現了很多的社區劃分算法，如Fast Unfolding算法[1]，Fast Unfolding算法是基于模塊度的算法，模塊度相當于對上述社區的形象描述的一種抽象表示，成為優化的主要目標。但是模塊度的計算相對較為復雜，這也成為限制基于模塊度算法在大規模圖數據上的應用。

Label Propagation算法[2]是一種基于標簽傳播的局部社區劃分算法，相比較而言其簡單的計算過程，能夠在大規模的圖數據上應用。

2. Label Propagation算法

2.1. Label Propagation算法概述

Label Propagation算法是一種基于標簽傳播的局部社區劃分算法。對于網絡中的每一個節點，在初始階段，Label Propagation算法對每一個節點一個唯一的標簽，在每一個迭代的過程中，每一個節點根據與其相連的節點所屬的標簽改變自己的標簽，更改的原則是選擇與其相連的節點中所屬標簽最多的社區標簽為自己的社區標簽，這便是標簽傳播的含義。隨著社區標簽的不斷傳播，最終緊密連接的節點將有共同的標簽。

Label Propagation算法最大的優點是其算法過程比較簡單，想比較于優化模塊度的過程，算法速度非?？臁abel Propagation算法利用網絡的結構指導標簽的傳播過程，在這個過程中無需優化任何函數。在算法開始前我們不必要知道社區的個數，隨著算法的迭代，在最終的過程中，算法將自己決定社區的個數。

2.2. Label Propagation算法原理

對于Label Propagation算法，假設對于節點x，其鄰居節點為x1,x2,?,xk，對于每一個節點，都有其對應的標簽，標簽代表的是該節點所屬的社區。在算法迭代的過程中，節點x根據其鄰居節點更新其所屬的社區。更新的規則是選擇節點x的鄰居節點中，所屬社區最多的節點對應的社區為其新的社區。

上述便是Label Propagation算法的核心概念。在初始節點，令每一個節點都屬于唯一的社區，當社區的標簽在節點間傳播的過程中，緊密相連的節點迅速地取得一致的標簽。具體過程如下圖所示：

這樣的過程不斷地持續下去，直到所有可能聚集到一起的節點都具有了相同的社區標簽。在傳播過程的最終，具有相同社區標簽的節點被劃到相同的社區中稱為一個個獨立的社區。

在標簽傳播的過程中，節點的標簽的更新過程可以分為兩種，即：

  • 同步更新
  • 異步更新

同步更新是指對于節點xxx，在第ttt代時，根據其所有鄰居節點在第t?1代時的社區標簽對其標簽進行更新。即：

在上圖中，兩邊的標簽會在社區標簽aaa和社區標簽bbb不停地震蕩。

這樣的停止條件可以使得最終能夠獲得強壯的社區(Strong Community)，但是社區并不是唯一的。對于Strong Community，其要求對于每一個節點，在其社區內部的鄰居節點嚴格大于社區外部的鄰居節點，然而Label Propagation算法能夠保證對于每一個節點，在其所屬的社區內有足夠多的鄰居節點。

3.3. Label Propagation算法過程

3. 實驗

3.1. 數據描述

實驗過程中使用的數據為參考[1]中使用的數據，其結構如下所示：

其在Fast Unfolding算法的劃分結果為：

  • 社區1：節點0，1，2，3，4，5，6，7
  • 社區2：節點8，9，10，11，12，13，14，15

3.2. 實驗代碼

#####################################
# Author:zhaozhiyong
# Date:20151205
# Fun:Label Propagation
# Fix:已經用Python3重新修改
#####################################
import random
def loadData(filePath):
    f = open(filePath)
    vector_dict = {}
    edge_dict = {}
    for line in f.readlines():
        lines = line.strip().split("\t")
        for i in range(2):
            if lines[i] not in vector_dict:
                #put the vector into the vector_dict
                vector_dict[lines[i]] = int(lines[i])
                #put the edges into the edge_dict
                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 = {}
    # generate the 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
    # find the max label
    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_check = {}
        for ad_node in adjacency_node_list:
            node_id_weight = ad_node.strip().split(":")
            node_id = node_id_weight[0]
            if vector_dict[node_id] not in label_check:
                label_check[vector_dict[node_id]] = 1
            else:
                label_check[vector_dict[node_id]] += 1
        sort_list = sorted(label_check.items(), key = lambda d: d[1], reverse=True)
        if node_label == sort_list[0][0]:
            continue
        else:
            return 0
    return 1    
def label_propagation(vector_dict, edge_dict):
    #initial, let every vector belongs to a community
    t = 0
    #for every node in a random order
    while True:
        if (check(vector_dict, edge_dict) == 0):
            t = t+1
            print("----------------------------------------")
            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)
            print(vector_dict)
        else:
            break
    return vector_dict
if __name__ == "__main__":
    vector_dict, edge_dict=loadData("./cd_data.txt")
    dict_key_list = list(vector_dict.keys())
    random.shuffle(dict_key_list)
    new_vector_dict = {}
    for key in dict_key_list:
        new_vector_dict[key] = vector_dict.get(key)
    print("original community: ", new_vector_dict)
    vec_new = label_propagation(new_vector_dict, edge_dict)
    print("---------------------------------------------------------")
    print("the final result: ")
    community_dict = {}
    for key in vec_new.keys():
        if vec_new[key] not in community_dict:
            community_dict[vec_new[key]] = []
        community_dict[vec_new[key]].append(str(key))
    for key in community_dict.keys():
        print("community-" + str(key) + " ---> " + str(community_dict[key]))

3.3. 代碼解析

上述的實驗代碼中主要包括4個部分其一為loadData()函數，其目的是從文件中讀入數據，取得點的信息，邊的信息；

第二個是label_propagation()函數，其目的是Label Propagation算法的整個迭代過程，期中會調用兩個函數，即get_max_community_label()函數和check()函數，get_max_community_label()函數的目的是在對每個節點遍歷其鄰居節點的過程中，選擇出最大的社區標簽，check()函數的目的是判斷算法是否迭代結束。

4. 實驗結果

參考文獻

[1] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of statistical mechanics: theory and experiment, 2008, 2008(10): P10008.

[2] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical review E, 2007, 76(3): 036106.

原文鏈接：https://juejin.cn/post/7194661027307323451

欄目分類
最近更新