TY - GEN

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

AU - Antoro, S. C.

AU - Ariyanti, Kiki

AU - Handari, Bevina Desjwiandra

PY - 2017/7/10

Y1 - 2017/7/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85026263293&partnerID=8YFLogxK

U2 - 10.1063/1.4991245

DO - 10.1063/1.4991245

M3 - Conference contribution

AN - SCOPUS:85026263293

T3 - AIP Conference Proceedings

BT - International Symposium on Current Progress in Mathematics and Sciences 2016, ISCPMS 2016

A2 - Sugeng, Kiki Ariyanti

A2 - Triyono, Djoko

A2 - Mart, Terry

PB - American Institute of Physics Inc.

T2 - 2nd International Symposium on Current Progress in Mathematics and Sciences 2016, ISCPMS 2016

Y2 - 1 November 2016 through 2 November 2016

ER -