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 on average).

Network dismantling—the targeted removal of nodes to degrade large-scale connectivity—plays a central role in resilience analysis, epidemic containment, and systemic-risk mitigation. Recent work shows that dismantling performance depends strongly on mesoscale modular structure, suggesting that community-aware strategies may offer advantages over classical centrality-based heuristics. In this work, we perform a large-scale, systematic evaluation of dismantling strategies and introduce gateways as a new mesoscale dismantling concept. While similar experiments exist using degree- and betweenness-based dismantling strategies, we check a new strategy based on gateways, which capture asymmetric entry points into communities and generalize the notion of inter-community connectors. Furthermore, we process a massive dataset of 568,584 LFR benchmark graphs, covering a wide range of degree distributions, community sizes, and mixing parameters. For evaluation, we use both extrinsic (ARI, NMI, FMI, VI) and intrinsic (Modularity, Coverage, Performance, Average Conductance, Average Internal Density) metrics. We find that across parameter regimes and evaluation metrics, classical strategies (degree, betweenness, community connections) and gateway-based dismantling exhibit broadly similar performance. Our results also corroborate recent findings that dismantling effectiveness is robust to the specific partitioning algorithm and that inter-community connectivity plays a dominant role in global fragmentation. The evaluation provides large-scale evidence that gateway-aware dismantling captures an operationally relevant mesoscale mechanism as good as previous approaches and motivates further empirical studies on real networks and cost-aware settings.

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for this purpose are crucial in various applications, particularly as datasets grow to substantial scales. This paper presents an optimized parallel implementation of the Label Propagation Algorithm (LPA), a high speed community detection method, for shared memory multicore systems. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our LPA, which we term as GVE-LPA, outperforms FLPA and NetworKit LPA by 139× and 40× respectively — achieving a processing rate of 1.4B edges/s on a 3.8B edge graph. In addition, GVE-LPA scales at a rate of 1.7× every doubling of threads. To address the issue of internally-disconnected communities with GVE-LPA, we split the obtained communities with a parallel BFS-based approach. The resulting implementation, which we refer to as GSL-LPA, continues to outperform the above mentioned state-of-the-art implementations, which scaling at a rate of 1.6× for every doubling of threads.

Community detection, or clustering, identifies groups of nodes in a graph that are more densely connected to each other than to the rest of the network. The Leiden algorithm, which improves upon the Louvain algorithm, efficiently detects high-quality communities in large networks. Yet, given the size and dynamic nature of real-world graphs, efficient dynamic community detection algorithms capable of tracking community evolution over time are crucial. However, existing algorithms based on Leiden are inefficient and lack support for tracking evolving communities. This paper introduces parallel Naive-dynamic (ND), Delta-screening (DS), and Dynamic Frontier (DF) Leiden algorithms that efficiently track communities over time.

Community detection is the process of grouping nodes in a network into clusters. However, real-world graphs often evolve over time, making repeated community detection on such graphs expensive. In this paper, we extend three dynamic approaches, namely, Naive-dynamic (ND), Delta-screening (DS), and Dynamic Frontier (DF), to a fast multicore implementation of the Leiden algorithm - an algorithm known for its high-quality community detection - using subset renumbering, selective refinement, and load balancing of the aggregation phase. This is, to the best of our knowledge, the first attempt at applying such dynamic approaches to the Leiden algorithm.

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 multicore implementations of the Louvain algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Louvain, which we term as GVE-Louvain, outperforms Vite, Grappolo, NetworKit Louvain, and cuGraph Louvain (running on NVIDIA A100 GPU) by 50×, 22×, 20×, and 5.8× faster respectively - achieving a processing rate of 560M edges/s on a 3.8B edge graph. In addition, GVE-Louvain improves performance at an average rate of 1.6× for every doubling of threads.

PageRank is a centrality measure that ranks graph vertices based on their connections and importance. This paper presents efficient GPU implementations for both Static PageRank and incrementally expanding (and contracting) Dynamic Frontier (DF) and Dynamic Frontier with Pruning (DFP) PageRank, which process only a subset of vertices likely to change ranks. The Static PageRank implementation recomputes scores from scratch using a synchronous, pull-based, atomicsfree approach. It partitions vertices into low and high in-degrees, processed by two separate kernels. Our DF and DF-P PageRank additionally partition low and high out-degree vertices, using two additional kernels for incremental expansion and/or contraction of the set of affected vertices. On an NVIDIA A100 GPU, our Static PageRank outperforms Hornet and Gunrock's implementations by 16.3 × and 5.3 ×, respectively. Further, our DF and DF-P PageRank achieve speedups of 5.2 × 3.9 × on real-world dynamic graphs and 12.8 × 6.2 × on large static graphs with random updates compared to prior multicore implementations.

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions are critical in a number of applications. This paper presents an optimized implementation of the Label Propagation Algorithm (LPA) for community detection, featuring an asynchronous LPA with a Pick-Less (PL) method every 4 iterations to handle community swaps, ideal for SIMT hardware like GPUs. It also introduces a novel per-vertex hashtable with hybrid quadratic-double probing for collision resolution. On an NVIDIA A100 GPU, our implementation, ν-LPA, outperforms FLPA (sequential), NetworKit LPA (multicore), Gunrock LPA (GPU), and cuGraph Louvain (GPU) by 364×, 62×, 2.6×, and 37×, respectively, while running FLPA and NetworKit LPA on a server with dual 16-core and achieves higher modularity than FLPA, but lower than NetworKit LPA and cuGraph Louvain.

Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for this purpose are crucial in various applications, particularly as datasets grow to substantial scales. This paper presents an optimized parallel implementation of the Label Propagation Algorithm (LPA), a high speed community detection method, for shared memory multicore systems. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our LPA, which we term as GVE-LPA, outperforms FLPA, igraph LPA, and NetworKit LPA by 139×, 97000×, and 40× respectively - achieving a processing rate of 1.4B edges/s on a 3.8B edge graph. In addition, GVE-LPA scales at a rate of 1.7× every doubling of threads.

Efficient IO techniques are crucial in high-performance graph processing frameworks like Gunrock and Hornet, as fast graph loading can help minimize processing time and reduce system/cloud usage charges. This research study presents approaches for efficiently reading an Edgelist from a text file and converting it to a Compressed Sparse Row (CSR) representation. On a server with dual 16-core Intel Xeon Gold 6226R processors and Seagate Exos 10e2400 HDDs, our approach, which we term as GVEL, outperforms Hornet, Gunrock, and PIGO by significant margins in CSR reading, exhibiting an average speedup of 78×, 112×, and 1.8×, respectively. For Edgelist reading, GVEL is 2.6× faster than PIGO on average, and achieves an Edgelist read rate of 1.9 billion edges/s. For every doubling of threads, GVEL improves performance at an average rate of 1.9× and 1.7× for reading Edgelist and reading CSR respectively.

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. This submission introduces our parallel approach, called LHub, which predict links using neighborhood-based similarity measures on large graphs. LHub is a heuristic approach that disregards large hubs, 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, LHub is on average 1019× faster than not disregarding hubs, especially on web graphs and social networks, while maintaining similar prediction accuracy. Notably, LHub achieves a link prediction rate of 38.1M edges/s and improves performance at a rate of 1.6× for every doubling of threads.

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 (Formula presented.) 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 (Formula presented.) 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.

Community detection is the problem of identifying natural divisions in networks. A relevant challenge in this problem is to find communities on rapidly evolving graphs. In this paper, we present our parallel Dynamic Frontier (DF) approach. Given a batch update of edge deletions or insertions, this approach incrementally identifies an approximate set of affected vertices in the graph with minimal overhead. We apply this approach to both Louvain, a high quality, and Label Propagation Algorithm (LPA), a fast static community detection algorithm. Our approach achieves a mean speedup of 7.3 × and 6.7 ×, when applied to Louvain and LPA respectively, compared to our parallel and optimized implementation of Δ-screening, a recently proposed state-of-the-art approach. Finally, we show how to combine Louvain and LPA with the DF approach to arrive at a hybrid algorithm. This algorithm produces high-quality communities while providing a speedup of 2.0 x on top of DF -based Louvain.

Community detection refers to the identification of coherent partitions in networks. In this poster, we present a parallel dynamic Louvain algorithm that finds communities in rapidly evolving graphs. Given a batch update of edge deletions or insertions, our algorithm identifies an approximate set of affected vertices in the graph with minimal overhead and updates the community membership of each vertex. This process repeats until convergence. Our approach achieves a mean speedup of 7.3 ×, compared to our parallel and optimized implementation of Δ-screening combined with Louvain, a recently proposed state-of-the-art approach.

PageRank is a widely used centrality measure that assesses the significance of vertices in a graph. Efficiently updating PageRank on dynamic graphs is essential for various applications due to the increasing scale of datasets. This paper introduces our Dynamic Frontier (DF) and Dynamic Frontier with Pruning (DF-P) approaches (https://github.com/puzzlef/pagerank-openmp-dynamic). Given a batch update comprising edge insertions and deletions, these approaches iteratively identify vertices likely to change their ranks with minimal overhead. On a server featuring a 64-core AMD EPYC-7742 processor, our approaches outperform Static and Dynamic Traversal PageRank by 5.2×/15.2× and 1.3×/3.5× respectively - on real-world dynamic graphs, and by 7.2×/9.6× and 4.0×/5.6× on large static graphs with random batch updates. Our approaches scale at a rate of 1.8×/1.7× for every doubling of threads.

Graphs, including, for example, social networks, collaboration networks, and epidemiological networks, offer a way to represent relationships among entities. Graphs arising from most real-world phenomena are not static and evolve. Dealing with such dynamic graphs requires special algorithms, known as dynamic graph algorithms, that update the required graph analytic based on the change in the current graph instead of recomputing the analytic from scratch. Parallel dynamic graph algorithms are now known for various graph problems such as connectivity, spanning trees, shortest paths, centrality metrics, and community detection. Dynamic algorithms often work in settings where a batch of edge insertions/deletions affects the current graph.

PageRank is a metric that assigns importance to the vertices of a graph based on its neighbors and their scores. Recently, there has been increasing interest in computing PageRank on dynamic graphs, where the graph structure evolves due to edge insertions and deletions. However, traditional barrier-based approaches for updating PageRanks encounter significant wait times on certain graph structures, leading to high overall runtimes. Additionally, the growing trend of multicore architectures with increased core counts has raised concerns about random thread delays and failures. In this study, we propose a lock-free algorithm for updating PageRank scores on dynamic graphs. First, we introduce our Dynamic Frontier (DF) approach, which identifies and processes vertices likely to change PageRanks with minimal overhead. Subsequently, we integrate DF with our lock-free and fault-tolerant PageRank (Alg. DFLF), incorporating a helping mechanism among threads between its two phases. Experimental results demonstrate that Alg. DFLF not only eliminates waiting times at iteration barriers but also withstands random thread delays and crashes. On average, it is 4.6× faster than lock-free Naive-dynamic PageRank (Alg. NDLF).

The design and implementation of parallel algorithms for dynamic graph problems is attracting significant research attention in the recent years, driven by numerous applications to social network analysis, neuroscience, and protein interaction networks. One such problem is the computation of PageRank values of vertices in a directed graph. This paper presents two new parallel algorithms for recomputing the PageRank values of vertices in a dynamic graph. Our techniques require the recomputation of the PageRank of only the vertices affected by the insertion/deletion of a batch of edges. We conduct detailed experimental studies of our algorithm on a set of 11 real-world graphs. Our results on Intel Xeon Silver 4116 CPU and NVIDIA Tesla V100 PCIe 16GB GPU indicate that our algorithms outperform static and dynamic update algorithms by 6.1times: and 8.6times {on} the CPU, and by 9.8×and 9.3times{on} the GPU respectively. We also compare the performance of the algorithms in batched mode to cumulative single-edge updates.