一种有效的加权图聚集算法  

An efficient weighted graph aggregation algorithm

作　　者：胡宝丽[1] 游进国[1] 周翠莲[1] 王洋[1] 崔红波[1] 

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500

出　　处：《中国科学技术大学学报》2016年第3期180-187,共8页JUSTC

基　　金：国家自然科学基金(61462050);云南省自然科学基金(2013FZ020;KKSY201303095)资助

摘　　要：图聚集(图概括)技术是解决大规模网络的有效技术之一.现实生活中,这些图不仅规模大,而且边可能带有权重,当前图聚集算法很少或未考虑边的权重或边存在的概率等信息,导致聚集图与原图的误差大.为了提高加权图的图聚集的质量和效率,对加权图的图聚集算法进行了研究.为此引入超图邻接矩阵分组的权重值一致性来衡量边权重的一致性,定义压缩率衡量图聚集算法的空间效率,使用误差率衡量聚集图与原图的误差;通过控制图的误差率来控制图的压缩质量,并与现有图聚集算法进行了对比.实验论证了本文图聚集算法的有效性.Graph aggregation( graph summarization) technique is one of the effective ways to mine and analyze huge graphs. However,in reality,these graphs are not only huge but also carry weighted edges. The current algorithms do not or seldom take the weight into consideration,leading to a great difference between the aggregation graph and the original one. In order to solve this problem and improve the quality and efficiency of graph aggregation,The weighted graph aggregation algorithm was studied,the consistency of grouping area values of the adjacent matrix of the aggregation graphs was introduced to measure the consistency of weights of edges,compression ratio was defined to measure the spatial efficiency of the graph aggregation algorithm,and error rate was used to evaluate the difference between the aggregation graph and the original graph. The compression quality is ensured by controlling error rates and a comparison is made between the proposed algorithm and the existing graph aggregation algorithms. The experiment results show the effectiveness of the graph aggregation algorithm.

关 键 词：图数据 加权图 图聚集 图概括 压缩率 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]