Abstract

Centrality measures offer a mechanism to quantify various notions of the importance of vertices in a network. These measures find application in social network analysis, the study of disease spread, and the like. Since the networks of interest are usually large, parallelism has become a powerful tool for computing these measures. However, for some of these applications, it is crucial to study how these centrality values change when there are changes to the underlying network. As a result, parallel algorithms that examine how to update these values due to changes to the graph are gaining research interest. In this paper, we study the update of the percolation centrality measure in a dynamic graph. We present parallel algorithms to handle changes to the percolation value of a batch of vertices and the addition and deletion of a batch of edges to the graph. We leverage the graphs' structural properties to improve our algorithms' performance. To our knowledge, we are the first to propose such algorithms for percolation centrality. We implement and benchmark our dynamic algorithms on a server with two AMD EPYC CPUs and an Nvidia A100 GPU. Our experiments on a collection of real-world graphs indicate that our algorithms achieve speedups of 8.79x and 2.82x on CPU and GPU, respectively, for edge updates, and 309.44x and 18.71x on CPU and GPU, respectively, for vertex percolation updates over state-of-the-art static algorithms for a batch of 10000 edges and vertices, respectively.

Abstract

Efficient algorithms for graph connected components and minimum spanning tree (MST) computations are vital in diverse domains, from medical diagnostics to chip design. Yet, as graph sizes grow to billions of edges, existing approaches often fail due to limited device memory. This challenge demands innovative rethinking of both algorithmic design and implementation strategies. We address this need by presenting a novel Parallel Heterogeneous External Memory (PHEM) framework, which harnesses both multicore CPU and GPU resources to tackle large-scale graph processing. Our method minimizes communication overhead while maximizing computational throughput through efficient copy- computation strategies. Experiments on a variety of real-world and synthetic benchmarks demonstrate that our algorithms for connected components and minimum spanning tree in the PHEM model outperform current state-of-the-art solutions, significantly advancing the capability to process massive graphs.

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. 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 1019x 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.6x for every doubling of threads.

Abstract

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 78x, 112x, and 1.8x, respectively. For Edgelist reading, GVEL is 2.6x 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.9x and 1.7x for reading Edgelist and reading CSR respectively.

Abstract

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 139x, 97000x, and 40x 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.7x every doubling of threads.

Abstract

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 design efficient community detection algorithms in the batch dynamic setting. First, we present our parallel Dynamic Frontier 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 Dynamic Frontier approach to arrive at a hybrid algorithm. This algorithm produces high-quality communities while being 14.6× faster than state-of-the-art, and identifying communities with the same quality score.

Abstract

In this paper, we present a deterministic -round algorithm for the 2-ruling set problem in the sublinear Massively Parallel Computation (MPC) model. This improves upon the fastest known deterministic 2-ruling set algorithm for this model, which is the -round algorithm by Giliberti and Parsaeian (PODC 2024). Our result is obtained by derandomizing the “sample-and-gather” approach of Kothapalli, Pai, and Pemmaraju (FSTTCS 2020). The “sample-and-gather” approach involves making random sampling decisions, not just for the current iteration, but a batch of future iterations. Thus, derandomizing this approach requires the “fixing” of randomness for a batch of future iterations. We further extend our results to show that a β -ruling set for β ≥ 2 can be obtained in deterministic rounds in the sublinear MPC model. Additionally, we present a deterministic β -ruling set algorithms for sparse graphs (i.e., bounded arboricity graphs) where β ≥ 2, which runs in rounds for arboricity-λ graphs in the sublinear MPC model

Abstract

The present disclosure provides a system and a method for generating a secure digital certificate for a user using cryptographic hashing and storing the digital certificate on a smart contract by a decentralized blockchain. The method includes (i) generating a registration token for a first user using the cryptographic hashing,(ii) storing the registration token of the first user as a second hash in the smart contract,(iii) receiving digital request through the first user device,(iv) validating (a) the digital request of the first user by (m) authenticating whether the biometrics of the first user, and (n) checking whether the second hash exists in the decentralized blockchain, and (b) the second user associated with a second user device using a driver algorithm,(v) sending a message to the second user device to initiate the digital request and (vi) generating the digital certificate when the first user receives a verification.

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 1019x 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 1.6x for every doubling of threads.

Abstract

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.