高级检索
    尹 丹 高 宏 邹兆年. 一种新的高效图聚集算法[J]. 计算机研究与发展, 2011, 48(10): 1831-1841.
    引用本文: 尹 丹 高 宏 邹兆年. 一种新的高效图聚集算法[J]. 计算机研究与发展, 2011, 48(10): 1831-1841.
    Yin Dan, Gao Hong, and Zou Zhaonian. A Novel Efficient Graph Aggregation Algorithm[J]. Journal of Computer Research and Development, 2011, 48(10): 1831-1841.
    Citation: Yin Dan, Gao Hong, and Zou Zhaonian. A Novel Efficient Graph Aggregation Algorithm[J]. Journal of Computer Research and Development, 2011, 48(10): 1831-1841.

    一种新的高效图聚集算法

    A Novel Efficient Graph Aggregation Algorithm

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

       

      Abstract: 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 large-scale 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.

       

    /

    返回文章
    返回