Parallelization of special graph algorithms on GPU cluster

Abstract

A social graph is a plot that illustrates interconnections among people, group and organizations in a social network. Each user is represented by a vertex and connection between two users is represented by an edge. In the social sciences, a clique is a group of people who interact with each other and such cliques are contained in social graphs in large numbers. Applications of cliques searching have been widespread in searching for highly connected communities, graph clustering, network traffic analysis and more. Cliques’ problem is a hard problem in computer science. Bron-kerbosch is an algorithm, which can be used for searching cliques in a graph. The algorithm is used to search cliques in a social graph and a lower running time is expected relative to a dense graph. The objective of the work is to check whether betweenness-centrality property and edge distribution property of social graphs can be used to search cliques efficiently, because of the sparseness of social graphs. Bron-kerbosch algorithm can be formed in a parallelized way, so that it can be run on multi core CPU, GPU and GPU cluster to get better performance. Finally, the parallelized bron-kerbosch algorithm is launched on selected vertices and edges, considering both betweenness-centrality and edge distribution properties. A GPU cluster as expected performed better than a single GPU. A GPU is better for large social graphs than a CPU. However, launching from selected vertices and edges have not contributed significantly to an improvement in result when considering the percentage of total number of cliques in particular social graphs.