tailieunhanh - Heuristic algorithm for extracting a subset of maximal cliques inside graphs

This problem is considered as a NP-complete problem. In this work, we propose a heuristic algorithm that treats the above problem. In our algorithm, undirected graph is represented using the adjacency-list. Next, this representation is transformed into a new form so-called transaction database that is very familiar in data mining domain. Based on the new representation, we are able to count the frequency of subset of vertices inside undirected graph which is used to extract a set of maximal candidates that become possibly maximal cliques. | Journal of Science & Technology 123 (2017) 054-058 Heuristic Algorithm for Extracting a Subset of Maximal Cliques Inside Graphs Trinh Anh Phuc*, Dinh Viet Sang Hanoi University of Science and Technology, No. 1, Dai Co Viet, Hai Ba Trung, Hanoi, Viet Nam Received: May 26, 2017; Accepted: November 03, 2017 Abstract We investigate the problem of extracting a subset of maximal cliques inside an undirected graph. This problem is considered as a NP-complete problem. In this work, we propose a heuristic algorithm that treats the above problem. In our algorithm, undirected graph is represented using the adjacency-list. Next, this representation is transformed into a new form so-called transaction database that is very familiar in data mining domain. Based on the new representation, we are able to count the frequency of subset of vertices inside undirected graph which is used to extract a set of maximal candidates that become possibly maximal cliques. Our experimental results show that this algorithm maintains a reasonable threshold in order to control its complexity. Keywords: Maximal cliques, Graph mining, Heuristic algorithms, Apriori Algorithm 1. Introduction * in graph theory (see some examples in Figure 1). Finding the complete list of all maximal cliques of a graph requires the algorithms with exponential complexity [10-14]. However, we need sometimes answer a question, given a certain graph, if we conduct a limited subset of listing maximal cliques inside the graph then a proposal algorithm will reduce possibly its time complexity requirement. In recent years, applications of graph mining get more and more interested by the datamining community. There are several reasons to explain these rising interests. Firstly, the graph seems a flexible way to represent visually many real-world problems. Secondly, graphs contain NP-problems that made more challenges to scientists. Among the graph NP-problems [1], we decide to choose the problem of extracting maximal cliques