การวัดความคล้ายหรือระยะห่างระหว่างจุดยอดในกราฟ
มีสองประเภทของการวัด ได้แก่ ระยะทางแบบจีโอเดซิก (Geodesic Distance) และ ระยะทางแบบสุ่มเดิน (Distance based on Random Walk)
1. ระยะทางจีโอเดซิก (Geodesic Distance)
การวัดระยะห่างระหว่างสองจุดยอดในกราฟที่ง่ายที่สุดคือ เส้นทางสั้นที่สุด (Shortest Path) ระหว่างจุดยอด โดยทั่วไป ระยะทางจีโอเดซิกระหว่างสองจุดยอดคือ ความยาวในแง่ของจำนวนเส้นขอบ (Number of Edges) ของเส้นทางสั้นที่สุดระหว่างจุดยอด สำหรับสองจุดยอดที่ไม่เชื่อมต่อในกราฟ ระยะทางจีโอเดซิกแสดงเป็นอันนันต์ (Infinite)
ด้วยการใช้ระยะทางจีโอเดซิก สามารถกำหนดการวัดที่มีประโยชน์หลายอย่างสำหรับการวิเคราะห์และจัดกลุ่มกราฟได้ ให้กราฟ G = (V, E) โดย V คือชุดจุดยอด และ E คือชุดเส้นขอบ สามารถกำหนดได้ดังนี้:
- ความเยี่ยมเย้ย (Eccentricity) ของโหนด v ∈ V: eccen(v) คือ ระยะทางจีโอเดซิกสูงสุดระหว่าง v และโหนด u ใดๆ ∈ V \ {v} eccen(v) บ่งบอกว่า v อยู่ห่างจากจุดยอดปลาย (Farthest Vertex) ของกราฟเพียงใด
- รัศมีของกราฟ G (Radius): คือ ความเยี่ยมเย้ยขั้นต่ำ (Minimum Eccentricity) ของทุกจุดยอด r = min eccen(v) สำหรับ v ∈ V รัศมีจับระยะห่างระหว่าง "จุดกลางมากที่สุด" (Most Central Point) และ "ขอบไกลที่สุด" (Furthest Border) ของกราฟ
- เส้นผ่านศูนย์กลางของกราฟ G (Diameter): คือ ความเยี่ยมเย้ยสูงสุด (Maximum Eccentricity) ของทุกจุดยอด d = max eccen(v) สำหรับ v ∈ V เส้นผ่านศูนย์กลางกำหนดระยะห่างสูงสุดระหว่างคู่จุดยอดใดๆ
- จุดยอดรอบนอก (Peripheral Vertex): คือ จุดยอดที่ให้เส้นผ่านศูนย์กลาง
2. SimRank - ความคล้ายแบบสุ่มเดินและบริบทโครงสร้าง (Similarity Based on Random Walk and Structural Context)
ในหลายแอปพลิเคชัน ระยะทางจีโอเดซิกอาจไม่เหมาะสมในการคำนวณความคล้ายคลึงระหว่างจุดยอดในกราฟ ใน SimRank มีการวัดความคล้ายที่ขึ้นอยู่กับการสุ่มเดิน (Random Walk) และโครงสร้างพื้นฐาน (Structural Context) ของกราฟ ในคณิตศาสตร์ การสุ่มเดิน (Random Walk) คือ เส้นทางที่ประกอบด้วยการขั้นตอนสุ่มซ้ำๆ (Successive Random Steps)
มีสองวิธีในการแสดงความคล้ายคลึง:
- ความคล้ายแบบบริบทโครงสร้าง (Structural Context-based Similarity): สองผู้ใช้ถือว่าเหมือนกัน หากพวกเขามีเพื่อนบ้าน (Neighbors) เหมือนกันในเครือข่ายสังคม ฮิวริสติกนี้เข้าใจง่าย เพราะสองคนที่ได้รับคำแนะนำจากเพื่อนร่วมมากมาย มักตัดสินใจเหมือนกัน ประเภทความคล้ายนี้ขึ้นอยู่กับโครงสร้างท้องถิ่น (Local Structure) คือบริบทล่าง (Neighborhoods) ของจุดยอด
- ความคล้ายแบบสุ่มเดิน (Random Walk-based Similarity): สมมติ AllElectronics ส่งข้อมูลโปรโมชันให้ทั้ง Ada และ Bob ในเครือข่ายสังคม Ada และ Bob สามารถส่งต่อข้อมูลดังกล่าวแบบสุ่มไปยังเพื่อน (หรือเพื่อนบ้าน) ในเครือข่าย ความใกล้ชิดระหว่าง Ada และ Bob สามารถคำนวณได้โดยความน่าจะเป็นที่ผู้ใช้คนอื่นๆ ที่ต่างกัน รับข้อมูลโปรโมชันที่ส่งให้ Ada และ Bob เริ่มต้น พร้อมกัน ประเภทความคล้ายนี้ขึ้นอยู่กับการเข้าถึงได้ของการสุ่มเดิน (Random Walk Reachability) ผ่านเครือข่าย จึงถูกกำหนดว่าเป็นความคล้ายแบบสุ่มเดิน
