ALGORITMA K-NEAREST NEIGHBOR UNTUK MENDETEKSI CLIQUE DALAM SUATU GRAPH - Apriani, Wiwin (Jurnal Pendidikan Almuslim, 2018)
Algoritma k-nearest neighbor dapat digunakan untuk mendeteksi clique dalam suatu graf. Adapun graf yang digunakan adalah suatu graf lengkap tak berarah, berbobot, dan tidak berbobot. Untuk graf berbobot, andaikan diberikan suatu graf lengkap G = (V,E) dengan wij merupakan bobot pada tiap edge (i,j). Sehingga untuk mendeteksi clique dalam graf berbobot dapat menggunakan nilai jarak euclidean pada masing-masing verteks yang saling bertetanggaan. Adapun tujuannya mendeteksi clique dengan jumlah bobot maksimum. Selain itu, untuk permasalahan graf tidak berbobot, pencarian clique dapat menggunakan nilai bilangan biner. Jika ViVj ≠ 0, berarti bahwa verteks i dan verteks j saling terhubung dan dapat dimasukkan kedalam clique. Akan tetapi, jika ViVj = 0, berarti bahwa verteks i dan verteks j tidak saling terhubung, sehingga verteks yang tidak terhubung tersebut tidak termasuk kedalam clique dan dapat diabaikan. Tujuan mendeteksi clique pada graf tak berbobot adalah memperoleh maksimum clique. Kata kunci: Algoritma K-nearest neighbor, Clique, Graf berbobot, Graf tak berbobot