เราจะวัดความเหมือนหรือระยะห่างระหว่างจุดยอดสองจุดในกราฟได้อย่างไร

มีการวัด 2 ประเภท เช่น ระยะทาง geodesic และระยะทางตามการเดินแบบสุ่ม

ระยะทางทางภูมิศาสตร์ − การวัดระยะทางอย่างง่ายระหว่างจุดยอดสองจุดในกราฟคือเส้นทางที่สั้นที่สุดในบรรดาจุดยอด โดยปกติ ระยะทาง geodesic ระหว่างจุดยอดสองจุดคือความยาวในแง่ของขอบหลายด้านของเส้นทางที่สั้นที่สุดในบรรดาจุดยอด สำหรับจุดยอดสองจุดที่ไม่ได้เชื่อมโยงกันในกราฟ ระยะ geodesic จะแสดงเป็นอนันต์

ด้วยการใช้ระยะทาง geodesic มันสามารถแสดงการวัดที่มีประโยชน์ต่างๆ สำหรับการวิเคราะห์กราฟและการจัดกลุ่ม ให้กราฟ G =(V, E) โดยที่ V คือเซตของจุดยอด และ E คือเซตของขอบ มันสามารถแทนค่าต่อไปนี้ -

• สำหรับจุดยอด v ∈ V ความเยื้องศูนย์กลางของ v ซึ่งระบุ eccen(v) คือระยะห่าง geodesic สูงสุดระหว่าง v และจุดยอดหลายจุด u ∈ V − {v} ความเยื้องศูนย์กลางของ v จะจับว่า v อยู่ห่างจากจุดยอดสุดปลายสุดในกราฟเพียงใด

• รัศมีของกราฟ G คือความเยื้องศูนย์กลางต่ำสุดของจุดยอดทั้งหมด

• นั่นคือ r =นาที eccen(v)

  v ∈ V

  รัศมีจะจับระยะห่างระหว่าง "จุดศูนย์กลางมากที่สุด" และ "เส้นขอบที่ไกลที่สุด" ของกราฟ

• เส้นผ่านศูนย์กลางของกราฟ G คือความเยื้องศูนย์กลางสูงสุดของจุดยอดทั้งหมด

• นั่นคือ d =max eccen(v)

  v ∈ V

  เส้นผ่านศูนย์กลางกำหนดระยะห่างสูงสุดระหว่างจุดยอดบางคู่

• จุดยอดส่วนปลายคือจุดยอดที่สร้างเส้นผ่านศูนย์กลาง

SimRank − ความคล้ายคลึงกันโดยพิจารณาจากการเดินสุ่มและบริบทของโครงสร้าง − ในการใช้งานที่หลากหลาย ระยะทาง geodesic อาจไม่เหมาะสมในการคำนวณความคล้ายคลึงกันระหว่างจุดยอดในกราฟ ใน SimRank การวัดความคล้ายคลึงกันขึ้นอยู่กับการเดินสุ่มและตามกรอบพื้นฐานของกราฟ ในวิชาคณิตศาสตร์ การเดินสุ่มเป็นวิถีที่รวมถึงการสุ่มกระบวนการต่อเนื่องกัน

มีสองวิธีในการแสดงความคล้ายคลึงกันซึ่งมีดังนี้ -

• ผู้ใช้สองคนจะได้รับการปฏิบัติเหมือนกันหากมีเพื่อนบ้านเหมือนกันในเว็บโซเชียล ฮิวริสติกนี้เข้าใจได้เพราะคนสองคนที่ได้รับคำแนะนำจากเพื่อนทั่วไปจำนวนมากสร้างการตัดสินใจแบบเดียวกัน ความคล้ายคลึงกันประเภทนี้ขึ้นอยู่กับโครงสร้างในท้องถิ่น (เช่น ย่าน) ของจุดยอด และเรียกว่าความคล้ายคลึงตามบริบทเชิงโครงสร้าง

• สมมติว่า AllElectronics ส่งข้อมูลส่งเสริมการขายไปยังทั้ง Ada และ Bob ในเว็บโซเชียล Ada และ Bob สามารถสุ่มส่งต่อข้อมูลดังกล่าวไปยังเพื่อน (หรือเพื่อนบ้าน) ในเครือข่าย ความใกล้ชิดระหว่าง Ada และ Bob สามารถคำนวณได้จากโอกาสที่ผู้ใช้ที่แตกต่างกันจะได้รับข้อมูลส่งเสริมการขายที่ส่งไปยัง Ada และ Bob ในขั้นต้น ความคล้ายคลึงกันประเภทนี้ขึ้นอยู่กับความสามารถในการเข้าถึงของการเดินแบบสุ่มบนเว็บ ดังนั้นจึงกำหนดเป็นความคล้ายคลึงกันโดยอิงจากการสุ่มเดิน