Hasil Pencarian  ::  Simpan CSV :: Kembali

Abstrak :
Pencacahan clique maksimal adalah suatu metode graph clustering yang bertujuan untuk mencari simpul mana saja yang memiliki peranan paling besar dalam suatu graf. Pencacahan clique maksimal ini telah banyak diaplikasikan, diantaranya analisis pada jaringan sosial, pendeteksian hierarki melalui jaringan email, analisis statistik jaringan finansial, clustering pada jaringan dinamis, dan komputasi biologi. Algoritma Bron-Kerbosch merupakan salah satu algoritma tercepat dalam pencarian clique maksimal, maka pada penelitian ini, digunakanlah algoritma Bron-Kerbosch. Dalam mencacah semua clique maksimal dari suatu graf, matriks yang biasa digunakan adalah matriks ketetanggaan dari graf tersebut, sehingga dapat diperoleh simpul mana saja pada graf yang memiliki peranan paling besar. Selain matriks ketetanggaan, penelitian ini juga menggunakan matriks komplemen dalam mencacah clique maksimal. Data yang digunakan dalam penelitian ini adalah graf yang merepresentasikan rute jalur penerbangan domestik dari salah satu maskapai penerbangan di Indonesia. Dengan menerapkan algoritma Bron-Kerbosch, semua clique maksimal dari graf terkait akan didaftar, sehingga dapat diperoleh simpul yang memiliki peranan paling besar dalam graf ini. Graf tersebut direpresentasikan dalam bentuk matriks ketetanggaan dan juga matriks komplemen. Hasil penerapan algoritma Bron-Kerbosch pada data, baik yang menggunakan matriks ketetanggaan maupun matriks komplemen, keduanya memberikan hasil yang sama dalam menentukan simpul yang memiliki peranan paling besar dari graf terkait. Selain itu, melalui hasil penerapan yang menggunakan matriks komplemen, dapat diketahui pula simpul-simpul yang hanya bertetangga langsung dengan simpul yang memiliki peranan paling besar.

---

Maximal clique enumeration is a graph clustering method for finding all vertices that have the most influence in a graph. This maximal clique enumeration has largely been applied, including social network analysis, hierarchy detection through email networks, statistical analysis of financial networks, clustering in dynamic networks, and computational biology. The Bron-Kerbosch algorithm is one of the fastest algorithms to find all maximal cliques, hence this research 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. Other than adjacency matrix, this research will also use a complement matrix 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 an adjacency matrix as well as a complement matrix. The result of applying the Bron-Kerbosch algorithm both the adjacency and the complement matrix?will give the same result in determining 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.

Abstrak :
Pengklasteran clustering yang dilakukan dengan menggunakan metode graf disebut dengan pengklasteran graf graph clustering . Pengklasteran graf dengan memperhatikan bobot dapat diselesaikan dengan menggunakan pohon rentangan minimum. Salah satu algoritma yang dapat digunakan untuk menyelesaikan pengklasteran graf berbobot berdasarkan pohon rentangan minimum adalah algoritma maximum standard deviation reduction MSDR . Pada algoritma MSDR tidak perlu ditentukan banyaknya klaster yang terbentuk, karena terdapat perhitungan untuk menentukan banyak klaster secara otomatis. Namun dalam penelitian lanjutan algoritma MSDR cukup sulit dikerjakan karena sulitnya dalam menentukan nilai kandidat klaster terbaik, sehingga dilakukan modifikasi untuk menentukan nilai -nya. Modifikasi ini disebut dengan modifikasi MSDR MMSDR. Penelitian ini merupakan implementasi dari algoritma MMSDR pada masalah rute penerbangan di Indonesia yang disebut maskapai X, dengan menggunakan input matriks komplemen. Dengan menggunakan input matriks dari komplemen graf didapatkan pengklasteran berdasarkan jarak antar bandara. Penelitian ini juga menganalisis perubahan nilai epsilon dan perubahan matriks input. Hasil analisis menunjukkan bahwa perubahan nilai epsilon tidak mempengaruhi banyaknya klaster dan anggota klaster, sedangkan perubahan matriks input dapat mempengaruhi perbedaan anggota klaster. ...... Clustering is done by using graph method called graph clustering. Graph clustering with weights can be solved by using a minimum spanning tree. One of the algorithms that can be used to complete a weighted graph clustering based on a minimum spanning tree is the maximum standard deviation reduction MSDR algorithm. In the MSDR algorithm there is no need to determine the number of clusters that are formed, because there are calculaions to determine many clusters automically. However, in advanced research MSDR algorithm is quite difficult to do because of the difficulty in determining the value of best cluster candidates, so modifications are made to determine the value of. This modification is called the modification MSDR MMSDR. This research is an implementation of MMSDR algorithm on flight route problem in Indonesia called airline X, by using input complement matrix. Using the matrix input from the complement graph obtained clustering based on the distance between airports. This research also analyzed changes in epsilon value and changes in input matrix. The results of the analysis show that the change in epsilon value does not affect the number of clusters and clusters members, whereas the change in input matrix may affect the cluster members.