Metrik grafik yang diarahkan pada dominasi (turnamen).

Saya tertarik untuk mendapatkan metrik dominasi (seperti dalam hierarki dominasi) untuk node dalam grafik berarah dominasi, alias grafik turnamen. Saya dapat menggunakan R dan paket igraph untuk membuat grafik seperti itu dengan mudah, mis.

library(igraph)

membuat bingkai data tepi

the.froms <- c(1,1,1,2,2,3)

the.tos <- c(2,3,4,3,4,4)

the.set <- data.frame(the.froms, the.tos)

set.graph <- graph.data.frame(the.set)

plot(set.graph)

Grafik yang diplot ini menunjukkan bahwa node 1 mempengaruhi node 2, 3, dan 4 (dominan terhadap mereka), bahwa 2 dominan terhadap 3 dan 4, dan bahwa 3 dominan terhadap 4.

Namun, saya tidak melihat cara mudah untuk menghitung hierarki dominasi seperti di halaman: https://www.math.ucdavis.edu/~daddel/linear_algebra_appl/Applications/GraphTheory/GraphTheory_9_17/node11.html . Jadi, pertanyaan pertama dan utama saya adalah apakah ada yang tahu cara mendapatkan hierarki dominasi/metrik dominasi berbasis simpul untuk grafik seperti ini menggunakan beberapa solusi yang diharapkan sudah dikodekan di R?

Selain itu, dalam kasus saya yang sebenarnya, saya sebenarnya memiliki matriks renggang yang tidak memiliki beberapa interaksi, misalnya.

incomplete.set <- the.set[-2, ]

incomplete.graph <- graph.data.frame(incomplete.set)

plot(incomplete.graph)

Dalam grafik yang diplot ini, tidak ada hubungan antara spesies 1 dan 3, namun dengan asumsi transitivitas, hierarki dominasinya sama seperti di atas.

Ini adalah masalah yang jauh lebih rumit, tetapi jika ada yang punya masukan tentang bagaimana saya bisa mendapatkan metrik dominasi berbasis simpul untuk matriks renggang seperti ini, beri tahu saya. Saya berharap untuk solusi yang sudah dikodekan di R, tapi saya pasti LEBIH dari bersedia untuk mengkodekannya sendiri.

Terima kasih sebelumnya!


r igraph social-networking graph-theory
person forlooper    schedule 23.09.2013    source sumber
comment
Untuk ahli teori non-grafik, mungkin lebih baik menjelaskan konsep dominasi dalam pertanyaan Anda. Itu terserah Anda; orang lain mungkin tahu apa yang Anda bicarakan. Selain itu, jika pertanyaan Anda adalah tentang matematika dan bukan pengkodean, SO mungkin bukan tempat yang tepat untuk menjawabnya.   -  person Frank    schedule 24.09.2013
comment
Terima kasih Frank. Saya memodifikasinya menjadi lebih jelas, saya harap. Singkatnya, pertanyaan pertama saya pastinya tentang pemrograman, sedangkan pertanyaan kedua mungkin lebih banyak tentang matematika...walaupun saya berharap untuk mengabaikan matematika untuk saat ini dan menemukan solusi kode untuk dimainkan sementara saya mencoba dan memahami matematika dari aspek yang lebih rumit dari itu.   -  person forlooper    schedule 24.09.2013
comment
Apakah paket relations ada gunanya? Tampaknya mampu menangani perhitungan dominasi satu node terhadap node lainnya - cran.r-project.org/web/packages/relations/vignettes/   -  person thelatemail    schedule 24.09.2013
comment
Sejujurnya, saya tidak tahu apa sebenarnya pertanyaan Anda. Apa keluaran dari contoh grafik Anda? Anda ingin mendapatkan metrik, tetapi apa yang akan diukur oleh metrik ini? Mengapa ini merupakan pertanyaan stackoverflow jika Anda tidak tahu apa yang ingin Anda hitung?   -  person Gabor Csardi    schedule 24.09.2013
comment
@GaborCsardi Terima kasih banyak atas tanggapannya! Saya tahu apa yang ingin saya hitung. Saya ingin angka yang menggambarkan peringkat dalam hierarki dominasi setiap node dalam grafik berarah, seperti yang ditunjukkan pada tautan yang saya sediakan di postingan asli. Jadi, dalam contoh kode yang saya berikan, node 1 akan menjadi 1, node 2 akan menjadi 2, node 3 akan menjadi 3 dan node 4 akan menjadi 4. Saya membayangkan dalam jaringan yang lebih rumit dimungkinkan untuk memiliki nilai metrik ini yang adalah ikatan, atau rentang, atau semacamnya, terutama jika jaringan tersebut bukan merupakan grafik asiklik berarah atau jika jaringan tersebut merupakan matriks renggang.   -  person forlooper    schedule 24.09.2013
comment
@thelatemail Terima kasih! Saya sedang melihatnya sekarang. Saya tidak melihat di mana ia dapat menghitung dominasi, tapi saya mungkin melewatkan sesuatu. Bagian menjelang akhir sketsa tentang tatanan linier sepertinya sudah berada di jalur yang benar, mungkin saya perlu berpikir lebih keras tentang cara mengkooptasinya.   -  person forlooper    schedule 24.09.2013
comment
@forlooper - Saya rasa saya sudah mengetahuinya - coba jawaban saya di bawah ini dan lihat apakah itu berfungsi untuk kumpulan data yang lebih kompleks.   -  person thelatemail    schedule 24.09.2013
comment
@forlooper: Oke, tapi ini hanya derajat keluar dari node, bukan? Maksud saya, jika pemeringkatan didasarkan pada jumlah node yang didominasi oleh node tertentu. Tautan Anda tidak terlalu menjelaskan apa itu hierarki dominasi, bahkan tidak mengandung kata hierarki.   -  person Gabor Csardi    schedule 24.09.2013
comment
@GaborCsardi. Terima kasih! Saya malu untuk mengatakan bahwa saya tidak mempertimbangkan kemungkinan itu. Dalam kasus lengkap di atas, ia mengembalikan jawaban yang benar. Namun, dalam contoh kedua yang tidak lengkap, ini tidak berhasil. Apa pun yang terjadi, saya menghargai petunjuk terhadap tindakan ini, ini akan sangat membantu nantinya. Hierarki dominasi adalah peringkat antar unit, misalnya. simpul, merangkum unit mana yang dominan terhadap unit lainnya. Tentu saja mungkin terdapat ikatan, namun umumnya (kasus paling sederhana) terdapat hubungan transitif sehingga seseorang dapat membuat beberapa asumsi tentang node yang datanya tidak tersedia.   -  person forlooper    schedule 24.09.2013

Jawaban (1)


arrow_upward
1
arrow_downward

Tidak yakin apakah ini sempurna atau saya sepenuhnya memahaminya, tetapi tampaknya berfungsi sebagaimana mestinya dari beberapa percobaan dan kesalahan:

library(relations)
result <- relation_consensus(endorelation(graph=the.set),method="Borda")
relation_class_ids(result)
#1 2 3 4 
#1 2 3 4

Ada banyak pilihan potensial untuk method= dalam menangani ikatan dll - lihat ?relation_consensus untuk informasi lebih lanjut. Menggunakan method="SD/L" yang merupakan urutan linier mungkin paling sesuai untuk data Anda, meskipun ini dapat menyarankan beberapa kemungkinan solusi karena konflik dalam contoh yang lebih kompleks. Untuk data sederhana saat ini, hal ini tidak terjadi - coba:

result <- relation_consensus(endorelation(graph=the.set),method="SD/L",
                             control=list(n="all"))
result
#An ensemble of 1 relation of size 4 x 4.

lapply(result,relation_class_ids)
#[[1]]
#1 2 3 4 
#1 2 3 4

Metode untuk mengatasi hal ini sekali lagi diberikan dalam contoh di ?relation_consensus.

person thelatemail    schedule 24.09.2013
comment
Ini bekerja dengan sangat baik. Secara khusus, opsi kedua di sini tampaknya mengembalikan urutan linier yang benar meskipun matriksnya kehilangan nilai, seperti pada contoh kedua yang saya berikan. Saya sangat menghargainya, terima kasih @thelatemail. Selain itu, dalam kode di atas Anda memanggil objek the.new. Saya tidak yakin dari mana asalnya, meskipun itu tidak mempengaruhi kebenaran jawaban ini. Bersulang - person forlooper; 24.09.2013
comment
@forlooper - jangan khawatir, kesalahan baru juga telah diperbaiki sekarang - itu hanya nama kumpulan data saya yang berfungsi. - person thelatemail; 25.09.2013