在非重叠社区划分算法里面，有很多的方法：

1. 基于模块度优化的社区划分

基本思想是将社区划分问题转换成了模块度函数的优化，而模块度是对社区划分算法结果的一个很重要的衡量标准。

模块度函数在实际求解中无法直接计算得到全局最优解析解（类似深度神经网络对应的复杂高维非线性函数），所以通常是采用近似解法，根据求解方法不同可以分为以下几种方法：

. 凝聚方法(down to top): 通过不断合并不同社区，实现对整个网络的社区划分，典型的方法有Newman快速算法，CNM算法和MSG-MV算法；

. 分裂方法(top to down): 通过不断的删除网络的边来实现对整个网络的社区划分，典型的方法有GN算法；

. 直接近似求解模块度函数(近似等价解): 通过优化算法直接对模块度函数进行求解，典型的方法有EO算法；

2. 基于谱分析的社区划分算法
3. 基于信息论的社区划分算法
4. 基于标签传播的社区划分算法

undone

https://www.cnblogs.com/LittleHann/p/9078909.html

0x1：LPA基本思想

. 首先: Kmeans是基于欧式空间计算节点向量间的距离的，而LPA则是根据节点间的“共有关系”以及“共有关系的强弱程度”来度量度量节点间的距离；

. 第二点: Kmeasn中节点处在欧式空间中，它假设所有节点之间都存在“一定的关系”，不同的距离体现了关系的强弱。但是 LPA 中节点间只有满足“某种共有关系”时，才存在节点间的边，没有共有关系的节点是完全隔断的，计算邻居节点的时候也不会计算整个图结构，而是仅仅计算和该节点有边连接的节点，从这个角度看，LPA 的这个图结构具有更强的社区型；

0x2：LPA算法优点

0x3：LPA算法缺点

划分结果不稳定，随机性强是这个算法致命的缺点。具体体现在：

. 更新顺序：节点标签更新顺序随机，但是很明显，越重要的节点越早更新会加速收敛过程；

. 随机选择：如果一个节点的出现次数最大的邻居标签不止一个时，随机选择一个标签作为自己标签。这种随机性可能会带来一个雪崩效应，即刚开始一个小小的聚类错误会不断被放大。不过话也说话来，如果相似邻居节点出现多个，可能是weight计算的逻辑有问题，需要回过头去优化weight抽象和计算逻辑；

0x4：LPA的一个简单例子

算法初始化：a、b、c、d各自为独立的社区；

第一轮标签传播：

一开始c选择了a，因为大家的社区标签都是一样的，所以随机选择了一个；

d也根据自己周围的邻居节点来确定标签数，最多的是a，所以就是d为a了；

继续标签传播：以此类推，最后就全部都是a了；

Relevant Link:

https://www.jianshu.com/p/cff65d7595f9

https://arxiv.org/pdf/0709.2938.pdf

https://blog.csdn.net/Katherine_hsr/article/details/82343647

http://sighingnow.github.io/%E7%A4%BE%E4%BC%9A%E7%BD%91%E7%BB%9C/community_detection_k_means_clustering.html

2. LPA算法过程

0x1：算法过程描述

第一步：先给每个节点分配对应标签，即节点1对应标签1，节点i对应标签i； 
第二步：遍历N个节点（for i=1：N），找到对应节点邻居，获取此节点邻居标签，找到出现次数最大标签，若出现次数最多标签不止一个，则随机选择一个标签替换成此节点标签；
第三步：若本轮标签重标记后，节点标签不再变化（或者达到设定的最大迭代次数），则迭代停止，否则重复第二步

0x2：边权重计算

社区图结构中边的权重代表了这两个节点之间的的“关系强弱”，这个关系的定义取决于具体的场景，例如：

. 两个DNS域名共享的client ip数量；

. 两个微博ID的共同好友数量；

0x3：标签传播方式

LPA标签传播分为两种传播方式，同步更新，异步更新。

1. 同步更新

同步的意思是实时，即时的意思，每个节点label更新后立即生效，其他节点在统计最近邻社区的时候，永远取的是当前图结构中的最新值。

对于节点，在第 t 轮迭代时，根据其所在节点在第t-1代的标签进行更新。也就是

，其中表示的就是节点在第 t 次迭代时的社区标签。

函数表示的就是取参数节点中社区标签最多的。

需要注意的是，这种同步更新的方法会存在一个问题，当遇到二分图的时候，会出现标签震荡，如下图：

这种情况和深度学习中SGD在优化到全局最优点附近时会围绕最优点附近进行布朗运动（震荡）的原理类似。解决的方法就是设置最大迭代次数，提前停止迭代。

2. 异步更新

异步更新方式可以理解为取了一个当前社区的快照信息，基于上一轮迭代的快照信息来进行本轮的标签更新。

import matplotlib.pyplot as plt

import pandas as pd

import numpy as np

import string

def loadData(filePath):

    f = open(filePath)

    vector_dict = {}

    edge_dict = {}

    for line in f.readlines():

        lines = line.strip().split("   ")

        for i in range():

            if lines[i] not in vector_dict:

                vector_dict[lines[i]] = int(lines[i])

                edge_list = []

                if len(lines) == :

                    edge_list.append(lines[ - i] + ":" + lines[])

                else:

                    edge_list.append(lines[ - i] + ":" + "")

                edge_dict[lines[i]] = edge_list

            else:

                edge_list = edge_dict[lines[i]]

                if len(lines) == :

                    edge_list.append(lines[ - i] + ":" + lines[])

                else:

                    edge_list.append(lines[ - i] + ":" + "")

                edge_dict[lines[i]] = edge_list

    return vector_dict, edge_dict

if __name__ == '__main__':

    filePath = './label_data.txt'

    vector, edge = loadData(filePath)

    print(vector)

    print(edge)

# -*- coding: utf- -*-

import matplotlib.pyplot as plt

import pandas as pd

import numpy as np

import string

def loadData(filePath):

    f = open(filePath)

    vector_dict = {}

    edge_dict = {}

    for line in f.readlines():

        lines = line.strip().split("   ")

        for i in range():

            if lines[i] not in vector_dict:

                vector_dict[lines[i]] = int(lines[i])

                edge_list = []

                if len(lines) == :

                    edge_list.append(lines[ - i] + ":" + lines[])

                else:

                    edge_list.append(lines[ - i] + ":" + "")

                edge_dict[lines[i]] = edge_list

            else:

                edge_list = edge_dict[lines[i]]

                if len(lines) == :

                    edge_list.append(lines[ - i] + ":" + lines[])

                else:

                    edge_list.append(lines[ - i] + ":" + "")

                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[]

        node_weight = int(node_id_weight[])

        # 按照label为group维度，统计每个label的weight累加和

        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[], reverse=True)

    return sort_list[][]

def check(vector_dict, edge_dict):

    for node in vector_dict.keys():

        adjacency_node_list = edge_dict[node]   # 获取该节点的邻居节点

        node_label = vector_dict[node]          # 获取该节点当前label

        label = get_max_community_label(vector_dict, adjacency_node_list)   # 从邻居节点列表中选择weight累加和最大的label

        if node_label >= label:

            continue

        else:

            return     #  找到weight权重累加和更大的label

    return 

def label_propagation(vector_dict, edge_dict):

    t =

    print('First Label: ')

    while True:

        if (check(vector_dict, edge_dict) == ):

            t = t +

            print('iteration: ', t)

            # 每轮迭代都更新一遍所有节点的社区label

            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

if __name__ == '__main__':

    filePath = './label_data.txt'

    vector, edge = loadData(filePath)

    print "load and initial the community...."

    #print(vector)

    #print(edge)

    print "start lpa clustering...."

    vector_dict = label_propagation(vector, edge)

    print "ending lpa clustering...."

    print "the finnal cluster result...."

    print(vector_dict)

    cluster_group = dict()

    for node in vector_dict.keys():

        cluster_id = vector_dict[node]

        print "cluster_id, node", cluster_id, node

        if cluster_id not in cluster_group.keys():

            cluster_group[cluster_id] = [node]

        else:

            cluster_group[cluster_id].append(node)

    print cluster_group

{: ['', '', ''], : ['', '', '', '', ''], : ['', '', ''], : ['', '', '', '', '']}

https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/Label%20Propagation

https://www.jianshu.com/p/cff65d7595f9

https://www.cnblogs.com/bethansy/p/6953625.html

https://blog.csdn.net/zzz24512653/article/details/26151669