Community detection involves grouping nodes in a graph with dense connections within groups, than between them. Recently, efficient multicore (GVE-LPA) and GPU-based (ν -LPA) implementations of Label Propagation Algorithm (LPA) for community detection have been proposed. However, these methods incur high memory overhead due to their per-thread/per-vertex hashtables. This makes it challenging to process large graphs on shared memory systems. In this paper, we introduce memory-efficient GPU-based LPA, using weighted Boyer-Moore (BM) and Misra-Gries (MG) sketches. Our ν MG8-LPA, using an 8-slot MG sketch, reduces memory usage by 98 × and 44 × compared to GVE-LPA and ν -LPA, respectively. It is also 2.4 × faster than GVE-LPA and only 1.1 × slower than ν -LPA, with minimal quality loss (below \(5\%\) on average).

ABSTRACT Link prediction can help rectify inaccuracies in various graph algorithms, stemming from unaccounted‐for or overlooked links within networks. However, many existing works use a baseline approach, which incurs unnecessary computational costs due to its high time complexity. Further, many studies focus on smaller graphs, which can lead to misleading conclusions. Here, we study the prediction of links using neighborhood‐based similarity measures on large graphs. In particular, we improve upon the baseline approach (IBase), and propose a heuristic approach that additionally disregards large hubs (DLH), based on the idea that high‐degree nodes contribute little similarity among their neighbors. On a server equipped with dual 16‐core Intel Xeon Gold 6226R processors, DLH is on average faster than IBase, especially on web graphs and social networks, while maintaining similar prediction accuracy. Notably, DLH achieves a link prediction rate of 38.1M edges/s and improves performance by for every doubling of threads.

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions is critical in a number of applications, where the size of datasets have reached significant scales. This paper presents one of the most efficient implementations of the Leiden algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Leiden implementation, which we term as GVE-Leiden, outperforms NetworKit Leiden and cuGraph Leiden (running on NVIDIA A100 GPU) by 8.2 × and 3.0 × respectively — achieving a processing rate of 403M edges/s on a 3.8B edge graph. In addition, GVE-Leiden improves performance at a rate of 1.6 × for every doubling of threads.