简单易学的机器学习算法——Label Propagation

一、社区划分的概述

对于社区,没有一个明确的定义,有很多对社区的定义,如社区是指在一个网络中,有一组节点,它们彼此都相似,而组内的节点与网络中的其他节点则不相似。更为一般的可以表述为:社区是指网络中节点的集合,这些节点内部连接较为紧密而外部连接较为稀疏。

基于上述的形象的表示,出现了很多的社区划分算法,如前面介绍的Fast Unfolding算法,Fast Unfolding算法是基于模块度的算法,模块度相当于对上述社区的形象描述的一种抽象表示,成为优化的主要目标。

二、Label Propagation算法

1、Label Propagation算法概述

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

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

2、Label Propagation算法原理

这样的过程不断地持续下去,直到所有可能聚集到一起的节点都具有了相同的社区标签。在传播过程的最终,具有相同社区标签的节点被划到相同的社区中称为一个个独立的社区。

在标签传播的过程中,节点的标签的更新过程可以分为两种,即:

  • 同步更新
  • 异步更新

3、Label Propagation算法过程

三、实验

1、数据描述

实验过程中使用的数据为:社团划分——Fast Unfolding算法中使用的数据,其结构如下所示:

其在Fast Unfolding算法的划分结果为:

  • 社区1:节点0,1,2,3,4,5,6,7
  • 社区2:节点8,9,10,11,12,13,14,15

2、实验代码

#####################################
# Author:zhaozhiyong
# Date:20151205
# Fun:Label Propagation
#####################################
import string

def loadData(filePath):
    f = open(filePath)
    vector_dict = {}
    edge_dict = {}
    for line in f.readlines():
        lines = line.strip().split("\t")

        for i in xrange(2):
            if lines[i] not in vector_dict:
                #put the vector into the vector_dict
                vector_dict[lines[i]] = string.atoi(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 = 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

    # 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")
    print "original community: ", vector_dict
    vec_new = label_propagation(vector_dict, edge_dict)
    print "---------------------------------------------------------"
    print "the final result: "
    for key in vec_new.keys():
        print str(key) + " ---> " + str(vec_new[key])

3、代码解析

上述的实验代码中主要包括444个部分,其一为loadData()函数,其目的是从文件中读入数据,取得点的信息,边的信息;第二个是label_propagation()函数,其目的是Label Propagation算法的整个迭代过程,期中会调用两个函数,即get_max_community_label()函数和check()函数,get_max_community_label()函数的目的是在对每个节点遍历其邻居节点的过程中,选择出最大的社区标签,check()函数的目的是判断算法是否迭代结束。

4、实验结果

若需要PDF版本,请关注我的新浪博客@赵_志_勇,私信你的邮箱地址给我。

参考文献

[1] U. N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76 (2007) 036106.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据派THU

教你用Keras和CNN建立模型识别神奇宝贝!(附代码)

在今天博客的最后,你将会了解如何在你自己的数据库中建立、训练并评估一个卷积神经网络。

73910
来自专栏AI研习社

Github 项目推荐 | Facebook 密集人体姿态估计工具 DensePose

DensePose-RCNN 在 Detectron 框架下由 Caffe2 实现。

19830
来自专栏SnailTyan

非极大值抑制(Non-Maximum Suppression)

1. 什么是非极大值抑制 非极大值抑制,简称为NMS算法,英文为Non-Maximum Suppression。其思想是搜素局部最大值,抑制极大值。NMS算法在...

50400
来自专栏ATYUN订阅号

在Keras中展示深度学习模式的训练历史记录

通过观察神经网络和深度学习模型在训练期间的表现,你可以得知很多有用的信息。 Keras是Python中强大的库,为创建深度学习模型提供了一个简单的接口,并包装了...

67090
来自专栏深度学习那些事儿

TensorFlow中滑动平均模型介绍

其中a的取值范围[0,1],具体就是:本次滤波结果=(1-a)*本次采样值+a*上次滤波结果,采用此算法的目的是:

55490
来自专栏IT派

值得探索的 8 个机器学习 JavaScript 框架

JavaScript开发人员倾向于寻找可用于机器学习模型训练的JavaScript框架。下面是一些机器学习算法,基于这些算法可以使用本文中列出的不同JavaSc...

15700
来自专栏ATYUN订阅号

深度学习与R语言

对于R语言用户来说,深度学习还没有生产级的解决方案(除了MXNET)。这篇文章介绍了R语言的Keras接口,以及如何使用它来执行图像分类。文章结尾会通过提供一些...

60940
来自专栏深度学习那些事儿

浅谈深度学习中超参数调整策略

深度学习中,设计模型以及保证模型的正确性是首要需要考虑的。当模型设置完成时,理论上模型不存在问题,实现效果也通过计算可以复现出来。一切准备就绪后,那么接下来需要...

374110
来自专栏人工智能头条

模仿人类智慧——“多任务学习”动手实践

10830
来自专栏新智元

谷歌大脑开源TensorFuzz,自动Debug神经网络!

【新智元导读】众所周知,神经网络难以debug。谷歌大脑的Augustus Odena和Ian Goodfellow提出了一种新方法,能够自动Debug神经网络...

9930

扫码关注云+社区

领取腾讯云代金券