东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2015, Vol. 36 ›› Issue (5): 609-613.DOI: 10.12068/j.issn.1005-3026.2015.05.001

• 信息与控制 •    下一篇

利用多级社区中心标签实现大规模图上距离查询

张翼飞， 王国仁， 张恩德， 赵长宽   

  1. (东北大学 信息科学与工程学院， 辽宁 沈阳110819)
  • 收稿日期:2014-04-03 修回日期:2014-04-03 出版日期:2015-05-15 发布日期:2014-11-07
  • 通讯作者: 张翼飞
  • 作者简介:张翼飞(1976-)，男，吉林白山人，东北大学博士研究生，沈阳航空航天大学副教授; 王国仁(1966-)，男，湖北崇阳人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金青年基金资助项目(61303016)； 辽宁省教育厅一般项目(L2012045).

Utilizing Multilevel Community Center Labels for Distance Querying in Large Graphs

ZHANG Yi-fei， WANG Guo-ren， ZHANG En-de， ZHAO Chang-kuan   

  1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.
  • Received:2014-04-03 Revised:2014-04-03 Online:2015-05-15 Published:2014-11-07
  • Contact: ZHANG Yi-fei
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

830

摘要： 距离查询是图数据挖掘应用中的最基本的操作之一，但是目前的现存查询算法均无法高效处理大规模图数据.针对这个问题，提出建立多级社区中心的标签机制，即首先在原图中将结点按社区划分为多个集合，然后再将各集合中的中心结点建成带权查询子图，经过多次递归操作，最终为各结点建立一个基于社区中心的树状结构标签集，该标签集可以实现利用较短的创建时间和较小的存储代价大幅度提高距离查询的效率.从实验结果可以看出，该方法综合效率明显优于现存的高效算法.

关键词: 多级社区中心, 标签, 大规模图数据, 距离查询, 带权查询

Abstract: Distance querying is one of the most fundamental operations in many graph data mining applications. However， most of the previous methods cannot handle large graphs， especially those with more than a hundred thousand vertices. To solve this problem， a multilevel community center labels index structure was proposed. Firstly， the vertices of the original graph were divided into different communities. Then a weighted query sub-graph was constructed by each community center. Finally， a tree-like label set was built for every vertex. The query efficiency could be improved greatly with small time and storage cost. The experimental result showed that the overall efficiency of this approach is significantly better than those of the-state-of-the-art algorithms.

Key words: multilevel community center, label, large graphs, distance query, weighted query

中图分类号: