结构-属性平衡图节点相似度测量算法

摘要

Nodes similarity is the basis of graph clustering algorithm. The existing clustering algorithms based on structure and attribute graph are lower efficiency because of the constrains of traditional graph model. To resolve the problem, a measure method of graph nodes similarity is proposed, which is based on the structure and attribute balance graph notion and random walk model. Compared with existing methods, the proposed method measures the similarity not only directed nodes but also undirected nodes, and improves the algorithm efficiency without increasing the scale of similarity matrix.%节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低.为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度.与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率.