Pendekatan dan contoh pengelompokan grafik di "R"

Saya mencari untuk mengelompokkan / menggabungkan node dalam grafik menggunakan pengelompokan grafik di 'r'.

Ini adalah variasi mainan yang menakjubkan dari masalah saya.

• Ada dua "cluster"
• Ada "jembatan" yang menghubungkan cluster

Berikut ini adalah jaringan kandidat:

Ketika saya melihat jarak koneksi, "hopcount", jika Anda mau, maka saya bisa mendapatkan matriks berikut:

 mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

Pikiran di sini:

• Beruntung atau karena kesederhanaan mainan, matriks memiliki tambalan yang jelas ini tidak akan menjadi kasus dalam matriks (sangat besar). Jika saya secara acak hubungan antara titik dan baris maka itu tidak akan begitu bersih.
• Saya mungkin salah paham - jadi jika saya salah ketik, beri tahu saya.
• Hop-count di sini adalah jumlah hop terpendek yang menghubungkan titik pada baris i dengan titik pada kolom j. Hop-diri masih hop, jadi yang diagonal adalah semua.

Jadi dalam matriks ini jarak yang lebih besar (hop) memiliki angka yang lebih tinggi. Jika saya menginginkan sebuah matriks yang menunjukkan "konektivitas" alih-alih jarak, maka saya bisa melakukan dot-inverse, di mana setiap sel matriks diganti dengan invers multiplikatifnya.

Pertanyaan:

Untuk membantu saya menemukan jalan saya sendiri:

• Apa syarat untuk mengurangi jumlah node pada grafik dengan menggabungkannya? Apakah itu pengelompokan, penggabungan, munging - apa kata-kata yang harus saya gunakan?
• Apa teknik yang terbukti? Apakah ada buku pelajaran tentang topik itu? Bisakah Anda menunjuk ke makalah atau situs web?
• Sekarang saya mencoba untuk melihat di sini dulu - ini adalah tempat "pemeriksaan pertama" yang bagus. Saya tidak menemukan apa yang saya cari. Jika saya melewatkannya (bukan tidak mungkin) dapatkah Anda mengarahkan saya ke satu atau dua pertanyaan yang dijawab tentang topik di sini di CV?

Untuk membawa saya ke tempat tujuan saya:

• Apakah ada paket 'R' yang akan mengelompokkan node pada jaringan dengan benar?
• Bisakah Anda mengarahkan saya ke contoh kode untuk melakukan ini?
• Apakah ada paket 'R' yang akan menampilkan jaringan yang dihasilkan secara grafis?
• Bisakah Anda mengarahkan saya ke contoh kode untuk melakukan ini?

Terima kasih sebelumnya.

Contoh khusus Anda menyarankan menemukan komunitas dalam jaringan yang memiliki lebih banyak koneksi antara node dalam komunitas dan relatif sedikit tepi antara node di komunitas yang berbeda. Ini berbeda dari menemukan komunitas yang terisolasi , di mana ada subgraph yang sepenuhnya terputus.

Berikut adalah contoh deteksi komunitas dalam R menggunakan igraphpaket dan algoritma yang dijelaskan dalam Clauset et al. (2004) . Untuk menggunakan algoritma ini, saya mengubah "hop count" Anda menjadi matriks kedekatan biner tanpa loop otomatis. Algoritme membutuhkan matriks tidak terarah, yang konsisten dengan diagram tulisan tangan Anda dan data yang Anda berikan (ujungnya simetris).

library(igraph)
mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

Saya tidak bisa mengomentari kesesuaian runtuh node tersebut untuk analisis lebih lanjut, tetapi deteksi komunitas seperti itu pasti berguna untuk menjelajahi jaringan. Ada banyak algoritma pendeteksian komunitas lainnya (juga pustaka lain untuk analisis jaringan di R). Ini hanyalah satu contoh yang terjadi untuk menghasilkan output yang Anda inginkan untuk masalah mainan ini.

Jika Anda belum terikat ke repositori untuk node dan data koneksi Anda, Anda mungkin melihat paket Rneo4j. Tetapi ini menyiratkan penggunaan neo4j (basis data grafik, bukan RDBMS) untuk menyimpan data Anda. Saya bukan ahli di sini, tetapi saya pikir pendekatan ini mungkin sangat efektif jika a) seperti yang disarankan oleh Anony-Mousse, Anda tidak dapat memformalkan ini, atau b) jumlah node dan koneksi sangat besar, atau c) Anda memutar memiliki pertanyaan tambahan tentang jaringan Anda.

Untuk pembaca masa depan,

Berikut adalah serangkaian fungsi dari paket igraph dan yang terakhir dari MCL:

print("LABEL PROPAGATION")
w<-cluster_label_prop(g)

print("Leading Eigen")
w<-cluster_leading_eigen(g)

print("SpinGlass")
w<-cluster_spinglass(g, stop.temp = 0.05)

print("walktrap")
w<-cluster_walktrap(g, steps=4)

print("MCL")
adj<-get.adjacency(g)
w<-mcl(adj,addLoops=TRUE)

Anda dapat menemukan dokumentasi di sini http://igraph.org/r/doc/ dan di sini https://cran.r-project.org/web/packages/MCL/MCL.pdf

Saya menemukan walktrap sangat berguna