arrow
返回

Three Algorithms for Parallel Graph Summarization

delete2025-12-09
delete0
PRE
AI
T
Till Blume
J
Jannik Rau
D
David Richerby
A
Ansgar Scherp *
DOI:10.1111/exsy.70179delete
delete原文链接
delete分享
delete收藏
摘要

摘要

En 中文
大多数图摘要算法都是针对特定的图摘要模型定制的,并且仅设计用于一次性计算,即基于批次的计算。我们开发了一种通用的并行图摘要方法,以及三种计算图摘要的算法——用于静态图的基于批次的算法、用于演化图的增量算法,以及一种可扩展至大型图和大型模式结构的基于哈希的算法,即使用长度为k $$ k $$的路径来定义顶点等价。通过在基准数据集和真实世界数据集上的实验,我们观察到增量算法几乎总是比批处理计算更快,即使在图有50%的变化时,甚至在使用的核心更少时也是如此;然而,它仅使用8%更多的内存( ± 1 % $$ \pm 1\% $$ )。此外,我们证明基于哈希的算法可以在包含超过10 M边的图上在几秒内计算10跳等价子图,在包含100 + M边的图上在几分钟内完成,并在包含1 + B边的图上在不到一小时的时间内完成。我们详细分析了我们算法的复杂度,并证明了增量算法的正确性。总体而言,我们通过这三种算法表明,我们的并行图摘要方法是通用的,并为需要大规模图摘要的各种应用开辟了道路。
Keyword:
graph summarisation
k-bisimulation
parallel algorithms
temporal graphs

期刊

Expert Systems 封面图
Expert Systems
IF:
2.3
论文数:
2.6K
被引数:
4.8K

机构

U
university of essex
学者数:
287
论文数: 196
被引数: 3.6K
U
ulm university
学者数:
349
论文数: 130
被引数: 9.5K
E
ernst & young gmbh wpg – r&d, berlin, germany
学者数:
1
论文数: 1
被引数: 0
学者 查看更多机构
引用论文

引用论文

LODatio
err2013-06-23
err0
PREAI
errGottron,Thomas; Scherp,Ansgar; Krayer,Bastian; Peters,Arne
err分享
err收藏
Incremental graph pattern matching
err2011-06-12
err0
errOAAI
errWenfei Fan; Jianzhong Li; Jizhou Luo; Zijing Tan; Xin Wang; Yinghui Wu
err分享
err收藏
S+EPPs
err2015-08-01
err0
PREAI
errMariano P. Consens; Valeria Fionda; Shahan Khatchadourian; Giuseppe Pirrò
err分享
err收藏
err分享
err收藏
err分享
err收藏
Pregel
err2010-06-06
err0
PREAI
errGrzegorz Malewicz; Matthew H. Austern; Aart J.C Bik; James C. Dehnert; Ilan Horn; Naty Leiser; Grzegorz Czajkowski
err分享
err收藏
RDF graph summarization for first-sight structure discovery
err2020-04-30
err0
PREAI
errFrançois Goasdoué; Paweł Guzewicz; Ioana Manolescu
err分享
err收藏
学者 查看更多内容