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

