ALGORITMA K-NEAREST NEIGHBOR UNTUK MENDETEKSI CLIQUE DALAM SUATU GRAPH
Abstract
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
References
Brualdi, R.A., dan Ryser H.J. (1991). Combinatorial Matrix Theory. Cambridge University Press, Cambridge.
Chopra, S. dan Rao, M. R. (1991). On the multiway cut polyhedron. Networks 21, 51-89
Chopra, S. dan Rao, M. R. (1993). The partition problem. Mathematical programming 59, 87-116.
Cavique, L., Rego. dan Themido, I. (2002). A Scatter Search Algorithm for Maximum Clique Problem. in:Essays and Surveys in Metahauristics. Kluwer Academic Publishers. 227-244
Gorunescu, F. (2011) Data Mining: Concepts, Models and Techniques. Springer.
Grotschel, M. dan Wakabayashi, Y. (1989). A cutting plane algorithm for a clustering problem. Mathematical Programming Series B 45, 59-96.
Mehrotra, A.,dan Trick, A. M. (1998). Cliques and clustering: A combinatorial approach. Elsevier. Operation Research letters 1-12
Palla, G., Derenyi, I., Farkas, I., dan Vicsek, T. (2005). Uncovering to overlappingcommunity structure of complex network in nature and society. Nature 435 (70043): 814-818
Regneri, M. (2007). Finding all cliques of an undirected graph. Current trends in IE WS 06/07
