Python实现Label Propagation社区划分算法

淡淡的烟草味﹌ 2021-08-19 14:47 326阅读 0赞

声明：代码的运行环境为Python3。Python3与Python2在一些细节上会有所不同，希望广大读者注意。本博客以代码为主，代码中会有详细的注释。相关文章将会发布在我的个人博客专栏[《Python从入门到深度学习》][Python]，欢迎大家关注。

--------------------

开篇之前先来一段很老套的开场白吧~ 随着经济的日益发展，人们可以在社交网站上进行交流，在这些交流的背后，不仅存在着用户之间的社交关系，还存在着用户之间的兴趣关系。为了能够对相关社交网站（例如：微博）上的用户进行聚类，可以使用社区划分的算法对用户进行聚类分析，本文主要讲述Label Propagation社区划分算法。

社区通俗来讲就是网络中节点的集合，为什么这么说呢？因为社区结构指的是在网络中，由一些节点构成特定的分组，在同一个分组内的节点通过节点之间的边紧密的连在一起，而分组与分组之间，则连接比较松散，称每一个分组称一个社区。

**一、Label Propagation算法原理**

众所周知，Fast Unfolding算法是基于模块度的算法，不同于Fast Unfolding算法的是，Label Propagation算法是基于标签传播的局部社区划分算法。在初始阶段，Label Propagation算法给每一个节点设置一个唯一的标签，在每一次迭代的过程中，每一个节点选择与其相连的节点中所属标签最多的社区标签为自己的社区标签。随着社区标签的不断传播，最终紧密连接的节点将有共同的标签。Label Propagation算法的计算过程比较简单，Label Propagation算法利用网络的结构指导标签的传播过程，在这个过程中无需优化任何函数。随着算法的迭代，最终算法将自己决定社区的个数。

在标签传播的过程中，节点的标签更新可以分为两种情况：同步更新和异步更新。同步更新意思是某个节点在迭代第n次的时候，会根据其所有邻接节点第n-1次迭代的标签结果进行标签更新。同步更新对于一个二分或者近似二分的网络来说会存在着社区标签震荡的情况。这里我们着重介绍异步更新。一部更新是指某个节点在迭代第n次的时候，会根据已经迭代完第n次的标签结果和已经迭代完第n-1次的标签结果进行标签更新。

**二、实现过程**

整个实现过程围绕着异步更新来完成，以下是异步更新的方法：

def label_propagation(vector_dict, edge_dict):
        '''
        标签传播算法
        :param vector_dict: 存储节点和社区的字典
        :param edge_dict: 存储节点之间边和权重的字典
        :return: 返回节点和社区的结果字典
        '''
        iter = 0  # 设置iter作为迭代次数
    
        # 以随机的次序处理每个节点
        while True:
            if (whether_condition_is_satisfied(vector_dict, edge_dict) == 0):  # 不符合条件
                iter = iter + 1  # 迭代次数加一
    
                # 对每一个node进行更新
                for node in vector_dict.keys():
                    adjacent_node_list = edge_dict[node]  # 获取节点node的邻接节点
                    vector_dict[node] = get_node_belong_community(vector_dict, adjacent_node_list)
            else:
                break
        return vector_dict

其中，whether\_condition\_is\_satisfied()方法用来检测是否满足终止条件。终止条件的判定为：对于每一个节点，在其所有的邻居节点所属的社区中，其所属的社区标签是最大的。此时表示满足迭代终止条件，若满足此条件则终止迭代。whether\_condition\_is\_satisfied()方法的实现过程如下：

def whether_condition_is_satisfied(vector_dict, edge_dict):
        '''
        是否满足终止条件
        :param vector_dict: 储节点和社区的字典
        :param edge_dict: 存储节点之间边和权重的字典
        :return: 符合条件返回1，否则返回0
        '''
        for node in vector_dict.keys():
            adjacent_node_list = edge_dict[node]  # 获取与节点相邻的节点列表
            node_community = vector_dict[node]  # 获取节点所属的社区
            get_community = get_node_belong_community(vector_dict, adjacent_node_list)
    
            if node_community == get_community:  # 符合条件
                continue
            else:
                return 0
        return 1

其中，get\_node\_belong\_community()方法是获取某节点所属的社区，即：属于所有邻接节点中标签最多的社区。实现方法如下：

def get_node_belong_community(vector_dict, adjacent_node_list):
        '''
        获取节点所属于的社区：相邻节点中标签数最多的
        :param vector_dict: 存储节点和社区的字典
        :param adjacent_node_list: 节点的邻接节点列表
        :return: 返回节点所属的社区
        '''
        label_dict = {}
    
        for node in adjacent_node_list:
            weight = node.strip().split(":")
            node_name = weight[0]  # 得到节点的邻接节点
            node_weight = int(weight[1])  # 得到与邻接节点的权重
    
            if vector_dict[node_name] not in label_dict:
                label_dict[vector_dict[node_name]] = node_weight
            else:
                label_dict[vector_dict[node_name]] += node_weight
    
        # items()以元组的形式返回字典的键值对，lambda表达式进行降序排序，得到降序排序列表
        desc_list = sorted(label_dict.items(), key=lambda data: data[1], reverse=True)
        # 得到节点所属的社区
        get_community = desc_list[0][0]
        return get_community

**三、测试**

1、加载测试数据

测试需要有测试数据，测试数据可以为两列或三列的数据，两列的数据均为节点，三列的数据最后一列需为权重值。如下所示：

（1）两列数据示例：

2	6
    3	7
    4	10
    5	7
    5	11
    6	7
    6	11
    8	9
    8	10
    8	11

（2）三列数据示例：

2	1	1
    1	4	5
    4	1	2
    1	7	1
    7	1	4
    2	4	2
    4	2	2
    2	5	9
    5	2	7
    2	6	1
    6	2	4
    3	7	1
    7	3	5
    4	10	1
    10	4	4
    5	7	1
    7	5	2
    5	11	1
    11	5	2

这里需要一个加载数据的方法，此方法在前面的文章中也提过不止一次了，可以使用[《Python两种方式加载文件内容》][Python 1]（不限于这两种）加载数据，因为此次聚类算法用到节点和边的概念，所以加载数据的方式与以往略有不同，具体方式如下：

def load_data(file_path):
        '''
        加载数据
        :param file_path: 存储文件的路径
        :return: 返回vector_dict和edge_dict
        '''
        f = open(file_path)
        vector_dict = {}  # 定义存储节点和社区的字典
        edge_dict = {}  # 定义存储节点之间边和权重的字典
    
        for row in f.readlines():
            rows = row.strip().split("\t")
            for i in range(2):
                if rows[i] not in vector_dict:  # 如果节点不在vector_dict中
                    # 将节点放到vector_dict中并设置所属社区为其自身
                    vector_dict[rows[i]] = int(rows[i])
                    # 将边放入到edge_dict中
                    edge_list = []
                    if len(rows) == 3:
                        edge_list.append(rows[1-i] + ":" + rows[2])
                    else:
                        edge_list.append(rows[1-i] + ":" + "1")
                    edge_dict[rows[i]] = edge_list
                else:
                    edge_list = edge_dict[rows[i]]
                    if len(rows) == 3:
                        edge_list.append(rows[1-i] + ":" + rows[2])
                    else:
                        edge_list.append(rows[1-i] + ":" + "1")
                    edge_dict[rows[i]] = edge_list
        f.close()
        return vector_dict, edge_dict

2、保存聚类结果

此处需要有一个方法对测试得到的聚类结果即社区划分结果进行保存，方法如下：

def save_result(file_name, vector_dict_result):
        '''
        保存结果
        :param file_name: 结果文件名
        :param vector_dict_result: 结果字典
        :return:
        '''
        result = open(file_name, "w")
    
        for key in vector_dict_result.keys():
            result.write(str(key) + "\t" + str(vector_dict_result[key]) + "\n")
        result.close()

3、主函数进行测试

if __name__ == '__main__':
        vector_dict, edge_dict = load_data("./test.txt")
        vector_dict_result = label_propagation(vector_dict, edge_dict)
        save_result("result", vector_dict_result)

你们在此过程中遇到了什么问题，欢迎留言，让我看看你们都遇到了哪些问题。

[Python]: https://blog.csdn.net/gdkyxy2013/category_9274573.html
[Python 1]: https://blog.csdn.net/gdkyxy2013/article/details/81979214