Heuristic algorithm for extracting a subset of maximal cliques inside graphs

Authors: Trịnh Anh Phúc*, Đinh Viết Sang

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.

Keyword

Maximal cliques, Graph mining, Heuristic algorithms, Apriori Algorithm
Pages : 54-58

Related Articles:

Authors : Nguyen Hoang Minh Vu*, Vo Viet Cuong, Phan Thi Thanh Binh
Authors : nguyen thi hue*, đỗ quang huy, trần mạnh hà, hoàng sĩ hồng