Algoritma pengelompokan grafik yang efisien

20

Saya mencari algoritma yang efisien untuk menemukan cluster pada grafik besar (Ini memiliki sekitar 5.000 simpul dan 10000 tepi).

Sejauh ini saya menggunakan algoritma Girvan-Newman diimplementasikan di perpustakaan java JUNG tetapi cukup lambat ketika saya mencoba untuk menghapus banyak tepi.

Bisakah Anda menyarankan saya alternatif yang lebih baik untuk grafik besar?

algorithms graph cluster mariosangiorgio
sumber
Sudahkah Anda melihat k-means?
Oded
Bisakah Anda memberi saya beberapa referensi untuk belajar tentang cara menggunakannya pada grafik?
mariosangiorgio
en.wikipedia.org/wiki/K-means_clustering
Oded
Saya beralih ke implementasi JUNG dari VoltageClusterer dan sudah pasti cepat. jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/…
mariosangiorgio
1
Bukankah ini lebih cocok untuk < cs.stackexchange.com > karena ini lebih tentang ilmu komputer daripada insinyur perangkat lunak?
Oeufcoque Penteano

Jawaban:

13

Saya pribadi menyarankan pengelompokan Markov . Saya telah menggunakannya beberapa kali di masa lalu dengan hasil yang baik.

Perambatan afinitas adalah pilihan lain yang layak, tetapi tampaknya kurang konsisten daripada pengelompokan Markov.

Ada berbagai pilihan lain, tetapi keduanya bagus di luar kotak dan cocok untuk masalah khusus pengelompokan grafik (yang dapat Anda lihat sebagai matriks jarang). Ukuran jarak yang Anda gunakan juga merupakan pertimbangan. Hidup Anda akan lebih mudah jika Anda menggunakan metrik yang tepat.

Saya menemukan makalah ini sambil mencari tolok ukur kinerja, itu adalah survei yang baik dari subjek.

Nathan Rice
sumber
Terima kasih, saya akan melihat semua algoritma yang Anda sarankan.
mariosangiorgio
Koreksi: algoritma ini perlu sebagai bobot input yang mencerminkan kesamaan, bukan jarak. Properti metrik (ketimpangan segitiga) tidak masuk ke dalamnya. Dapat bermanfaat untuk mengubah bobot sehingga berada dalam kisaran alami, misalnya untuk korelasi (Pearson) seperti yang dijelaskan di sini ( micans.org/mcl/man/clmprotocols.html#array ), dan untuk nilai-nilai BLAST E seperti yang dijelaskan di sini ( micans.org/mcl/man/clmprotocols.html#blast ).
micans
10

Clustering Hirarkis

Ini direkomendasikan kepada saya oleh seorang teman. Menurut Wikipedia :

Dalam metode ini kita mendefinisikan ukuran kesamaan mengukur beberapa jenis kesamaan (biasanya topologi) antara pasangan node. Ukuran yang umum digunakan termasuk kesamaan cosinus, indeks Jaccard, dan jarak Hamming antara baris matriks adjacency. Kemudian satu kelompok simpul yang mirip ke dalam komunitas sesuai dengan ukuran ini. Ada beberapa skema umum untuk melakukan pengelompokan, dua yang paling sederhana adalah pengelompokan hubungan tunggal, di mana dua kelompok dianggap sebagai komunitas yang terpisah jika dan hanya jika semua pasangan node dalam kelompok yang berbeda memiliki kesamaan lebih rendah dari ambang yang diberikan, dan pengelompokan tautan lengkap , di mana semua node dalam setiap grup memiliki kesamaan lebih besar dari ambang batas.

Markov Cluster

Inilah yang saya gunakan dalam situasi Anda. Ini adalah algoritma yang sangat berguna. Saya menemukan tautan ke PDF yang bagus tentang Algoritma. Ini adalah algoritma yang hebat, dan, karena tidak ada istilah yang lebih baik, sangat "kuat". Cobalah dan lihat.

Dinamis
sumber
5

Untuk masalah Anda di sini, saya pikir Anda harus memikirkan cara untuk memetakan titik-tepi ke satu set koordinat untuk setiap titik. Saya tidak yakin apakah ada cara yang lebih baik untuk melakukan ini. Tapi, saya pikir Anda bisa memulai dengan mewakili setiap titik sebagai dimensi dan kemudian, nilai tepi ke titik tertentu akan menjadi nilai yang Anda perlukan untuk dimensi itu. Setelah itu Anda bisa melakukan jarak Euclid sederhana dan bekerja dengannya.

viki.omega9
sumber
1
Setelah membaca sedikit, saya menemukan ini, di sini dan saya pikir Anda harus melihatnya.
viki.omega9