基于用户特征和链接关系的Louvain算法研究  

Research of Louvain Algorithm Based on User Features and Linkage

作　　者：胡健[1] 薛龙龙 HU Jian;XUE Longlong(North China University of Technology,Beijing 100144)

机构地区：[1]北方工业大学

出　　处：《计算机与数字工程》2019年第8期1974-1978,2008,共6页Computer & Digital Engineering

摘　　要：Louvain算法是基于模块度的凝聚类社区发现算法,该算法有易于理解、非监督、计算快速的特点且能够发现层次性社区结构,其优化的目标是最大化整个图的模块度。在使用Louvain算法进行社区发现时,多数研究者采用给节点间的边赋相等的初值而未考虑边的实际权重及其有向边对社区发现结果的影响,为了进一步改善社区发现的结果,论文提出一种融合AHP层次分析法、PageRank算法思想及Louvain算法的社区发现方法,取名为APL。该方法首先利用AHP层次分析法对提取出的用户特征进行权重划分,然后计算各个用户初始影响力并利用PageRank思想计算用户的最终影响力,再根据用户的最终影响力计算网络中各边的权值,最后,运用Louvain社区发现方法对初始化后的加权网络进行社区划分。通过在真实的微博数据上的实验表明,论文提出的方法能改善社区发现的结果。Louvain algorithm is a agglomerative community discovery algorithm based on modularity.The algorithm has the advantages of easy to understand,unsupervised and computationally fast,and can discover the hierarchical community structure.It's goal of optimization is to maximize the modularity of the whole graph.When Louvain algorithm is used for community discovery,most researchers use the same initial value of edge assignment between nodes without considering the impact of the actual weight of the edge and directed edge on the community discovery results.In order to further improve the results of community discovery.This paper proposes a community discovery method based on AHP,PageRank algorithm and Louvain algorithm which is named APL.Firstly,AHP method is used to weight the extracted user features.Then,the initial influence of each user is calculated and the final influence of users is calculated by using PageRank theory.Then the weight of each edge of the network is calculated according to the user's final influence.Finally,Louvain community discovery method is used to classify the initialized weighted network.Experiments on real Weibo data show that the proposed method can improve the results of community discovery.

关 键 词：社区发现 Louvain算法 社交网络 PAGERANK算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]