Label Propagation

2018-09-25 本文已影响1人冒绿光的盒子

Label propagation是基于标传播的一种社区划分算法。Label Propagation Algorithm简称LPA算法，也可以是说是一种划分小团体的算法。这种社区划分的方法有很多，LPA只是一种最简单的一种。比如，以微博为例，用户在微博上可以关注感兴趣的人，同样也会被其他人关注，这样用户和用户之间就存在了关系，使用LPA就可以对用户进行聚类操作，相同兴趣点的用户可以聚类在一起，划分一起之后就可以统一进行推荐了，这样就可以用LPA。

社区划分

社区结构指的就是在网络中由一些节点构成的特定分组，在同一个分组内的节点通过节点，之间的连接边紧密的连接在一起，而在分组和分组之间，其连接比较松散，称每一个分组就是一个社区。由上就可以知道社区是网络中节点的集合，这些节点内部连接较为紧密而外部连接较为稀疏。

在一个社区网络中每一个用户其实就是一个节点，用户之间通过互相关注关系构成了用户之间的社交关系，用户之间通过转发感兴趣的东西，从而就构成了用户之间的兴趣关系。通过将不同用户划分到不同的社区，使得每一个社区是都有不同的属性，比如兴趣，领域等等。而在两个兴趣之间的关系相对来说就比较弱一些的就被分成了两个社区，这两个社区之间的相对连接会较为稀疏。比如：

黑圈里面的相对连接比较稠密，所以可以作为一个社区。可以看到整个网络被分成了3个圈，各个社区之间的联系就比较稠密。

社区划分算法

假设在一个网络里面，每一个样本只能是属于一个社区的，那么这样的问题就称为非重叠社区划分。在非重叠社区划分算法里面，有很多的方法：①基于模块度优化的社区划分。②基于谱分析的社区划分算法。③基于信息论的社区划分算法。④基于标签传播的社区划分算法。比较经典的应该算是基于模块度优化的社区划分算法了，其基本思想是将社区划分问题转换成了模块度函数的优化，而模块度是对社区划分算法结果的一个很重要的衡量标准。在实际求解的过程中是不能直接求解的，所以通常是采用近似解法，根据求解方法不同可以分为以下几种方法：①凝聚方法，通过不断合并不同社区，实现对整个网络的社区划分，典型的方法有Newman快速算法，CNM算法和MSG-MV算法。②分裂方法，通过不断的删除网络的边来实现对整个网络的社区划分，典型的方法有GN算法。③直接近似求解模块度函数，通过优化算法直接对模块度函数进行求解，典型的方法有EO算法。

社区划分的评价标准

按照不同的划分算法，社区划分的结果可能会存在很多种，所以每一种社区划分的质量都是不一样的，为了可以度量社区划分的质量，于是便使用了模块度的衡量标准。模块度是在 $[-1,1]$ 区间上的一个实数，通过比较每一个社区内部的连接密度和社区与社区直接的连接密度，去度量社区划分的质量。若将连接比较稠密的点划分在一个社区中，这样模块度的值就会变大。最后模块度最大的一种划分方法就是最优的划分方法。

Label Propagation Algorithm

LPA是一种基于标签传播的局部社区划分。对于网络中的每一个节点，在初始阶段，Label Propagation算法对于每一个节点都会初始化一个唯一的一个标签。每一次迭代都会根据与自己相连的节点所属的标签改变自己的标签，更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签，这就是标签传播的含义了。随着社区标签不断传播。最终，连接紧密的节点将有共同的标签。
LPA算法的最大的优点就是算法的逻辑非常简单，相对于优化模块度算法的过程是非常快的。LPA算法利用自身的网络的结构指导标签传播，这个过程是无需任何的任何的优化函数，而且算法初始化之前是不需要知道社区的个数的，随着算法迭代最后可以自己知道最终由多少个社区。
假设对于一个节点 $x$ ，其相邻节点为 $x_1,x_2,x_3...x_k$ ，对于每一个节点，都有其对应的标签，标签代表的是该节点所属的社区。在算法迭代的过程中，节点 $x$ 根据其邻居节点更新所属的社区。比如：

一开始c选择了a，因为大家的社区标签都是一样的，所以随机选择了一个，d也根据自己周围的邻居节点来确定标签数，最多的是a，所以就是d为a了，以此类推，最后就全部都是a了。

标签传播

和上诉的更新过程是类似的，标签传播也分两种传播方式，同步更新，异步更新。
同步更新：对于节点 $x$ ，在第t代时，根据其所以节点在第t-1代的标签进行更新。也就是 $C_x(t) = f(C_{x_1}(t-1),C_{x_2}(t-1),C_{x_3}(t-1),...,C_{x_k}(t-1))$ 其中 $C_{x}(t)$ 表示的就是节点 $x$ 在第t代时的社区标签。函数 $f$ 表示的就是取参数节点中社区标签最多的。但是问题来了，这种同步更新的方法会存在一个问题，会出现标签震荡。

虽然结果影响不是非常大，但是对于这种不断的震荡终归是不好的。而且很难停止，因为停止的条件就是当社区标签不再变化的时候终止。
异步更新：对于异步更新方式 $C_x(t) = f(C_{x_1}(t),C_{x_2}(t),C_{x_3}(t),...,C_{x_k}(t))$ 这个算法就不会出现刚刚的标签震荡的情况了。
对于他们之间的权重关系，其实就是他们之间的重要程度，也就是用户之间通信的频繁程度，比如密友和陌生人之间权重肯定不一样，还有他们之间的互动程度也不一样。所以如果没有给定权重，那就只能强算了。

前面两个是连接的点，最后一个是权重。

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