दो प्रकार के उपाय हैं जैसे कि भूगणितीय दूरी और यादृच्छिक चलने के आधार पर दूरी।
जियोडेसिक दूरी - ग्राफ़ में दो शीर्षों के बीच की दूरी का एक सरल माप, शीर्षों के बीच सबसे छोटा मार्ग है। आमतौर पर, दो शीर्षों के बीच की भूगणितीय दूरी, शीर्षों के बीच सबसे छोटे पथ के कई किनारों के संदर्भ में लंबाई होती है। दो शीर्षों के लिए जो ग्राफ़ में लिंक नहीं हैं, भूगणितीय दूरी को अनंत के रूप में दर्शाया जाता है।
जियोडेसिक दूरी का उपयोग करके, यह ग्राफ विश्लेषण और क्लस्टरिंग के लिए विभिन्न उपयोगी मापों का प्रतिनिधित्व कर सकता है। एक ग्राफ 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 =अधिकतम eccen(v)
v V
व्यास कुछ युग्मों के बीच की उच्चतम दूरी को परिभाषित करता है।
-
एक परिधीय शीर्ष एक शीर्ष है जो व्यास उत्पन्न करता है।
SimRank - रैंडम वॉक और स्ट्रक्चरल कॉन्टेक्स्ट पर आधारित समानता -विभिन्न अनुप्रयोगों में, ग्राफ़ में शीर्षों के बीच समानता की गणना करने में भूगणितीय दूरी अनुपयुक्त हो सकती है। सिमरैंक में, एक समानता माप यादृच्छिक चलने और ग्राफ के मौलिक ढांचे पर निर्भर करता है। गणित में, एक यादृच्छिक चलना एक प्रक्षेपवक्र है जिसमें क्रमिक यादृच्छिक प्रक्रिया शामिल है।
समानता का प्रतिनिधित्व करने के लिए दो तरीके हैं जो इस प्रकार हैं -
-
दो उपयोगकर्ताओं के साथ एक जैसा व्यवहार किया जाता है यदि सोशल वेब में उनके समान पड़ोसी हों। यह अनुमान बोधगम्य है क्योंकि बड़ी संख्या में आम मित्रों से सिफारिशें प्राप्त करने वाले दो व्यक्ति समान निर्णय लेते हैं। इस प्रकार की समानता शीर्षों की स्थानीय संरचना (अर्थात पड़ोस) पर निर्भर करती है, और इसे संरचनात्मक संदर्भ-आधारित समानता के रूप में जाना जाता है।
-
मान लीजिए AllElectronics सामाजिक वेब में Ada और Bob दोनों को प्रचार डेटा भेजता है। अदा और बॉब इस तरह के डेटा को नेटवर्क में अपने दोस्तों (या पड़ोसियों) को बेतरतीब ढंग से अग्रेषित कर सकते हैं। Ada और Bob के बीच निकटता की गणना इस संभावना से की जा सकती है कि अलग-अलग उपयोगकर्ता एक ही समय में प्रचार डेटा प्राप्त करते हैं जो शुरुआत में Ada और Bob को भेजा गया था। इस प्रकार की समानता वेब पर रैंडम वॉक रीचैबिलिटी पर निर्भर करती है, और इसलिए इसे रैंडम वॉक पर आधारित समानता के रूप में परिभाषित किया गया है।