Algoritma pengelompokan grafik yang mempertimbangkan bobot negatif

8

Saya memiliki instance grafik dengan tepi terarah tertimbang yang nilainya dapat berada dalam kisaran [-1,1]. Saya perlu melakukan pengelompokan pada grafik ini, untuk mengetahui kelompok-kelompok di mana simpul lebih berkorelasi.

Saya mencari beberapa algoritma berbasis pengelompokan atau deteksi komunitas grafik, tetapi kebanyakan dari mereka tidak bekerja karena bobot negatif. Sampai sekarang saya telah menerapkan spinglass (disebut dalam perpustakaan igraph , ini adalah algoritma yang didasarkan pada model Potts) yang tampaknya bekerja dengan bobot positif dan negatif.

Apakah ada algoritma lain untuk melakukan pengelompokan atau deteksi komunitas pada grafik yang memiliki bobot tepi negatif dan positif?

Pembaruan: bobot tepi mewakili korelasi, 1 berarti dua simpul berkorelasi kuat, -1 yang berkorelasi terbalik dan 0 berarti independen.

correlation clustering graph-theory networks igraph Ebe
sumber
Apa yang diwakili oleh bobot?
eliasah
@eliasah Saya melakukan pembaruan untuk menjelaskan itu
Ewybe
Apakah Anda mencoba menggunakan skala lain? Itu mungkin solusi yang baik dengan menggunakan metode pengelompokan biasa berdasarkan pada algoritma centrality betweenness per contoh.
eliasah
@eliasah Melakukan penskalaan data ini agar tidak mudah karena saya tertarik untuk melestarikan makna korelasinya
Ewybe
1
Untuk pengelompokan, apakah tanda korelasi benar-benar diperlukan? Korelasi terbalik adalah hubungan yang cukup kuat juga. Lihat jawaban saya di bawah ini.
Memiliki QUIT - Anony-Mousse

Jawaban:

2

Sudahkah Anda mencoba memetakan nilai ke [0; 2]?

Maka banyak algoritma dapat bekerja.

Pertimbangkan misalnya Dijkstra: ini membutuhkan bobot tepi non-negatif, tetapi jika Anda tahu batas minimumnya a, Anda bisa menjalankannya x-adan mendapatkan jalur bebas siklus terpendek.

Pembaruan: untuk nilai korelasi, Anda mungkin tertarik pada nilai absolut abs(x)(yang merupakan kekuatan korelasi!) Atau Anda mungkin ingin memecah grafik menjadi dua untuk sementara: pertama cluster hanya pada korelasi positif, kemudian pada korelasi negatif hanya jika tandanya penting untuk pengelompokan & pendekatan sebelumnya tidak berfungsi.

Memiliki QUIT - Anony-Mousse
sumber
Entah bagaimana itu yang saya sarankan, dia berkata bahwa dia akan "kehilangan arti korelasinya". Apa pendapatmu tentang itu?
eliasah
Dengan deskripsinya yang diperbarui, abs (x) dapat bekerja lebih baik.
Memiliki QUIT - Anony-Mousse
Meskipun demikian saya percaya [0,2] lebih representatif. Grafik berbobot biasanya memiliki kepentingan yang sangat besar dalam hal ini untuk menghitung sentralitas, jarak, diameter, dll.
eliasah
1
Itu tidak berarti Anda tidak dapat mendiskriminasi sesudahnya. Sudahkah Anda mencobanya , hasilnya mungkin masih bermanfaat?
Memiliki QUIT - Anony-Mousse
1
Kemudian cobalah pendekatan lain - menemukan kluster positif dan negatif secara terpisah.
Memiliki QUIT - Anony-Mousse
1

Ya, ada algoritme yang disebut 'Afinitas Propagasi' yang berfungsi dengan bobot negatif; Saya percaya ini diimplementasikan dalam sklearn (lihat dokumentasi di sini ). Referensi untuk apa yang terjadi di balik layar dapat ditemukan di sini .

Semoga itu yang Anda cari!

squattyroo
sumber
Saya tidak tahu algoritma ini, tampaknya menjadi solusi yang bagus. Saya pasti akan mencobanya. Terima kasih.
Ewybe
Sejauh yang saya tahu pengelompokan Affinity Propagation tidak akan dapat secara simultan mempertimbangkan korelasi positif dan negatif sementara juga memisahkan mereka. Dalam hal ini, saya pikir tugas itu kontradiktif.
micans
0

Menurut saya masalah yang Anda gambarkan dikenal sebagai Masalah Clustering Korelasi . Informasi ini akan membantu Anda menemukan beberapa implementasi, seperti:

Perhatikan beberapa algoritma deteksi komunitas juga telah dimodifikasi untuk memproses jaringan yang ditandatangani, misalnya Amelio'13 , Sharma'12 , Anchuri'12 , dll. Namun, saya tidak dapat menemukan implementasi yang tersedia untuk umum.

Vincent Labatut
sumber
0

Lihatlah kode ini , ini cukup skalabel, bekerja dengan tepi positif dan negatif, dan memecahkan Correlation Clustering (CC) sebagai kasus khusus (r = 0). Namun, untuk kasus CC (memaksimalkan tautan positif dan meminimalkan tautan negatif di dalam kluster), saya akan menyarankan metode lain yang khusus dalam menyelesaikan tujuan ini.

Sebagai ilustrasi, Correlation Clustering (tidak seperti apa yang dicari oleh literatur Deteksi Komunitas) tidak memperhitungkan kepadatan positif dari cluster, jadi ketika sebuah jaringan tidak memiliki atau sedikit ikatan negatif (kebanyakan kasus dunia nyata), semua jaringan dimasukkan ke dalam satu besar gugus.

Orang Esma
sumber