ตัวชี้วัดกราฟที่เน้นการครอบงำ (ทัวร์นาเมนต์)

ฉันสนใจที่จะได้รับตัวชี้วัดการครอบงำ (เช่นเดียวกับในลำดับชั้นการครอบงำ) สำหรับโหนดในกราฟที่กำกับการครอบงำ หรือที่เรียกว่ากราฟการแข่งขัน ฉันสามารถใช้ R และแพ็คเกจ igraph เพื่อสร้างกราฟดังกล่าวได้อย่างง่ายดาย เช่น

library(igraph)

สร้างกรอบข้อมูลของขอบ

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)

กราฟที่ลงจุดนี้แสดงให้เห็นว่าโหนด 1 มีอิทธิพลต่อโหนด 2, 3 และ 4 (มีความโดดเด่น) โดยที่ 2 มีความโดดเด่นต่อ 3 และ 4 และ 3 นั้นมีความโดดเด่นต่อ 4

อย่างไรก็ตาม ฉันไม่เห็นวิธีง่ายๆ ในการคำนวณลำดับชั้นการครอบงำเหมือนในหน้า: https://www.math.ucdavis.edu/~daddel/linear_algebra_appl/Applications/GraphTheory/GraphTheory_9_17/node11.html ดังนั้น คำถามแรกและคำถามหลักของฉันคือมีใครรู้วิธีหาลำดับชั้นการครอบงำ/เมตริกการครอบงำตามโหนดสำหรับกราฟแบบนี้โดยใช้โซลูชันที่หวังว่าจะเขียนโค้ดแล้วใน R หรือไม่

ยิ่งไปกว่านั้น ในกรณีจริงของฉัน จริงๆ แล้วฉันมีเมทริกซ์กระจัดกระจายซึ่งขาดการโต้ตอบบางอย่าง เช่น

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

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

plot(incomplete.graph)

ในกราฟที่ลงจุดนี้ ไม่มีความเชื่อมโยงระหว่างสปีชีส์ 1 และ 3 อย่างไรก็ตาม เมื่อมีข้อสันนิษฐานบางประการเกี่ยวกับการผ่านผ่าน ลำดับชั้นการครอบงำจะเหมือนกับข้างต้น

นี่เป็นปัญหาที่ซับซ้อนกว่ามาก แต่ถ้าใครมีข้อมูลใดๆ เกี่ยวกับวิธีที่ฉันจะหาเมตริกซ์ที่เน้นโหนดตามโหนดสำหรับเมทริกซ์แบบกระจัดกระจายเช่นนี้ โปรดแจ้งให้เราทราบ ฉันหวังว่าจะได้วิธีแก้ปัญหาที่เข้ารหัสแล้วใน R แต่ฉันก็เต็มใจที่จะเขียนโค้ดด้วยตัวเองมากกว่าอย่างแน่นอน

ขอบคุณล่วงหน้า!


r igraph social-networking graph-theory
person forlooper    schedule 23.09.2013    source แหล่งที่มา
comment
สำหรับนักทฤษฎีที่ไม่ใช่กราฟ อาจเป็นการดีกว่าที่จะอธิบายแนวคิดเรื่องอำนาจเหนือในคำถามของคุณ มันขึ้นอยู่กับคุณแล้ว คนอื่นอาจรู้ว่าคุณกำลังพูดถึงอะไร นอกจากนี้ หากคำถามของคุณเกี่ยวกับคณิตศาสตร์ ไม่ใช่การเขียนโค้ด SO อาจไม่ใช่คำตอบที่ถูกต้อง   -  person Frank    schedule 24.09.2013
comment
ขอบคุณแฟรงค์ ฉันแก้ไขให้ชัดเจนขึ้นฉันหวังว่า กล่าวโดยสรุป คำถามแรกของฉันเกี่ยวกับการเขียนโปรแกรม ในขณะที่คำถามที่สองอาจเกี่ยวกับคณิตศาสตร์มากกว่า...แม้ว่าตอนนี้ฉันหวังว่าจะข้ามคณิตศาสตร์และหาวิธีแก้ปัญหาที่ใช้โค้ดเพื่อเล่นซอในขณะที่ฉันพยายามทำความเข้าใจคณิตศาสตร์ของ ด้านที่ซับซ้อนมากขึ้นของมัน   -  person forlooper    schedule 24.09.2013
comment
แพ็คเกจ relations จะมีประโยชน์หรือไม่ ดูเหมือนว่าจะสามารถจัดการกับการคำนวณสำหรับการครอบงำของโหนดหนึ่งเหนืออีกโหนดหนึ่งได้ - cran.r-project.org/web/packages/relations/vignettes/   -  person thelatemail    schedule 24.09.2013
comment
พูดตามตรงฉันไม่รู้ว่าคำถามของคุณคืออะไร ผลลัพธ์สำหรับกราฟตัวอย่างของคุณจะเป็นอย่างไร คุณต้องการได้รับหน่วยเมตริก แต่หน่วยเมตริกนี้จะวัดอะไรได้ทั้งหมด เหตุใดจึงเป็นคำถาม stackoverflow หากคุณไม่รู้ว่าต้องการคำนวณอะไร   -  person Gabor Csardi    schedule 24.09.2013
comment
@GaborCsardi ขอบคุณมากสำหรับการตอบกลับ! ฉันรู้ว่าฉันต้องการคำนวณอะไร ฉันต้องการตัวเลขที่อธิบายอันดับในลำดับชั้นการครอบงำของทุกโหนดในกราฟกำกับ ดังที่แสดงในลิงก์ที่ฉันให้ไว้ในโพสต์ต้นฉบับ ดังนั้น ในโค้ดตัวอย่างที่ฉันให้ไว้ โหนด 1 จะเป็น 1 โหนด 2 จะเป็น 2 โหนด 3 จะเป็น 3 และโหนด 4 จะเป็น 4 ฉันจินตนาการว่าในเครือข่ายที่ซับซ้อนกว่านี้ มันเป็นไปได้ที่จะมีค่าของตัวชี้วัดนี้ที่ คือความสัมพันธ์ หรือช่วง หรืออะไรทำนองนั้น โดยเฉพาะอย่างยิ่งถ้าเครือข่ายไม่ใช่กราฟอะไซคลิกแบบกำหนดทิศทาง หรือถ้าเป็นเมทริกซ์แบบกระจัดกระจาย   -  person forlooper    schedule 24.09.2013
comment
@thelatemail ขอบคุณ! ฉันกำลังดูสิ่งนั้นอยู่ตอนนี้ ฉันไม่เห็นว่ามันสามารถคำนวณการครอบงำได้ที่ไหน แต่ฉันอาจขาดอะไรบางอย่างไป ส่วนที่ใกล้ถึงจุดสิ้นสุดของบทความสั้นเกี่ยวกับลำดับเชิงเส้นดูเหมือนว่าจะมาถูกทางแล้ว บางทีฉันอาจต้องคิดให้หนักขึ้นเกี่ยวกับวิธีการเลือกใช้ร่วมกัน   -  person forlooper    schedule 24.09.2013
comment
@forlooper - ฉันคิดว่าฉันเข้าใจแล้ว - ลองคำตอบของฉันด้านล่างแล้วดูว่ามันใช้ได้กับชุดข้อมูลที่ซับซ้อนกว่านี้หรือไม่   -  person thelatemail    schedule 24.09.2013
comment
@forlooper: ตกลง แต่นี่เป็นเพียงระดับนอกของโหนดใช่ไหม ฉันหมายถึงถ้าการจัดอันดับขึ้นอยู่กับจำนวนโหนดที่ถูกครอบงำโดยโหนดใดโหนดหนึ่ง ลิงก์ของคุณไม่ได้อธิบายจริงๆ ว่าลำดับชั้นการครอบงำคืออะไร จริงๆ แล้วไม่มีแม้แต่ลำดับชั้นของคำด้วยซ้ำ   -  person Gabor Csardi    schedule 24.09.2013
comment
@GaborCsardi. ขอบคุณ! ฉันอายที่จะบอกว่าฉันไม่ได้คำนึงถึงความเป็นไปได้นั้น ในกรณีที่สมบูรณ์ข้างต้นจะส่งคืนคำตอบที่ถูกต้อง อย่างไรก็ตาม ในตัวอย่างที่สองที่ไม่สมบูรณ์ ระบบจะไม่ทำงาน ไม่ว่าจะด้วยวิธีใด ฉันขอขอบคุณที่ชี้ให้เห็นถึงมาตรการนี้ ซึ่งจะมีประโยชน์มากในภายหลัง ลำดับชั้นการครอบงำคือการจัดอันดับระหว่างหน่วยต่างๆ เช่น จุดยอด โดยสรุปว่าหน่วยใดมีความโดดเด่นเหนือหน่วยอื่น แน่นอนว่าอาจมีความสัมพันธ์กัน แต่โดยทั่วไป (กรณีที่ง่ายที่สุด) มีความสัมพันธ์แบบสกรรมกริยาซึ่งสามารถตั้งสมมติฐานบางประการเกี่ยวกับโหนดที่ไม่มีข้อมูลได้   -  person forlooper    schedule 24.09.2013

คำตอบ (1)


arrow_upward
1
arrow_downward

ไม่แน่ใจว่าสิ่งนี้สมบูรณ์แบบหรือฉันเข้าใจสิ่งนี้อย่างถ่องแท้ แต่ดูเหมือนว่าจะได้ผลเท่าที่ควรจากการลองผิดลองถูก:

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

มีตัวเลือกที่เป็นไปได้มากมายสำหรับ method= สำหรับการจัดการกับความสัมพันธ์ ฯลฯ - ดู ?relation_consensus สำหรับข้อมูลเพิ่มเติม การใช้ method="SD/L" ซึ่งเป็นลำดับเชิงเส้นอาจเหมาะสมที่สุดสำหรับข้อมูลของคุณ แม้ว่าจะสามารถแนะนำวิธีแก้ปัญหาที่เป็นไปได้ได้หลายวิธีเนื่องจากข้อขัดแย้งในตัวอย่างที่ซับซ้อนมากขึ้น สำหรับข้อมูลธรรมดาในปัจจุบันไม่เป็นเช่นนั้น - ลอง:

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

วิธีการจัดการกับสิ่งนี้มีให้ไว้ในตัวอย่างใน ?relation_consensus อีกครั้ง

person thelatemail    schedule 24.09.2013
comment
มันใช้งานได้ดีมาก โดยเฉพาะอย่างยิ่ง ตัวเลือกที่สองที่นี่ดูเหมือนว่าจะส่งคืนลำดับเชิงเส้นที่ถูกต้อง แม้ว่าเมทริกซ์จะไม่มีค่าก็ตาม ดังตัวอย่างที่สองที่ฉันให้ไว้ ฉันซาบซึ้งมาก ขอบคุณ @thelatemail นอกจากนี้ ในโค้ดของคุณด้านบน คุณเรียกวัตถุว่า the.new ฉันไม่แน่ใจว่าสิ่งนี้มาจากไหน แม้ว่าจะไม่ส่งผลต่อคำตอบที่ถูกต้องก็ตาม ไชโย - person forlooper; 24.09.2013
comment
@forlooper - ไม่ต้องกังวล ข้อผิดพลาด .new ได้รับการแก้ไขแล้วเช่นกัน นั่นเป็นเพียงชื่อของชุดข้อมูลการทำงานของฉัน - person thelatemail; 25.09.2013