An Empirical Study on the Significance of Node Ordering for Computing Cliques using Map Reduce

Abstract

Counting the number of cliques in large-scale graphs is a significant problem in graph mining and data mining research communities. Motivated by several studies and applications in the graphs, we revisit the design aspect of some algorithms that compute cliques. We investigate the importance of node order in the context of computing cliques, which benefits several real-world applications. In our work, we develop some scalable distributed algorithms considering the sparsity of a graph for computing cliques. We highlight the merits and demerits of the aforementioned studies that count and list all the cliques in a graph. We compare the best performances in small and large real-world graphs. We highlight the need for careful design to minimize the communication cost involved in computing cliques. We analyze the start-of-the-art methods that consider an order in finding the number of cliques in a graph and establish the significance of order. With extensive experimentation, we show crucial findings on both synthetic and real-world datasets. Our observations and research results significantly benefit the current trending industrial applications using big data.