<p><a href="http://jshun.github.io/ligra/" rel="nofollow noreferrer">Ligra</a> is either the state of the art or close to it for single-machine multicore implementations. It should be able to handle your graph no problem.</p>

<p><a href="https://arxiv.org/pdf/1807.10727.pdf" rel="nofollow noreferrer">Connected Components at Scale via Local
Contractions</a>, by my colleagues Jakub Łącki, Vahab Mirrokni, and Michał Włodarczyk, is the state of the art (at least, that I know about) for MapReduce algorithms. We've used it on graphs a thousand times bigger than yours.</p>
Parallel algorithm for connected components
<p>I have to find the best algorithm from already known for parallel computing of connected components of graph.</p>

<p>Here is a brief outline of my data and computer architecture:</p>

<ul>
<li>I have access to a computational cluster with several thousands of
processors (memory is not shared, but I expect that there should be
enough memory in a single node to assess my needs for the whole
data).</li>
<li>my graph has rather small ratio of edges number to vertices number (about 5)</li>
<li>I expect the most of connected components to be very small (2-3 vertices)</li>
<li>there will be, however, very big components with millions of vertices (constituting even up to 10% of total vertices number).</li>
</ul>

<p>I have read about parallel algorithms for computing connected components of graphs. As I have noticed, some of them base on the classical BFS approach for the serialized case. To be honest, I got a bit lost in the number of these algorithms. Could anyone give me some advice, which algorithm would be the best for my purposes?</p>