人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

    标签传播(Label Propagation)算法详解

    < 上一篇:DBSCAN聚类算法 下一篇:没有了 >
    近年来随着社交网络的发展,先后出现了以 Facebook、Twitter 为代表的社交网站,国内的社交网站如新浪微博等。人们可以在这些社交网站上进行交流,分享各自的想法,社交网络的发展对信息的传播起到了推波助澜的作用。

    以微博为例,用户在微博上,可以关注感兴趣的人,同样也会被其他人关注,可以发表各自的观点,也可以转发其他人的博文,在这些数据的背后,不仅存在用户之间的社交关系,还存在着用户之间的兴趣关系。为了能够对社交网站上的用户进行聚类,可以使用社区划分的算法对用户进行聚类。

    标签传播算法(Label Propagation)算法是基于标签传播的社区划分算法,在基于标签传播的社区划分算法中,将网络中的边看作是个体之间的信息传播,其传播的结果通常使得社团内部节点之间共享相同的信息。

    社区划分

    社区以及社区划分

    随着对各种网络结构的研究,人们发现在各类网络中存在社区结构,社区结构指的是在网络中,由一些节点构成特定的分组,在同一个分组内的节点通过节点,之间的连接边紧密地连接在一起,而在分组与分组之间,其连接比较松散,称每一个分组为一个社区。

    由上可知社区是网络中节点的集合,这些节点内部连接较为紧密而外部连接较为稀疏。

    在社交网络中,每一个用户相当于一个节点,用户之间通过互相的关注关系构成了用户之间的社交关系,用户之间通过转发感兴趣的微博,构成了用户之间的兴趣关系。

    通过将用户划分到不同的社区中,每一个社区具有一些不同的属性以区分其他社区,如兴趣,在该社区内部的节点之间有较为紧密的连接,而在任意两个社区之间,由于两个社区之间的属性不一样,如一个社区的兴趣为电影,另一个社区的兴趣为体育,这两个社区之间的相对连接则较为稀疏。具有两个社区的社区结构如图 1 所示。

    社区结构
    图 1 社区结构

    在图 1 中,节点之间通过边的连接构成了整个网络,整个网络被划分成了两个部分,分别为社区 A 和社区 B,其中,社区 A 或者社区 B 的内部连接较为紧密,而在社区 A 和社区 B 之间的连接则较为稀疏。

    社区划分的算法

    假设在网络中,每一个样本点只能属于一个社区,这样的问题称为非重叠社区划分。在非重叠社区划分中,典型的方法主要有基于模块度优化的社区划分算法,基于谱分析的社区划分算法,基于信息论的社区划分算法和基于标签传播的社区划分算法。

    在基于模块度优化的社区划分算法中,其基本思想是将社区划分问题转化为对模块度函数的优化,其中,模块度是度量社区划分质量的重要标准。在实际的求解过程中,由于模块度函数不能直接求解,通常采用近似的方式对其进行求解,根据求解方法的不同,主要分为如下的几种方法:
    • 凝聚方法:通过不断合并不同社区,实现对整个网络的社区划分,典型的方法有 Newman 快速算法、CNM 算法和 MSG-MV 算法;
    • 分裂方法:通过不断删除网络中边来实现对整个网络的社区划分,典型的方法有 Newman 提出的 GN 算法;
    • 直接近似求解模块度函数:通过优化算法直接对模块度函数进行求解,典型的方法有 EO 算法。

    社区划分的评价标准

    社区划分是将网络划分成多个不同的社区,在每一个社区的内部,其连接比较紧密,在社区与社区之间的连接较为稀疏。根据这样形式化的定义,社区划分的结果会有很多种,为了能够度量社区划分的质量,Newman 等人提出了模块度的概念。

    模块度是一个在 [-1,1] 区间上的实数,其通过比较每一个社区内部的连接密度和社区与社区之间的连接密度,去度量社区划分的质量。若将连接比较稠密的点划分在一个社区中,这样模块度的值会变大,最终,模块度最大的划分是最优的社区划分。

    标签传播算法原理

    Label Propagation 算法是一种基于标签传播的局部社区划分算法。对于网络中的每一个节点,在初始阶段,Label Propagation 算法对每个节点初始化一个唯一的标签,在每次的迭代过程中,每个节点根据与其相连的节点所属的标签改变自己的标签,更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签,这便是标签传播的含义。随着社区标签不断传播,最终,连接紧密的节点将有共同的标签。

    Label Propagation 算法最大的优点是其算法逻辑比较简单,相比于优化模块度的过程,算法速度非常快。Label Propagation算法利用网络自身的结构指导标签的传播过程,在这个过程中无需优化任何函数。在算法开始前我们不必知道社区的个数,随着算法的迭代,在最终的过程中,算法将自己决定社区的个数。

    对于 Label Propagation 算法,假设对于节点 x,其邻居节点为 x1 ,x2 ,…,xk,对于每一个节点,都有其对应的标签,标签代表的是该节点所属的社区。在算法迭代的过程中,节点x根据其邻居节点更新其所属的社区。

    在初始阶段,令每一个节点都属于唯一的社区,当社区的标签在节点间传播时,紧密相连的节点迅速取得一致的标签。具体过程如图 2 所示。

    标签传播
    图 2 标签传播

    在图 2 中所示的标签传播的过程中,对于 c 节点,在选择了与 a 节点一致的标签后,与 d 节点相邻的节点中,属于 a 社区的节点最多,因此 c 节点的标签也被设置成 a,这样的过程不断持续下去,直到所有可能聚集到一起的节点都具有了相同的社区标签,此时,图 2 中的所有节点的标签都变成了 a。在传播过程的最终,具有相同社区标签的节点被划到相同的社区中成为一个个独立的社区。

    标签传播

    在标签传播的过程中,节点的标签是根据其邻接节点的标签进行更新的,如在图 2 中,与节点 c 相邻的节点分别为 a、b 和 d。节点的标签的更新过程可以分为两种,即同步更新和异步更新。

    同步更新是指对于节点 x,在第 t 代时,根据其所有邻居节点在第 t-1 代时的社区标签,对其标签进行更新。即:


    其中,Cx(t) 表示的是节点 x 在第 t 代时的社区标签。函数 f 表示的是取的参数节点中所有社区个数最大的社区。同步更新的方法存在一个问题,即对于一个二分或者近似二分的网络来说,这样的结构会导致标签的震荡,如图 3 所示。

    标签震荡
    图 3 标签震荡

    在图 3 中,在第一步的更新中,若左侧节点的标签更改为 a,右侧节点的标签更改为 b,在第二步中,左侧的节点又会更改为 b,右侧的节点又会更改为 a,如此往复,两边的标签会在社区标签 a 和 b 间不停地震荡。

    对于异步更新方式,其更新公式为:


    其中,邻居节点 xi1 ,…,xim 的社区标签在第t代已经更新过,则使用其最新的社区标签。而邻居节点 xi(m+1) ,…,xik 在第 t 代时还没有更新,则对于这些邻居节点还是用其在第(t-1)代时的社区标签。

    现在让我们一起使用 Python 构建 Label Propagation 算法的异步更新过程,实现的具体过程如下程序所示,对于节点的更新顺序可以顺序选择。
    def label_propagation(vector_dict, edge_dict):
        '''标签传播
        input:  vector_dict(dict)节点:社区
                edge_dict(dict)存储节点之间的边和权重
        output: vector_dict(dict)节点:社区
        '''
        # 初始化,设置每个节点属于不同的社区
        t = 0
        # 以随机的次序处理每个节点
        while True:
            if (check(vector_dict, edge_dict) == 0):
                t = t + 1
                print "iteration: ", t
                # 对每一个node进行更新
                for node in vector_dict.keys():
                    adjacency_node_list = edge_dict[node] # 获取节点node的邻接节点
                    vector_dict[node] = get_max_community_label(vector_dict, adjacency_node_list)
                print vector_dict
            else:
                break
        return vector_dict
    函数 label_propagation 是整个 Label Propagation 算法的核心部分,其输入为节点以及其所属的社区 vector_dict 和节点之间的边的信息 edge_dict,其输出为最终计算出来的节点以及其所属的社区 vector_dict。

    在迭代的过程中,首先会判断是否需要迭代,对每一个节点进行更新。在对该节点计算的过程中,找到与其相连接的节点所属社区最多的社区作为其社区,函数 get_max_community_label 的具体实现代码如下所示:
    def get_max_community_label(vector_dict, adjacency_node_list):
        '''得到相邻接的节点中标签数最多的标签
        input:  vector_dict(dict)节点:社区
                adjacency_node_list(list)节点的邻接节点
        output: 节点所属的社区
        '''
        label_dict = {}
        for node in adjacency_node_list:
            node_id_weight = node.strip().split(":")
            node_id = node_id_weight[0]#邻接节点
            node_weight = string.atoi(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]
    此函数的输入为所有的节点及其所属社区 vector_dict 和节点 node 的邻接节 点 adjacency_node_list,输出为节点 node 所属的社区。

    通过统计其邻接节点中每一个节点所属的社区,再将社区按照出现的次数进行降序排列,最终返回出现次数最多的社区作为 node 节点的社区。

    迭代的终止条件

    在迭代过程中,当网络中的每个节点所属的社区不再改变时,此时迭代过程便可以停止。但是在 Label Propagation 算法中,当某个节点的邻居节点中存在两个或者多个最大的社区标签时,如图 4 所示。


    图 4 迭代的终止条件

    节点 a 与社区 A 和社区 B 都有连接,且与社区 A 的连接权重为 2,与社区 B 的连接权重也为 2。对于节点 a,其所属的社区是随机选取的,此时可以选择社区 A,也可以选择社区 B,因此对于节点 a,其所属的社区会一直改变,这样就不能满足如上的跌倒终止条件。

    为了避免如上情况,可对上述的迭代终止条件修改为:对于每一个节点,在其所有的邻居节点所属的社区中,其所属的社区标签是最大的,即如果用 C1,…,Cp 来表示社区标签,dicj 表示节点i的所有邻居节点中社区标签为 Cj 的个数,算法终止的条件为:对于每一个节点i,如果节点 i 的社区标签为 Cm,则:


     
    这样的停止条件可以使得最终能够获得强壮的社区,但是社区并不是唯一的。终止条件判断的具体实现的代码如下程序所示:
    def check(vector_dict, edge_dict):
        '''检查是否满足终止条件
        input:  vector_dict(dict)节点:社区
                edge_dict(dict)存储节点之间的边和权重
        output: 是否需要更新
        '''
        for node in vector_dict.keys():
            adjacency_node_list = edge_dict[node]  # 与节点node相连接的节点
            node_label = vector_dict[node]  # 节点node所属社区
            label = get_max_community_label(vector_dict, adjacency_node_list)
            if node_label == label: # 对每个节点,其所属的社区标签是最大的
                continue
            else:
                return 0
        return 1

    标签传播算法过程

    Label Propagation 算法的过程如下:
    • 对网络中的每个节点初始化其所属社区标签,且每个节点所属的社区是唯一的,如对于节点 x,初始化其社区标签为 Cx(0)=x;
    • 设置代数 t;
    • 对于每个节点 x∈X,其中X是所有节点的集合,令:

    • 判断是否可以迭代结束,如果否,则设置 t=t+1,重新遍历。
    < 上一篇:DBSCAN聚类算法 下一篇:没有了 >