SCC (SmallWorld Optimized)
In addition to the regular strongly connected component algorithm, we also provide a version that is optimized for smallworld graphs. A smallworld graph in this context means the graph has a hub community, where a vast majority of the vertices of the graph are weakly connected.
This version improves upon the performance of the original algorithm when dealing with smallworld graphs by combining several different methods used to find connected components in a multistep process proposed by Slota et al. in BFS and Coloringbased Parallel Algorithms for Strongly Connected Components and Related Problems.
The algorithm starts by trimming the graph, which removes all vertices whose indegree or outdegree is 0. In the second phase, the algorithm selects an initial pivot vertex v with a high product of indegree and outdegree.
From the initial pivot vertex , the algorithm uses one iteration of the ForwardBackward method to identify all vertices reachable by v (descendants) and all vertices that can reach v (predecessors). The intersection of the descendants and the predecessors form a strongly connected component (SCC). The vertices that are not included in this SCC are passed off to the next step.
After identifying the first SCC, the algorithm uses the coloring method and Tarjan’s serial algorithm to identify the SCCs in the remaining vertices.
Parameters
Name  Description  Data type 


The vertex type to count as part of a strongly connected component 


The edge type to traverse 


The reverse edge type to traverse. If the graph is
undirected, fill in the name of the undirected edge here as well as for



The threshold used to choose initial pivot vertices. Only vertices whose product of indegree and outdegree exceed this threshold will be considered candidates for the pivot vertex. This is an attempt to increase the chances that the initial pivot is contained within the largest SCC. The default value for this parameter is 100000. It is suggested that you keep this default value when running the algorithm. 


If set to 

Result
When to_show_cc_count
is set to true
, the algorithm will return the
number of strongly connected components in the graph.