Considering the diversity and coverage of graph algorithms, 4 different types of algorithms are selected. Diversity means that all the graph applications should have different execution behavior, and coverage means that the implementation for each graph application should be representative.

Weakly Connected Components(WCC)

A weakly connected component is a subgraph of the original directed graph while all the vertices are connected in some path without counting the direction. The goal of this application is to identify each weakly connected component in a directed graph.  the implementations we choose for our WCC kernel are label propagation and the Shiloach-Vishkin (SV) algorithm as shown in figure above.

ArticleRank(AR)

ArticleRank ranks the influence of a paper in the citation network by assuming the influence of a paper is determined by how many papers cite it and the number of references that the cited paper had. A paper has a large ArticleRank score means it has a larger influence on the citation network. The formula for calculating the ArticleRank of each node is shown in figure above.

Betweenness Centrality(BC)

Between centrality scores can be defined as a measurement of the importance of each node regarding the connection of our graphs. Based on the traversal from each node throughout the graph, the ensemble of shortest path through each node can be determined, and then normalize to a score between [0,1]. For betweenness centrality, Brandes algorithm are selected to compute the BC score.

Graph Coloring(GC)

Graph coloring problem is a very famous problem that asks people to assign colors to certain elements inside a graph subject under specified constraints, but in this kernel, we mainly deal with vertex coloring problems subject to the constraint that a node has to be in different color compared with its neighbors. Thus, the greedy algorithm is used to solve this problem in a brute force way.