K-truss decomposition for Scale-Free Graphs at Scale in Distributed Memory
K-truss decomposition for Scale-Free Graphs at Scale in Distributed Memory
复制标题
分布式内存中大规模无标度图的 K 桁架分解
DOI：
10.1109/hpec.2018.8547572
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
G. Sanders
中科院分区：
文献类型：
--
作者：
R. Pearce;G. Sanders
我们更新了之前关于分布式内存中大规模三角形计数的 2017 年图形挑战提交 [11]，将其扩展为计算大型无标度图的完整 $k$-truss 分解 [6]。我们建立在启发式的基础上，通过在有序有向图上进行操作来最小化“楔形检查”，并描述了一种算法，以在计划通过$k$-桁架分解进行修剪时“展开”三角形计数。我们的 $k$-truss 算法是使用 HavoqGT 实现的，HavoqGT 是一种用于分布式内存的异步以顶点为中心的图形分析框架。我们对两个大型的、真实的、无标度的图进行了简短的实验评估：一个 128B 边缘网络图和一个 1.4B 边缘 Twitter 关注者图。据我们所知，128B 边网络图是计算 $k$ 桁架分解的最大现实世界图。
We update our prior 2017 Graph Challenge submission [11] on large scale triangle counting in distributed memory by extending it to compute the full $k$-truss decomposition [6] of large scale-free graphs. We build on heuristics to minimize ‘wedge checks', by operating on an ordered directed graph, and describe an algorithm to ‘unroll’ triangle counts when they are scheduled for pruning by the $k$-truss decomposition. Our $k$-truss algorithm is implemented using HavoqGT, an asynchronous vertex-centric graph analytics framework for distributed memory. We present a brief experimental evaluation on two large, real-world, scale-free graphs: a 128B edge web-graph and a 1.4B edge twitter follower graph. To our knowledge, the 128B edge web-graph is the largest real-world graph to have its $k$-truss decomposition computed.