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

doi:10.12263/DZXB.20190129

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

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

马慧芳^1,2,3, 邴睿¹, 赵卫中⁴, 常亮²

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-fang^1,2,3, BING Rui¹, ZHAO Wei-zhong⁴, CHANG Liang²

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

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

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

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

中图分类号:

TP301.6

马慧芳, 邴睿, 赵卫中, 等. 面向距离查询的属性加权图聚集算法[J]. 电子学报, 2021, 49(1): 132-139.

MA Hui-fang, BING Rui, ZHAO Wei-zhong, et al. Distance-Query-Oriented Attribute Weighted Graph Aggregation Algorithm[J]. Acta Electronica Sinica, 2021, 49(1): 132-139.

参考文献

[1] 张建朋,等.基于采样的大规模图聚类分析算法[J].电子学报,2019,47(8):1731-1737. ZHANG Jian-Peng,et al.A sampling-based graph clustering algorithm for large-scale networks[J].Acta Electronica Sinica,2019,47(8):1731-1737.(in Chinese)
[2] 潘秋萍,游进国,等.图聚集技术的现状与挑战[J].软件学报,2015,26(1):167-177. Pan QiuPing,You JinGuo,et al.Progress and challenges of graph aggregation and summarization techniques[J].Journal of Software,2015,26(1):167-177.(in Chinese)
[3] Chen C,et al.Graph OLAP:towards online analytical processing on graphs[A].Proceedings of the International Conference on Data Mining[C].Pisa,Italy:IEEE,2008.103-112.
[4] Le Fevre K,Terzi E.GraSS:Graph structure summarization[A].Proceedings of the International Conference on Data Mining[C].Sydney,Australia:IEEE,2010.454-465.
[5] Navlakha S,Rastogi R,Shrivastava N.Graph summarization with bounded error[A].Proceedings of the International Conference on Management of Data[C].Vancouver,Canada:ACM,2008.419-432.
[6] 尹丹,高宏,邹兆年.一种新的高效图聚集算法[J].计算机研究与发展,2011,48(10):1831-1841. Yin Dan,Gao Hong,Zou ZhaoNian.A novel efficient graph aggregation algorithm[J].Journal of Computer Research and Development,2011,48(10):1831-1841.(in Chinese)
[7] Liu Z,Yu J X,Cheng H.Approximate homogeneous graph summarization[J].Journal of Information Processing,2011,20(1):77-88.
[8] Tian Y Y,Hankins R A,Patel J M.Efficient aggregation for graph summarization[A].Proceedings of the International Conference on Management of Data[C].Vancouver,BC,Canada:ACM,2008.419-432.
[9] Zhang N,Tian Y Y,Patel J M.Discovery-driven graph summarization[A].Proceedings of the International Conference on Data Engineering[C].Long Beach,USA:IEEE,2010.880-891.
[10] Toivonen H,Zhou F,Hartikainen A,et al.Compression of weighted graphs[A].Proceedings of the International Conference on Knowledge Discovery and Data Mining[C].San Diego,USA:ACM,2011.965-973.
[11] 胡宝丽,等.一种有效的加权图聚集算法[J].中国科学技术大学学报,2016,46(3):180-187. Hu BaoLi,et al.An efficient weighted graph aggregation algorithm[J].Journal of University of Science and Technology of China,2016,46(3):180-187.(in Chinese)
[12] Maserrat H,Pei J.Neighbor query friendly compression of social networks[A].Proceedings of the International Conference on Knowledge Discovery and Data Mining[C].Washington,DC,USA:ACM,2010.533-542.
[13] Van Schaik S J,De Moor O.A memory efficient reachability data structure through bit vector compression[A].Proceedings of the International Conference on Management of Data[C].Athens,Greece:ACM,2011.913-924.
[14] Ruan N,Jin R,Huang Y,Distance preserving graph simplification[A].Proceedings of the International Conference on Data Mining[C].Vancouver,Canada:IEEE,2011.1200-1205.
[15] Sadri A,et al.Shrink:Distance preservinggraph compression[J].Information Systems,2017,69:180-193.
[16] Chang L,Li W,Qin L,et al.PSCAN:Fast and exact structural graph clustering[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(2):387-401.

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

Distance-Query-Oriented Attribute Weighted Graph Aggregation Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	施炜杰, 董一鸿, 钱江波, 陈华辉, 辛宇. SCBT-index:基于谱编码的子图索引算法[J]. 电子学报, 2020, 48(1): 110-117.
[2]	黄云, 洪佳明, 覃遵跃, 钟键, 李梦婷, 印鉴. ERSearch:一种高效的子图查询算法[J]. 电子学报, 2017, 45(2): 368-375.
[3]	戴文战, 姜晓丽, 李俊峰. 基于人眼视觉特性的NSCT医学图像自适应融合[J]. 电子学报, 2016, 44(8): 1932-1939.
[4]	沈军民, 李俊峰, 戴文战. 结合结构信息和亮度统计的无参考图像质量评价[J]. 电子学报, 2016, 44(4): 804-812.
[5]	杨静, 王超, 张健沛. 基于敏感属性熵的微聚集算法[J]. 电子学报, 2014, 42(7): 1327-1337.
[6]	米曾真. 小波域中CSF频率与方向加权的图像质量评价方法[J]. 电子学报, 2014, 42(7): 1273-1276.
[7]	宁卓;孙知信;龚俭;张维维. 利用流量特征的GIDS报文分类优化算法[J]. 电子学报, 2012, 40(3): 530-537.
[8]	杨春玲;高文瑞. 基于结构相似的小波域图像质量评价方法的研究[J]. 电子学报, 2009, 37(4): 845-849.
[9]	叶盛楠;苏开娜;肖创柏;段娟. 基于结构信息提取的图像质量评价[J]. 电子学报, 2008, 36(5): 856-861.
[10]	杨春玲, 陈冠豪, 谢胜利. 基于梯度信息的图像质量评判方法的研究[J]. 电子学报, 2007, 35(7): 1313-1317.