一种基于结构和属性的图聚类算法研究

Research on Graph Clustering Algorithm Based on Structure and Attribute

图是一种有效、简单而系统的建模方式,如何有效、准确的进行图聚类是目前的一个研究热点.本文提出一种基于结构和属性的图聚类算法,首先,针对传统k-means算法对初始聚类中心敏感的问题,提出一种基于相似度的初始聚类中心算法,对结构—属性相似度矩阵的行进行求和,按照从大到小顺序提取前K个不重叠值所对应的顶点作为初始聚类中心;其次,提出一种动态属性权重确定方法,根据上一次迭代后的聚类结果,考虑属性的不同取值数量以及属性值的分布情况,确定下一轮聚类时顶点属性的权重;再次,利用动态属性权重,计算节点间的属性—结构相似度,进行k-means聚类;最后,通过实验验证本文算法的正确性和有效性.

Graph is one of the effective,simple and systematic modeling pattern,and howto cluster graph effectively and exactly is a research hotspot. The paper proposed a graph clustering algorithm based on structure and attributes. Firstly,we put forward an initial clustering center algorithm based on similarity,which summed the rows in the similarity matrix of structure and attribute and regarded the first K clustering-unduplicated vertices in descending as the initial clustering centers; secondly,we proposed a method to obtain the dynamic attribute weight according to the last clustering results and attribute distribution; thirdly,we calculated the attribute-structure similarity between vertices and carried out the k-means clustering using the dynamic attribute weight; lastly,experiments verified correctness and availability of our algorithm.