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

Nodes similarity measure method based on sturcture-attribute balance graph

作　　者：韩启龙[1] 潘海为[1] 蔡绍滨[1] 姚念民[1] 印桂生[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机工程与应用》2013年第1期15-18,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61272184;No.41176082);黑龙江省自然科学基金(No.F201024);中央高校基本科研业务费专项资金(No.HEUCFZ1010;No.HEUCF100602);哈尔滨工程大学科技园基础科研培育基金

摘　　要：节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低。为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度。与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率。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.

关 键 词：图聚类 结构-属性平衡图 随机游走模型 统一度量 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]