电子学报 ›› 2021, Vol. 49 ›› Issue (1): 132-139.DOI: 10.12263/DZXB.20190129

• 学术论文 • 上一篇    下一篇

面向距离查询的属性加权图聚集算法

马慧芳1,2,3, 邴睿1, 赵卫中4, 常亮2   

  1. 1. 西北师范大学计算机科学与工程学院, 甘肃兰州 730070;
    2. 桂林电子科技大学广西可信软件重点实验室, 广西桂林 541004;
    3. 广西师范大学广西多源信息挖掘与安全重点实验室, 广西桂林 541004;
    4. 华中师范大学计算机学院, 湖北武汉 430079
  • 收稿日期:2019-01-22 修回日期:2020-03-12 出版日期:2021-01-25
    • 作者简介:
    • 马慧芳 女,1981年7月出生,甘肃兰州人.博士,硕士生导师,现为西北师范大学计算机科学与工程学院教授.研究领域为数据挖掘与机器学习.E-mail:mahuifang@yeah.net;邴睿 男,1994年10月出生,甘肃兰州人.现为西北师范大学计算机科学与工程学院硕士.研究方向为机器学习.E-mail:bingrui1030@qq.com
    • 基金资助:
    • 国家自然科学基金 (No.61762078,No.61363058,No.61762079); 广西多源信息挖掘与安全重点实验室开放基金 (No.MIMS18-08); 广西可信软件重点实验室研究课题 (No.kx202003)

Distance-Query-Oriented Attribute Weighted Graph Aggregation Algorithm

MA Hui-fang1,2,3, BING Rui1, ZHAO Wei-zhong4, CHANG Liang2   

  1. 1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou, Gansu 730070, China;
    2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China;
    3. Guangxi Key Laboratory of Multi-source Information Mining&Security, Guangxi Normal University, Guilin, Guangxi 541004, China;
    4. School of Computer, Central China Normal University, Wuhan, Hubei 430079, China
  • Received:2019-01-22 Revised:2020-03-12 Online:2021-01-25 Published:2021-01-25
    • Supported by:
    • National Natural Science Foundation of China (No.61762078, No.61363058, No.61762079); Guangxi Key Laboratory Foundation for Multi-source Information Mining and Security (No.MIMS18-08); Research Project of Guangxi Key Laboratory of Trusted Software (No.kx202003)

摘要: 图聚集技术是在保留原始图的结构和属性信息的同时,将一个大规模图聚集成简洁的小规模图的技术.随着图的规模不断增加使得图数据变得难以查询和存储,而基于距离的查询,例如最短路径查询,非常依赖图的规模大小.本文提出了面向距离查询的属性加权图聚集算法,在保证节点之间结构和属性相似的同时,保护了节点之间的距离,并有效地减小了图规模.实验证明本文方法的有效性与在查询任务上的高效性.

 

关键词: 图聚集, 图查询, 距离保护, 结构相似度, 属性熵

Abstract: Graph aggregation is a technology that aggregates a large-scale graph into a compact and small-scale graph while retaining the structure and attribute information of the original graph. With the increasing size of graph, graph data becomes difficult to query and store. Distance-based queries, such as shortest path queries, depend heavily on the size of graph.In this paper, a distance query-oriented attribute weighted graph aggregation algorithm is proposed, which not only guarantees the similarity of structure and attributes between nodes, but also preserves the distance between nodes, and effectively reduces the size of the graph. The experiments prove that this method is effective and efficient in the query tasks.

 

Key words: graph aggregation, graph query, distance preserving, structure similarity, attribute entropy

中图分类号: