Fast Parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs
Fast Parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs
复制标题
DOI：
10.1145/3605573.3605637
复制
发表时间：
2023-08
期刊：
影响因子：
--
通讯作者：
M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;Cy Chan;J. Shalf;S. Arifuzzaman
中科院分区：
文献类型：
--
作者：
M. A. M. Faysal-M.-A.-M.-Faysal-65776774;Maximilian H. Bremer;Cy Chan;J. Shalf;S. Arifuzzaman
寻找凝聚子图是一个重要的图分析核心，广泛用于社会和生物网络（图）。有各种方法可以发现网络中有洞察力的子结构，例如发现集团，社区发现和桁架分解。寻找团是一个计算上难以解决的问题，这使得在大型图中识别凝聚子图变得困难。一种可能的解决方案是k-桁架分解，这是一种可以在多项式时间内求解的松散形式。此外，与全球社区检测不同，它专注于将整个图分解为不相交的社区，本地或面向目标的社区搜索旨在找到感兴趣的实体的社区。在这项工作中，我们确定了一个k-桁架诱导的社区发现技术，可以在多项式时间内检测到本地社区。然而，大多数以前的研究都探讨了k-桁架诱导的局部社区形成在一个系列的设置，使他们不适合大型图。在本文中，我们设计了一个并行k-truss诱导的本地社区建设方法，利用多核并行。据我们所知，这是第一次尝试并行化这种算法的方法与广泛的性能分析。我们的实验表明，使用NERSC Perlmutter计算节点，对于具有数亿到数十亿条边的图形，性能得到了显着提高，加速比从19倍提高到55倍。
Finding cohesive subgraphs is a crucial graph analysis kernel widely used for social and biological networks (graphs). There exist various approaches for discovering insightful substructures in a network, such as finding cliques, community discovery, and truss decomposition. Finding cliques is a computationally intractable problem, making it difficult to identify cohesive subgraphs in large graphs. One possible solution is k-truss decomposition, which is a relaxed form of finding cliques that can be solved in polynomial time. Further, unlike global community detection–which focuses on breaking down the entire graph into disjoint communities–a local or goal-oriented community search aims at finding the community of an entity of interest. In this work, we identify a k-truss-induced community discovery technique that can detect local communities in polynomial time. However, most previous studies have explored k-truss-induced local community formation in a serial setting, making them unsuitable for large graphs. In this paper, we design a parallel k-truss-induced local community construction method using multi-core parallelism. To the best of our knowledge, this is the first attempt to parallelize this algorithmic approach with extensive performance analysis. Our experiments demonstrate a significant performance improvement, with speedups from 19x to 55x for graphs with hundreds of millions to billions of edges, using NERSC Perlmutter compute nodes.