Februari 2006


Sambungan dari Survey Link Mining (3).
Lanjut ke Graph-Related Tasks. Yang termasuk dalam Graph-Related Tasks adalah subgraph discovery, graph classification, dan generative models for graphs. Task ini fokus pada keseluruhan graph. Berikut ini akan dibahas task-task yang termasuk dalam Graph-Related Tasks.

  • Subgraph Discovery
  • Task ini mencari subgraph yang “menarik” dan sering muncul pada sebuah kumpulan graph. Subgraph adalah graph yang merupakan bagian dari sebuah graph. Beberapa pendekatan untuk task ini dilakukan dengan mencari frequent subgraph terlebih dahulu. Hasil dari task ini dapat juga digunakan untuk graph classification.

  • Graph Classification
  • Berbeda dengan Link-based Object Classification yang melakukan klasifikasi pada node-node dalam graph, Graph Classification melakukan klasifikasi pada keseluruhan graph. Ada tiga pendekatan yang sudah dikembangkan untuk graph classification yaitu berdasarkan feature mining pada graph, Inductive Logic Programming (ILP), dan menggunakan graph kernel.

  • Generative Models for Graphs
  • Task ini telah banyak dipelajari dalam social network analysis (SNA). Saat ini tidak hanya pada SNA, namun juga pada www, online social network, communication network, citation network, dan biological network. Tujuan task ini adalah sebuah model yang dapat digunakan untuk graph generator.

Link mining termasuk salah satu bidang data mining yang berkembang pesat. Banyak hal dalam link mining masih terbuka lebar untuk penelitian lebih lanjut mulai dari teknik preprocessing data, incremental classification sampai semantic web.
Semoga dengan review singkat ini dapat memberikan gambaran tentang link mining.

Menyambung Survey Link Mining (2), sekarang kita beralih ke Edge-Related Tasks. Titik beratnya adalah link-link yang menghubungkan antar object. Yang termasuk dalam Edge-Related Tasks adalah link prediction.
Permasalahan Link prediction adalah melakukan prediksi adanya sebuah link (hubungan) antar dua object berdasarkan attribute object dan link yang lainnya. Contohnya meliputi prediksi hubungan antar anggota dalam social network (prediksi friendship), prediksi keterlibatan seseorang dalam suatu event.
Umumnya pada link prediction, link-link yang sudah ada digunakan untuk memprediksi adanya link-link baru.
Kesulitan dan tantangannya di sini adalah banyak linked data yang “menarik” sifatnya sparse. Hal ini karena dalam sebuah graph, sebuah object umumnya hanya berhubungan dengan sebagian kecil object dari keseluruhan object yang ada dalam graph.
Bersambung ke Survey Link Mining (4).

Sambungan dari Survey Link Mining (1).
Object-Related Tasks fokus pada object (node) dalam sebuah graph. Jadi, yang menjadi pusat perhatian task-task yang berada di Object-Related Tasks adalah object dalam sebuah graph. Berikut ini akan dibahas task-task yang termasuk dalam Object-Related Tasks.

  • Link-Based Object Ranking
  • Link-based Object Ranking (LBR) merupakan merupakan salah satu task yang paling dikenal dalam link mining. Tujuannya adalah melakukan ranking object berdasarkan hubungan antar object (link) dalam sebuah graph. Misalnya ranking web page, ranking individu dalam sebuah social network. Saat ini, umumnya LBR dilakukan pada sebuah graph yang static. Melakukan LBR pada sebuah graph yang dinamis merupakan tantangan baru dari task ini

  • Link-Based Object Classification
  • Link-Based Object Classification (LBC) melakukan klasifikasi object pada sebuah graph. Berbeda dengan klasifikasi data pada umumnya, LBC melakukan klasifikasi pada object-object yang saling berkorelasi. Hubungan korelasi ini juga diperhitungkan dalam membentuk sebuah model klasifikasi.

  • Object Clustering (Group Detection)
  • Tujuan Group Detection adalah mengelompokkan object-object pada sebuah graph. Object-Object yang berada dalam sebuah kelompok akan memiliki karakteristik yang mirip. Misalnya pengelompokkan individu pada social network. Setiap individu dalam sebuah kelompok akan memiliki kemiripan hubungan dalam social network.

  • Object Identification (Entity Resolution)
  • Entity Resolution mengidentifikasi object-object pada suatu domain. Tujuan Entity Resolution adalah menentukan data-data yang referensinya mengarah pada entity real-world yang sama. Misalnya mencari deduplication pada database. Permasalahan ini dapat ditemui dalam bidang database (deduplication, data integration), natural language processing (co-reference), personal information management, dan lain-lain.

Bersambung ke Survey Link Mining (3).