วิธีกำหนดน้ำหนักให้กับโหนดในกราฟเครือข่ายแบบกำหนดทิศทาง และคำนวณน้ำหนักโหนดที่มีประสิทธิผล

ปัญหาของฉัน:

  1. ฉันมีชุดของโหนด โดยบางโหนดเชื่อมต่อกันด้วยขอบทิศทาง
  2. ฉันต้องการกำหนดน้ำหนักให้กับแต่ละโหนดและแต่ละขอบ
  3. สุดท้ายนี้ ฉันต้องการคำนวณน้ำหนักโหนดที่มีประสิทธิผลโดยพิจารณาจากอิทธิพลของโหนดที่เชื่อมต่อ

พื้นหลัง:

  1. ขณะนี้ฉันกำลังใช้ JUNG เพื่อแก้ไขปัญหาของฉัน
  2. ฉันดูแพ็คเกจ JUNG edu.uci.ics.jung.algorithms.scoring แต่ไม่แน่ใจว่าจะช่วยให้ฉันบรรลุวัตถุประสงค์ได้หรือไม่

java graph algorithm graph-algorithm jung
person user1920253    schedule 20.12.2012    source แหล่งที่มา
comment
มีหลายวิธีในการคำนวณน้ำหนักโหนด [ประสิทธิผล] ตามอิทธิพลของโหนดที่เชื่อมต่อ JUNG มีหลายวิธีในการดำเนินการดังกล่าวในแพ็คเกจที่คุณระบุ โปรดชี้แจงข้อกำหนดของคุณ: น้ำหนักโหนดและน้ำหนักขอบจะมีคุณสมบัติใดบ้าง และคุณคาดหวังว่าสิ่งเหล่านี้จะช่วยกำหนดน้ำหนักโหนดที่ 'มีประสิทธิผล' ได้อย่างไร คุณคาดหวังว่าความหมายของน้ำหนักโหนดที่มีประสิทธิผลจะเป็นอย่างไร ฯลฯ   -  person Joshua O'Madadhain    schedule 22.12.2012
comment
ขอบคุณโจชัวที่สละเวลาตอบ   -  person user1920253    schedule 26.12.2012
comment
(1) สมมติว่าฉันมีกราฟที่มีโหนดความเสี่ยงที่กำหนดไว้ล่วงหน้าจำนวนมากสำหรับแต่ละโหนด (2) ขณะนี้โหนดเหล่านี้บางส่วนเชื่อมต่อกับโหนดอื่นด้วยขอบทิศทาง ขอบเหล่านี้มีความหนาแปรผัน กล่าวคือ ความเสี่ยงที่เกิดขึ้นจะแตกต่างกันไปขึ้นอยู่กับขนาดของขอบ (3) ตอนนี้ ฉันต้องการคำนวณความเสี่ยงที่มีประสิทธิผลของโหนดเหล่านี้ตามการเชื่อมต่อ ‹br› ฉันเคยเห็น JUNG ให้คะแนนแพ็คเกจแล้ว ฉันไม่แน่ใจว่าต้องใช้อัลกอริทึมใดตามความต้องการของฉัน คุณช่วยแนะนำหน่อยได้ไหมว่าอันไหนเหมาะสมกว่า & มีตัวอย่างนัยหรือไม่?   -  person user1920253    schedule 26.12.2012
comment
คุณยังไม่มีข้อกำหนดที่ชัดเจนเพียงพอที่จะกำหนดอัลกอริทึม โดยพื้นฐานแล้ว หากคุณต้องการอัลกอริธึมการวนซ้ำแบบ PageRank คุณจะต้องกำหนดความเสี่ยงสำหรับโหนด N ในเวลา T ในแง่ของความเสี่ยงเพื่อนบ้านของ N (รุ่นก่อน? ผู้สืบทอด?) ในเวลา T-1 (คุณควรสามารถพิสูจน์คำจำกัดความนี้ได้ในระดับหนึ่งด้วย) พูดง่ายๆ ก็คือ คุณไม่มีวัตถุประสงค์ที่กำหนดไว้ชัดเจน ดังนั้นจึงเป็นไปไม่ได้ที่จะแนะนำวิธีบรรลุเป้าหมายดังกล่าว นี่เป็นคำถามในการออกแบบโมเดลเป็นหลัก จนกว่าคุณจะดำเนินการดังกล่าว และไม่เกี่ยวข้องกับซอฟต์แวร์ใดๆ โดยเฉพาะ   -  person Joshua O'Madadhain    schedule 28.12.2012

คำตอบ (2)


arrow_upward
1
arrow_downward

วิธีหนึ่งหากแสดงโหนดของคุณเป็นคลาส Java และน้ำหนักเป็นคุณสมบัติของคลาสนี้ คุณสามารถเก็บชุดของขอบเป็นฟิลด์ของคลาส และใช้วิธีการคำนวณน้ำหนักที่มีประสิทธิภาพ (เช่น: getEffectiveWeight())

person gerrytan    schedule 20.12.2012
comment
จริง. JUNG ได้จัดเตรียมเฟรมเวิร์กพื้นฐานทั้งหมดที่ทำงานกับกราฟไว้แล้ว คำถามของฉันมาจากอัลกอริธึมกราฟ (เช่น PageRank หรือ r EigenvectorCentrality) เนื่องจากฉันจะกำหนดน้ำหนักโหนดและใช้อัลกอริธึมเหล่านี้เพื่อค้นหาอิทธิพลของขอบเหล่านี้ได้อย่างไร - person user1920253; 21.12.2012
comment
PageRank ไม่ได้ใช้น้ำหนักโหนดเพื่อกำหนดคะแนนต่อโหนด หาก (ตัวอย่าง) คุณพิจารณาว่าน้ำหนักโหนด (เริ่มต้น) คือความน่าจะเป็นในการเริ่มต้นที่แต่ละโหนด จริงๆ แล้วการแจกแจงความน่าจะเป็นนี้ไม่เกี่ยวข้องกับคำตอบสุดท้ายเลย โดยมีเงื่อนไขว่ากราฟมีการเชื่อมต่ออย่างแน่นหนา (PageRankWithPriors เป็นอีกเรื่องหนึ่ง) - person Joshua O'Madadhain; 22.12.2012

arrow_upward
0
arrow_downward

มีสองแนวทางที่อยู่ในใจ:

  1. เพิ่มฟิลด์ weight ในคลาส Node และ Edge ของคุณ

  2. สร้าง Maps สองอัน อันหนึ่งใช้ Nodes เป็นคีย์ และอีกอันใช้ Edges เป็นคีย์ จากนั้นเก็บ weight เป็นค่า

person Code-Apprentice    schedule 21.12.2012
comment
หากเรากำลังพูดถึง PageRank ของ JUNG และอัลกอริธึมที่เกี่ยวข้อง ก็ไม่จำเป็น: น้ำหนักโหนด (โดยทั่วไป) ถูกกำหนดโดยอัลกอริทึม และน้ำหนักขอบสามารถระบุในตัวสร้างได้ หากต้องการ - person Joshua O'Madadhain; 22.12.2012