Algoritma untuk deteksi komunitas untuk grafik bipartit?

Apakah ada algoritma untuk deteksi komunitas untuk grafik bipartit (jaringan 2-mode) yang diterapkan dalam igraph, networkX, R atau Python dll? Secara khusus, adakah implementasi seperti itu di mana seseorang akan dapat membatasi deteksi komunitas hanya pada salah satu dari dua mode?

python graph-theory adamo
sumber

Bagaimana seseorang "membatasi deteksi komunitas hanya pada salah satu dari dua mode" tanpa mengetahui terlebih dahulu node mana yang membentuk mode? Tampaknya bundar.

hardmath

Dalam jaringan bipartit Anda sudah tahu dua mode. Jadi misalnya jika setengah dari simpul yang termasuk dalam mode "A" terhubung dengan sebuah simpul yang termasuk dalam mode "B" maka Anda memiliki komunitas di sana.

adamo

Jika sebelumnya Anda tahu node mana yang termasuk dalam masing-masing mode, maka itu menjawab pertanyaan saya tentang cara membatasi deteksi. Namun contoh Anda dan gagasan "komunitas" tersiratnya tidak jelas. Jika sebuah simpul dalam grafik bipartit tidak terhubung ke simpul mana pun dari mode yang berlawanan, maka simpul tersebut tidak terhubung ke simpul mana pun (itu akan terisolasi). Dalam grafik bipartit yang terhubung, setiap mode "A" menghubungkan ke beberapa mode "B" dan sebaliknya. "Komunitas" biasanya berarti sesuatu yang lebih dari sebuah subgraph yang terhubung.

hardmath

Pada refleksi saya menduga "tautan Anda dengan sebuah simpul" dimaksudkan untuk terhubung dengan satu simpul umum, memberikan klik pada grafik yang diproyeksikan (lihat Jawaban), dan dengan demikian "sebuah komunitas di sana". Permintaan maaf karena tidak memahami maksud Anda pada bacaan pertama.

hardmath

Tidak perlu permintaan maaf. Bahasa Inggris saya juga tidak begitu jelas.

adamo

Jawaban:

Frasa "deteksi komunitas" secara longgar didefinisikan sebagai mempartisi simpul dari sebuah grafik menjadi "komunitas" sehingga masing-masing memiliki anggota yang lebih terhubung satu sama lain daripada dengan anggota "komunitas" lainnya.

Tugas pertama kami adalah memastikan apa artinya ini dalam kasus grafik bipartit, yang secara definisi terdiri dari dua "mode" sehingga anggota dari satu mode hanya ditautkan dengan anggota mode lainnya. Ini dapat dinyatakan, setidaknya untuk grafik sederhana, sebagai memiliki matriks adjacency dari struktur blok khusus:

A = (\begin{matrix} 0 & B \\ B^{T} & 0 \end{matrix})

$A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$

$A^2$ $BB^T$ $B^TB$ $A$

Kami sama-sama beruntung karena algoritma pendeteksian komunitas igraph dan yang terkait telah "diperbarui untuk menangani grafik berbobot" (seperti multi-grafik).

S. Fortunato (2010) mensurvei kriteria deteksi komunitas ( deteksi komunitas dalam grafik ) dan penggunaannya dengan jaringan bipartit dan multipartit. Interpretasi yang saya sarankan di atas diartikulasikan pada halaman 8:

Grafik multipartit biasanya dikurangi menjadi proyeksi unipartit dari setiap kelas simpul. Misalnya, dari jaringan ilmuwan dan makalah bipartit, orang dapat mengekstraksi jaringan ilmuwan saja, yang terkait dengan kepenulisan bersama.

hardmath
sumber