东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

一种新的高效图聚集算法

ISSN号：1000-1239
期刊名称：计算机研究与发展
时间：2011.10.1
页码：1831-1841
分类：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
作者机构：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001
相关基金：国家自然科学基金项目（61173023,60933001）;中央高校基本科研业务费专项资金（HIT.NSRIF.201180）
相关项目：海量不确定图挖掘算法研究

关键词：图聚集, 顶点相似性, 聚集图质量函数, 局部敏感Hash, 熵, graph aggregation, node similarity, aggregated graph quality function, Locality SensitiveHash , entropy

中文摘要：

图聚集是将一个大规模的图用简洁的并能有效反映原始图的结构和属性信息的小规模图来表示的技术．图聚集在图数据管理、分析和可视化中发挥着重要作用．图聚集方面现有研究结果还很少，也很不系统．其主要不足之处是：1）算法依赖于具体应用；2）算法仅考虑了图的某方面信息，如结构信息或属性信息；3）算法对用户提供的交互和反馈信息的约束很强．针对现有图聚集算法存在的主要不足，提出一种有向图新型图聚集算法，该算法采用一种新的聚集图质量函数，全面刻画了聚集图多样性、覆盖性、简洁性和实用性．该算法使用LSH（locality sensitive Hashing）技术和基于熵的划分技术，保证了聚集图的质量．在真实数据集上进行了大量的实验，验证了算法的有效性．

英文摘要：

Many real world datasets can be modeled as graphs, where nodes represent objects and edges indicate relationships between nodes. Today, large graphs are common in many domains, such as social networks and road networks. Graph aggregation is a new technique for representing a largescale graph by a concise graph that can capture the structural and attributive information of the original large graph. Graph aggregation plays an important role in the management, analysis and visualization of graph data. However, there are very few research results in graph aggregation. Moreover, the existing results are far from systematic. The main problems are. 1）depending on specific applications~ 2）only considering partial information of graph, such as structures or attributes of original graphs 3）having strict constraints on users＇ interactions and feedbacks. To this end, this paper proposes a new graph aggregation algorithm on directed graphs, which adopts a new quality measuring function for aggregation graphs, characterizing the diversity, coverage, conciseness and utility of aggregated graphs. The algorithm guarantees the quality of aggregation graphs by means of Locality Sensitive Hashing （LSH） according to the Jaccard similarity of node attributes and an entropy-based partitioning method. Experiments on real datasets demonstrate the effectiveness and efficiency of the algorithm.

同期刊论文项目