Efficient Parallelization of Global Graph Measures on Multicore Shared Memory Systems

Exploring the structural and functional properties of real-world large graphs, such as detecting community structure in social networks and assessing the connectivity of different brain regions in brain graphs, is an increasingly prominent research area. Quantitative graph theory has been developed to quantify both structural and functional aspects of graphs. Typically, nodal and global graph measures are employed to estimate the information content of a graph. There is currently a pronounced interest in parallel graph processing, driven by the imperative to quickly analyze the large graphs available today. Modern desktop and laptop computers are equipped with multicore processors featuring shared memory architecture. The utilization of the OpenMP API offers numerous advantages for shared memory systems. In this study, parallel algorithms for four global graph measures have been designed and implemented on multicore shared memory systems using both task-centric and data-centric parallel techniques. We assess performance across varying numbers of cores and for different sizes of random graphs, as well as numerous real brain graphs, comparing the results against serial algorithms within the same hardware environment. Experimental results demonstrate a significant enhancement in the parallel algorithms across multiple cores, effectively meeting the demand for accelerated computation of graph measures.