基于最短路径的加权属性图聚类算法研究

摘要

图在计算机领域是一种重要的数据结构，可以用来描述事物之间的复杂关系。图的节点和边具备一个或者多个不同的属性。如何结合属性对图进行聚类是目前所面临的一个新的挑战。目前的属性图聚类算法，多存在聚类效果差，消耗资源多，效率低等缺点。针对以上问题，提出一种基于最短距离的加权属性图聚类算法 WASP（weighted attribute graph clustering algorithm based on shortest path），建立加权属性无向图模型，在此模型上基于最短路径算法度量节点间的关联度，以此为原则选取新的聚类中心对图进行聚类。实验表明，新的聚类算法具有更高效的聚类效果。%Graph is an important data structure in computer science,and can be used to describe the complex relationship between things. The nodes and edges in graph have one or more different attributes.How to cluster the graph in combination with attributes is a new challenge encountered at present.Many of current attribute graph clustering algorithms have the drawbacks of poor clustering effect,big resource con-sumption and low efficiency.In view of the above problems,this paper puts forward a shortest path-based weighted attribute graph clustering al-gorithm,and builds the weighted attribute undirected graph model.Based on the model the algorithm measures the correlation degree between the nodes based on shortest path algorithm,and takes this as the principle to select new clustering centre to cluster the graph.Experiment shows that the new clustering algorithm has more efficient clustering effect.