论文标题
三角形通过封面计数
Triangle Counting Through Cover-Edges
论文作者
论文摘要
在现实世界分析中通常使用计数和查找三角形，以表征凝聚力并识别图中的社区。在本文中，我们提出了一个新颖的封面套件概念，可用于更有效地找到三角形。我们使用广度优先搜索（BFS）快速生成紧凑的盖套件。提出了采用覆盖范围集的新型顺序和平行三角计数算法。顺序算法避免了不必要的三角检查操作，并且并行算法是沟通效率的。该平行算法可以渐近地减少大量图形上的通信，例如来自真实的社交网络和Graph500基准的合成图。在我们从大规模的Graph500图中的估计中，我们的新的并行算法可以将比例36图上的通信减少1156X，并在比例42图上缩小2368X的图表。
Counting and finding triangles in graphs is often used in real-world analytics to characterize cohesiveness and identify communities in graphs. In this paper, we propose the novel concept of a cover-edge set that can be used to find triangles more efficiently. We use a breadth-first search (BFS) to quickly generate a compact cover-edge set. Novel sequential and parallel triangle counting algorithms are presented that employ cover-edge sets. The sequential algorithm avoids unnecessary triangle-checking operations, and the parallel algorithm is communication-efficient. The parallel algorithm can asymptotically reduce communication on massive graphs such as from real social networks and synthetic graphs from the Graph500 Benchmark. In our estimate from massive-scale Graph500 graphs, our new parallel algorithm can reduce the communication on a scale 36 graph by 1156x and on a scale 42 graph by 2368x.
