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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationInternational Symposium on Current Progress in Mathematics and Sciences 2016, ISCPMS 2016
Subtitle of host publicationProceedings of the 2nd International Symposium on Current Progress in Mathematics and Sciences 2016
EditorsKiki Ariyanti Sugeng, Djoko Triyono, Terry Mart
PublisherAmerican Institute of Physics Inc.
ISBN (Electronic)9780735415362
DOIs
Publication statusPublished - 10 Jul 2017
Event2nd International Symposium on Current Progress in Mathematics and Sciences 2016, ISCPMS 2016 - Depok, Jawa Barat, Indonesia
Duration: 1 Nov 20162 Nov 2016

Publication series

NameAIP Conference Proceedings
Volume1862
ISSN (Print)0094-243X
ISSN (Electronic)1551-7616

Conference

Conference2nd International Symposium on Current Progress in Mathematics and Sciences 2016, ISCPMS 2016
CountryIndonesia
CityDepok, Jawa Barat
Period1/11/162/11/16

Fingerprint Dive into the research topics of 'Application of Bron-Kerbosch algorithm in graph clustering using complement matrix'. Together they form a unique fingerprint.

Cite this