Analisa Dan Implementasi Graph Summarization Dengan Metode Canal

Abstract

Abstract— Pemodelan data menggunakan graph telah diterapkan oleh banyak aplikasi dan sistem berskala besar dalam berbagai bidang. Data tersebut direpresentasikan sebagai graph dengan node yang mewakili sebuah objek dan edge menandakan hubungan antara dua objek. Untuk memahami karakteristik graph, maka dibutuhkan teknik graph summarization.
Pada penelitian ini digunakan metode CANAL (Categorization of Attributes with Numerical Values based on Attribute Values and Link Structures of Nodes) untuk meringkas graph. Metode ini merupakan pengembangan dari metode Aggregation-Based Graph Summarization yang melakukan peringkasan dengan mengelompokkan serta menggabung node kedalam sebuah super node kemudian mengggali pengetahuan dari data untuk menemukan cutoff yang digunakan dalam pengelompokan node secara otomatis. Metode CANAL memperbaiki metode graph summarization SNAP dan k-SNAP yang masih mempunyai kelemahan dalam menangani data dengan atribut numerik[2]. Kedua metode tersebut hanya dapat menangani categorical node attribute, sehingga ketika dihadapkan dengan atribut numerik pengguna masih harus melakukan pengelompokan secara manual berdasarkan pengetahuan mereka terhadap data yang digunakan.

Hasil dari sistem yang akan dibangun merupakan sebuah graph summary yang merepresentasikan pattern hubungan antar kelompok dalam ringkasan. Pattern tersebut dapat digunakan untuk membantu memahami informasi yang tersembunyi didalam graph asli. Dari summary yang dihasilkan oleh metode CANAL kemudian dinilai kualitasnya dan dibandingkan dengan kualitas summary dengan cutoff manual. Perbandingan tersebut menunjukkan bahwa kualitas summary dari CANAL memiliki kualitas baik yang setara dengan kualitas summary dengan cutoff manual.
Keywords—graph summarization, Aggregation-Based Graph Summarization, node attribute, link structure, interestingness measure.