দুটি ধরনের মাপ রয়েছে: জিওডেসিক দূরত্ব (geodesic distance) এবং র্যান্ডম ওক-ভিত্তিক দূরত্ব।
জিওডেসিক দূরত্ব (Geodesic Distance)
এক গ্রাফে দুটি ভের্টেক্সের মধ্যে দূরত্বের একটি সহজ মাপ হল ভের্টেক্সগুলোর মধ্যে সবচেয়ে ছোট পথ। সাধারণত, দুটি ভের্টেক্সের মধ্যে জিওডেসিক দূরত্ব হল সবচেয়ে ছোট পথের এজ সংখ্যা অনুযায়ী দৈর্ঘ্য। একটি গ্রাফে যেসব ভের্টেক্স সংযুক্ত নয়, তাদের জিওডেসিক দূরত্ব অসীম হিসেবে প্রকাশ করা হয়।
জিওডেসিক দূরত্ব ব্যবহার করে, গ্রাফ বিশ্লেষণ এবং ক্লাস্টারিং-এর জন্য বিভিন্ন উপকারী মাপ সংজ্ঞায়িত করা যায়। একটি গ্রাফ G = (V, E) দেওয়া থাকলে, যেখানে V হল ভের্টেক্সের সেট এবং E হল এজের সেট, নিম্নলিখিত موارد সংজ্ঞায়িত করা যায়:
একটি ভের্টেক্স v ∈ V-এর জন্য, v-এর একসেনট্রিসিটি (eccentricity), যাকে eccen(v) দ্বারা বোঝানো হয়, হল v এবং যেকোনো অন্য ভের্টেক্স u ∈ V - {v}-এর মধ্যে সর্বোচ্চ জিওডেসিক দূরত্ব। v-এর একসেনট্রিসিটি ক্যাপচার করে v তার গ্রাফের দূরতম ভের্টেক্স থেকে কত দূরে।
গ্রাফ G-এর রেডিয়াস হল সকল ভের্টেক্সের ন্যূনতম একসেনট্রিসিটি। অর্থাৎ, r = min eccen(v) (v ∈ V)। রেডিয়াস "সবচেয়ে কেন্দ্রীয় বিন্দু" এবং গ্রাফের "সর্বোচ্চ সীমানা" এর মধ্যে দূরত্ব ক্যাপচার করে।
গ্রাফ G-এর ডায়ামিটার হল সকল ভের্টেক্সের সর্বোচ্চ একসেনট্রিসিটি। অর্থাৎ, d = max eccen(v) (v ∈ V)। ডায়ামিটার যেকোনো দুটি ভের্টেক্সের মধ্যে সর্বোচ্চ দূরত্ব নির্ধারণ করে।
একটি পেরিফেরাল ভের্টেক্স হল সেই ভের্টেক্স যা ডায়ামিটার অর্জন করে।
SimRank - র্যান্ডম ওক এবং স্ট্রাকচারাল কনটেক্সট-ভিত্তিক সাদৃশ্য
বহু অ্যাপ্লিকেশনে, গ্রাফে ভের্টেক্সগুলোর মধ্যে সাদৃশ্য গণনায় জিওডেসিক দূরighth অনুপযুক্ত হতে পারে। SimRank-এ, একটি সাদৃশ্য মাপ র্যান্ডম ওক এবং গ্রাফের মৌলিক কাঠামোর ওপর ভিত্তি করে। গণিতে, একটি র্যান্ডম ওক হল একটি পথ যাতে ধাপে ধাপে র্যান্ডম প্রক্রিয়া নেওয়া হয়।
সাদৃশ্য প্রকাশ করার দুটি পদ্ধতি রয়েছে:
দুজন ব্যবহারকারী একে অপরের সাথে সাদৃশ্য যদি সোশ্যাল ওয়েবে তাদের সাধারণ প্রতিবেশী থাকে। এই হিউরিস্টিক উপযুক্ত কারণ বহু সাধারণ বন্ধু থেকে সুপারিশ পেয়ে দুজন ব্যক্তি একই সিদ্ধান্ত নেয়। এই ধরনের সাদৃশ্য লোকাল কাঠামোর (অর্থাৎ প্রতিবেশীদের) ওপর ভিত্তি করে এবং এটিকে স্ট্রাকচারাল কনটেক্সট-ভিত্তিক সাদৃশ্য বলা হয়।
মান लीজिए AllElectronics সোশ্যাল ওয়েবে Ada এবং Bob উভয়কেই প্রোমেশনাল ডেটা পাঠায়। Ada এবং Bob তাদের বন্ধুদের (বা প্রতিবেশীদের) নেটওয়ার্কে যাদুকরিভাবে সেটি ফরওয়ার্ড করতে পারে। Ada এবং Bob-এর মধ্যে घনিষ্ঠতা তাদের দ্বারা প্রারম্ভিকভাবে পাঠানো প্রোমেশনাল ডেটা বিভিন্ন ব্যবহারকারীদের একই সাথে পাওয়ার সম্ভাবনা দ্বারা হিসাব করা যায়। এই ধরনের সাদৃশ্য ওয়েবে র্যান্ডম ওক রিচেবিলিটির ওপর ভিত্তি করে এবং তাই র্যান্ডম ওক-ভিত্তিক সাদৃশ্য হিসেবে সংজ্ঞায়িত করা হয়।
