Application of Bron-Kerbosch algorithm in graph clustering using complement matrix

Maximal clique enumeration is a graph clustering method for finding all vertices that have the most influence in a graph. The Bron-Kerbosch algorithm is one of the fastest algorithms to find all maximal cliques. Hence, this paper will focus on that algorithm to find all maximal cliques. Counting all maximal cliques of a graph usually uses an adjacency matrix of the graph to find all vertices in the graph that have the most influence. But, in this paper, a complement matrix of a graph will be used in counting all maximal cliques. This research uses a graph that represents a domestic flight route of one of the airlines in Indonesia. By using Bron-Kerbosch algorithm, all maximal cliques of the graph will be listed, so that it will come up with the vertices which are the most influential in this graph. The graph will be represented in complement matrix. The result of applying the Bron-Kerbosch algorithm with the complement matrix of graph will determine vertices that have the most influence in the graph. Besides that, by using a complement matrix, the result gives more information on the vertices which are only connected to the vertices that have the most influence.