ग्राफ में दो शीर्षों के बीच समानता या दूरी मापना
दो प्रकार के माप हैं जैसे जियोडेसिक दूरी और यादृच्छिक चलन पर आधारित दूरी।
1. जियोडेसिक दूरी (Geodesic Distance)
ग्राफ में दो शीर्षों के बीच की दूरी का एक सरल माप शीर्षों के बीच सबसे छोटा मार्ग है। आमतौर पर, दो शीर्षों के बीच जियोडेसिक दूरी सबसे छोटे मार्ग की लंबाई है जो किनारों की संख्या के संदर्भ में है। दो शीर्षों के लिए जो ग्राफ में जुड़े नहीं हैं, जियोडेसिक दूरी को अनंत के रूप में दर्शाया जाता है।
जियोडेसिक दूरी का उपयोग करके, ग्राफ विश्लेषण और क्लस्टरिंग के लिए विभिन्न उपयोगी मापों को दर्शाया जा सकता है। एक ग्राफ 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। व्यास किसी भी जोड़ी के शीर्षों के बीच की उच्चतम दूरी को परिभाषित करता है।
- एक परिधीय शीर्ष एक शीर्ष है जो व्यास उत्पन्न करता है।
2. सिमरैंक - यादृच्छिक चलन और संरचनात्मक संदर्भ पर आधारित समानता (SimRank - Similarity Based on Random Walk and Structural Context)
विभिन्न अनुप्रयोगों में, ग्राफ में शीर्षों के बीच समानता की गणना में जियोडेसिक दूरी अनुचित हो सकती है। सिमरैंक में, एक समानता माप यादृच्छिक चलन और ग्राफ के मूलभूत ढांचे पर निर्भर करता है। गणित में, एक यादृच्छिक चलन एक प्रक्षेपवक्र है जिसमें क्रमिक यादृच्छिक प्रक्रिया शामिल होती है।
समानता दर्शाने के दो तरीके:
- संरचनात्मक संदर्भ-आधारित समानता: दो उपयोगकर्ताओं को एक-दूसरे के समान माना जाता है यदि सामाजिक वेब में उनके समान पड़ोसी हैं। यह अनुमान बोधगम्य है क्योंकि बड़ी संख्या में सामान्य दोस्तों से सिफारिशें प्राप्त करने वाले दो व्यक्ति समान निर्णय लेते हैं। इस प्रकार की समानता शीर्षों की स्थानीय संरचना (यानी, पड़ोस) पर निर्भर करती है, और इसे संरचनात्मक संदर्भ-आधारित समानता के रूप में जाना जाता है।
- यादृच्छिक चलन पहुंच योग्यता पर आधारित समानता: मान लीजिए AllElectronics सामाजिक वेब में एडा और बॉब दोनों को प्रचार डेटा भेजता है। एडा और बॉब नेटवर्क में अपने दोस्तों (या पड़ोसियों) को ऐसे डेटा को यादृच्छिक रूप से अग्रेषित कर सकते हैं। एडा और बॉब के बीच निकटता की गणना उस संभावना द्वारा की जा सकती है कि अलग-अलग उपयोगकर्ता एक ही समय में प्रचार डेटा प्राप्त करते हैं जो शुरू में एडा और बॉब को भेजा गया था। इस प्रकार की समानता वेब पर यादृच्छिक चलन पहुंच योग्यता पर निर्भर करती है, और इसलिए इसे यादृच्छिक चलन पर आधारित समानता के रूप में परिभाषित किया जाता है।
