দুই ধরনের পরিমাপ আছে যেমন জিওডেসিক দূরত্ব এবং এলোমেলো হাঁটার উপর ভিত্তি করে দূরত্ব।
জিওডেসিক দূরত্ব − একটি গ্রাফে দুটি শীর্ষবিন্দুর মধ্যে দূরত্বের একটি সরল পরিমাপ হল শীর্ষবিন্দুগুলির মধ্যে সবচেয়ে ছোট পথ। সাধারণত, দুটি শীর্ষবিন্দুর মধ্যে জিওডেসিক দূরত্ব হল শীর্ষবিন্দুর মধ্যে ক্ষুদ্রতম পথের একাধিক প্রান্তের দৈর্ঘ্য। একটি গ্রাফে সংযুক্ত নয় এমন দুটি শীর্ষবিন্দুর জন্য, জিওডেসিক দূরত্বকে অসীম হিসাবে উপস্থাপন করা হয়৷
জিওডেসিক দূরত্ব ব্যবহার করে, এটি গ্রাফ বিশ্লেষণ এবং ক্লাস্টারিংয়ের জন্য বিভিন্ন দরকারী পরিমাপ উপস্থাপন করতে পারে। একটি গ্রাফ দেওয়া হয়েছে G =(V, E), যেখানে V হল শীর্ষবিন্দুর সেট এবং E হল প্রান্তগুলির সেট, এটি নিম্নলিখিতগুলিকে উপস্থাপন করতে পারে -
-
একটি শীর্ষবিন্দু v ∈ V-এর জন্য, v এর বিকেন্দ্রতা, নির্দেশিত eccen(v), হল v এবং কয়েকটি শীর্ষবিন্দুর মধ্যে সর্বোচ্চ জিওডেসিক দূরত্ব u ∈ V − {v}। v এর বিকেন্দ্রতা গ্রাফে তার শেষ শীর্ষ থেকে v কত দূরে তা ক্যাপচার করে।
-
গ্রাফ G এর ব্যাসার্ধ হল সমস্ত শীর্ষবিন্দুর সর্বনিম্ন বিকেন্দ্রতা।
-
অর্থাৎ, r =min eccen(v)
v ∈ V
ব্যাসার্ধটি গ্রাফের "সবচেয়ে কেন্দ্রীয় বিন্দু" এবং "দূরতম সীমানা" এর মধ্যে দূরত্ব ক্যাপচার করে।
-
গ্রাফ G-এর ব্যাস হল সমস্ত শীর্ষবিন্দুর সর্বোচ্চ বিকেন্দ্রতা।
-
অর্থাৎ, d =max eccen(v)
v ∈ V
ব্যাস কিছু জোড়া শীর্ষবিন্দুর মধ্যে সর্বোচ্চ দূরত্ব নির্ধারণ করে।
-
একটি পেরিফেরাল শীর্ষবিন্দু হল একটি শীর্ষবিন্দু যা ব্যাস উৎপন্ন করে।
সিমর্যাঙ্ক − র্যান্ডম ওয়াক এবং স্ট্রাকচারাল প্রেক্ষাপটের উপর ভিত্তি করে সাদৃশ্য − বিভিন্ন অ্যাপ্লিকেশানে, গ্রাফে শীর্ষবিন্দুর মধ্যে সাদৃশ্য গণনা করার ক্ষেত্রে জিওডেসিক দূরত্ব অনুপযুক্ত হতে পারে। SimRank-এ, একটি সাদৃশ্য পরিমাপ এলোমেলো হাঁটার উপর এবং গ্রাফের মৌলিক কাঠামোর উপর নির্ভর করে। গণিতে, একটি এলোমেলো হাঁটা হল একটি ট্র্যাজেক্টোরি যার মধ্যে ধারাবাহিক এলোমেলো প্রক্রিয়া নেওয়া অন্তর্ভুক্ত।
সাদৃশ্য উপস্থাপন করার দুটি পদ্ধতি রয়েছে যা নিম্নরূপ -
-
সোশ্যাল ওয়েবে একই প্রতিবেশী থাকলে দুজন ব্যবহারকারীকে একে অপরের সাথে একই আচরণ করা হয়। এই হিউরিস্টিকটি উপলব্ধিযোগ্য কারণ দুটি ব্যক্তি যে বিপুল সংখ্যক সাধারণ বন্ধুদের কাছ থেকে সুপারিশ গ্রহণ করে তারা একই সিদ্ধান্ত গ্রহণ করে। এই ধরনের সাদৃশ্য শীর্ষবিন্দুগুলির স্থানীয় কাঠামোর (যেমন, আশেপাশের) উপর নির্ভর করে এবং এটি কাঠামোগত প্রসঙ্গ-ভিত্তিক সাদৃশ্য হিসাবে পরিচিত।
-
ধরুন AllElectronics সোশ্যাল ওয়েবে অ্যাডা এবং বব উভয়কেই প্রচারমূলক ডেটা পাঠায়। অ্যাডা এবং বব এলোমেলোভাবে নেটওয়ার্কে তাদের বন্ধুদের (বা প্রতিবেশীদের) কাছে এই ধরনের ডেটা ফরোয়ার্ড করতে পারে। অ্যাডা এবং বব-এর মধ্যে ঘনিষ্ঠতা এই সম্ভাবনার দ্বারা গণনা করা যেতে পারে যে একই সময়ে বিভিন্ন ব্যবহারকারী প্রচারমূলক ডেটা গ্রহণ করে যা প্রাথমিকভাবে অ্যাডা এবং ববকে পাঠানো হয়েছিল৷ এই ধরনের সাদৃশ্য নির্ভর করে ওয়েবে র্যান্ডম ওয়াক নাগালের উপর, এবং তাই র্যান্ডম ওয়াকের উপর ভিত্তি করে সাদৃশ্য হিসাবে সংজ্ঞায়িত করা হয়।
