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

STUDY ON SHORTEST PATH-BASED CLUSTERING ALGORITHM OF WEIGHTED ATTRIBUTE GRAPH

作　　者：张素智[1] 张琳[1] 曲旭凯 

机构地区：[1]郑州轻工业学院计算机与通信工程学院,河南郑州450002

出　　处：《计算机应用与软件》2016年第11期212-214,281,共4页Computer Applications and Software

基　　金：国家自然科学基金青年科学基金项目(61201447)

摘　　要：图在计算机领域是一种重要的数据结构,可以用来描述事物之间的复杂关系。图的节点和边具备一个或者多个不同的属性。如何结合属性对图进行聚类是目前所面临的一个新的挑战。目前的属性图聚类算法,多存在聚类效果差,消耗资源多,效率低等缺点。针对以上问题,提出一种基于最短距离的加权属性图聚类算法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 consumption and low efficiency. In view of the above problems,this paper puts forward a shortest path-based weighted attribute graph clustering algorithm,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.

关 键 词：图 加权属性图 最短路径 聚类 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]