साइंसहब # 04: रैंडम ग्राफ थ्योरी

एडिटर-इन-चीफ के नेतृत्व में पोस्टन्यूका का फिल्म क्रू कहीं भी नहीं गया, लेकिन यह देखने के लिए यांडेक्स के पास है कि आधुनिक प्रौद्योगिकियों की दुनिया में मौलिक विज्ञान ने किस तरह से मूल्य लागू किया है। हम शारीरिक और गणितीय विज्ञान के डॉक्टर आंद्रेई रैगोरोड्स्की से मिले, यैंडेक्स के सैद्धांतिक और व्यावहारिक अनुसंधान विभाग के प्रमुख और मास्को स्टेट यूनिवर्सिटी और मास्को इंस्टीट्यूट ऑफ फिजिक्स एंड टेक्नोलॉजी में प्रोफेसर हैं।

परिचय

एक संदेह है कि राबेरोडस्की के अपने भाषण में यहां बताने की कोशिश की जा रही है। शायद, होमवर्क करने वाले इसे समझते हैं और इसे दोहराए जाने की आवश्यकता नहीं है। इसलिए, खाली से खाली करने के लिए अतिप्रवाह नहीं करने के लिए, मैं एंड्री के उद्धरण उद्धृत करूंगा, और आप उन्हें टिप्पणियों में जोड़ सकते हैं।

आंद्रेई रैगोरोड्स्की: "एक व्यक्ति के लिए जो एक ग्राफ क्या है, यह बिल्कुल नहीं जानता है, यह बहुत विशिष्ट शब्दों में बताना सही है। कल्पना करें कि आपके पास एक बड़ा स्थानिक अणु है, जिसमें कठोर गेंदें हैं, चाहे वे (कार्डबोर्ड, धातु) से बने हों। और ये गोले आपस में जुड़े होते हैं, जो कि तारों, रेक्टिलाइनियर सेगमेंट से जुड़े होते हैं। यह एक कठोर संरचना का पता लगाता है, जिसे गणित में आमतौर पर ग्राफ कहा जाता है। यह एक विशुद्ध रूप से दृश्य व्याख्या है - एक अणु के रूप में। हालांकि मुझे लगता है कि यह किसी को भी सुविधाजनक लगता है जो यह कल्पना करने की कोशिश कर रहा है कि ग्राफ क्या है।

संक्षेप में, ग्राफ को इस तरह से व्यवस्थित किया गया है - इसमें कई कोने और कई किनारे हैं। वास्तव में, वे गेंदें जिन्हें हम अंतरिक्ष में देखते हैं वे ग्राफ के कोने हैं। और उन्हें जोड़ने वाले तार ग्राफ के किनारों हैं। सार शब्दों में बोलते हुए, वर्टिकल कुछ तत्वों के केवल कुछ परिमित सेट होते हैं।

कोई फर्क नहीं पड़ता कि ये तत्व क्या प्रकृति हैं। यह लोग हो सकते हैं, उदाहरण के लिए, जिनके बीच किसी प्रकार का संबंध है। यह प्राकृतिक संख्याएं हो सकती हैं, इंटरनेट पर साइटें, जैविक वस्तुएं, उदाहरण के लिए, प्रोटीन। कुछ प्रकार के पूरी तरह से सार तत्व हो सकते हैं।

पसलियां जो कुछ जोड़े को जोड़ती हैं, इन तत्वों की एक जोड़ी का सार है। यही है, हम कहते हैं कि दो तत्व एक किनारे से जुड़े हुए हैं। और वह यह है। प्रत्येक दो तत्वों के बारे में हम कह सकते हैं कि वे एक किनारे से जुड़े हुए हैं या नहीं। लेकिन यह इस बात पर निर्भर करता है कि हम कैसे परिभाषित करते हैं।
एक अमूर्त स्थिति में, हम आपकी तरह परिभाषित कर सकते हैं, बस तत्वों का एक सीमित सेट और किनारों से जुड़ते हुए इन तत्वों के कुछ जोड़े। परिणाम अंतरिक्ष में एक संरचना है, उदाहरण के लिए, स्थित या विमान पर। जैसा कि आप इसे आकर्षित करते हैं, ऐसा ही होगा। ”



“19 वीं शताब्दी में, एक शास्त्रीय रूप से प्रस्तुत कार्य था जो मानचित्रों के रंग से संबंधित था। यहां आपके पास दुनिया का नक्शा है। कुछ देश इस पर चित्रित हैं। स्वाभाविक रूप से, आपको प्रत्येक देश को एक निश्चित रंग में रंगने की आवश्यकता है ताकि एक-दूसरे को सीमा पर रखने वाले देश अलग-अलग रंगों के हों। यदि वे एक ही रंग हैं, तो वे बस एक साथ विलीन हो जाते हैं। और आप उन्हें अलग नहीं कर सकते। सवाल यह है कि इस तरह की पेंटिंग को अंजाम देने के लिए कितने रंगों की आवश्यकता थी?

परिकल्पना यह थी कि इन देशों की सीमाओं और उनके सापेक्ष पदों के गुणों के बारे में कुछ प्राकृतिक प्रतिबंधों को पूरा करने पर चार रंग हमेशा पर्याप्त होंगे। यदि कैलिनिनग्राद जैसे कोई एन्क्लेव नहीं हैं, तो मानचित्र को सही माना जाता है, मोटे तौर पर बोलना। और मैं किसी तरह इसे चार रंगों में रंगना चाहता हूं। यह स्वाभाविक रूप से ग्राफ सिद्धांत के साथ जुड़ा हुआ है। हम बस प्रत्येक देश को एक सार चोटी प्रदान करते हैं (यदि आप चाहें, तो इसकी पूंजी)। और आप ग्राफ के ऊपर - इन देशों की राजधानी प्राप्त करते हैं।

इसके अलावा, हम किनारे से जुड़ते हैं (यदि आप महंगा चाहते हैं) दो राजधानियां, जो उन देशों के मुख्य शहर हैं जो एक-दूसरे को सीमाबद्ध करते हैं। हमें एक ग्राफ मिलता है। इसकी चोटियाँ देशों के अनुरूप हैं। पसलियां चोटियों के जोड़े हैं जो पड़ोसी देशों की राजधानियों के अनुरूप हैं। और हम इस ग्राफ (अर्थात, देश) को कम से कम रंगों में रंगना चाहते हैं ताकि किनारे से जुड़े कोने अलग-अलग रंगों में रंगे जा सकें। चार रंगों का कार्य एक महान क्लासिक समस्या है जो अभी तक पूरी तरह से हल नहीं हुई है। यह कंप्यूटर खोज की मदद से हल किया गया है, लेकिन अभी भी कोई मैनुअल नहीं है, विशुद्ध रूप से विश्लेषणात्मक प्रमाण है कि चार रंग हमेशा पर्याप्त होते हैं। ”

दुर्घटना

यादृच्छिक रेखांकन की दिशा अब गणित में सबसे दिलचस्प में से एक है। यह Erds-Renyi सिद्धांत के साथ जुड़ा हुआ है, इन हंगेरियाई गणितज्ञों ने ग्राफ़ की भीड़ पर यादृच्छिकता का परिचय दिया।

AR: "उन्होंने यह कहा:" चलो n से कुछ निश्चित सेट पर विचार करें। चोटियों, कोई फर्क नहीं पड़ता कि इसमें क्या है। उसे सार n होने दो। वस्तुओं। उदाहरण के लिए, प्राकृतिक संख्या 1, 2 ... n। हम उनके बीच बेतरतीब ढंग से पसलियां खींचना चाहते हैं। ”
यह स्पष्ट है कि वहाँ कितने पसलियाँ हैं। लेकिन हर दो कोने संभावित रूप से एक किनारे से जुड़े हो सकते हैं। चलो कुछ दो चोटियाँ लें - एक सिक्का फेंक दें। हालांकि, गुरुत्वाकर्षण के विस्थापित केंद्र के साथ सिक्का। यह सैद्धांतिक रूप से या व्यावहारिक रूप से (मुझे नहीं पता कि कैसे कहना सबसे अच्छा है, लेकिन यह कहने का सबसे सही तरीका सांख्यिकीय है) "ईगल" को पूंछ की तुलना में अधिक बार गिरता है। जब आप इसे टेबल पर फेंकते हैं, तो संभावना है कि यह "ईगल" ऊपर गिर जाएगा यह संभावना नहीं है कि यह पूंछ गिर जाएगी। यही है, अगर सिक्का पूरी तरह से सजातीय सामग्री से बना था, तो यह निश्चित रूप से नहीं हुआ होगा। औसतन, आधा समय यह ऊपर गिरता है, आधा समय एक बाज। यह उम्मीद करना काफी स्वाभाविक है। लेकिन हमारे पास एक खराब सिक्का है। संभावना है कि वह पूंछ से गिर जाएगी अंतराल 0 से कुछ संख्या पी है। - 1. और संभावना है कि वह "ईगल" द्वारा गिर जाएगी, क्रमशः, 1 - पी है, क्योंकि, निश्चित रूप से, हम मानते हैं यह सिक्का इसके किनारे पर नहीं पड़ता है - यह किनारे पर नहीं मिलता है और हवा में लटका नहीं है। यही है, केवल दो संभावनाएं हैं: या तो यह "ईगल" ऊपर गिरता है या यह पूंछ ऊपर गिरता है।

आइए हम मान लें कि यदि यह एक संभाव्यता आर के साथ ऊपर की ओर झुका हुआ है, तो जब एक पूंछ बाहर निकलती है, तो हम क्रमशः, हमारे द्वारा तय किए गए कोने के बीच एक किनारा खींचते हैं। और अगर हम भाग्यशाली नहीं थे, वह एक चील गिर गई, तो पसलियां दिखाई नहीं देंगी। और इसलिए हम प्रत्येक जोड़ी के साथ करते हैं जो हमारे पास है। हमने एन। कोने। और हम इस तरह के सिक्के की मदद से प्रत्येक जोड़ी का परीक्षण करते हैं। इसे विज्ञान में (प्रायिकता सिद्धांत में) बर्नौली परीक्षण योजना कहा जाता है। हम सिर्फ एक सिक्का को कई बार फेंकते हैं और हर बार इसे ठीक करते हैं - यह पूंछ या "ईगल" ऊपर गिर गया। इस पर निर्भर करते हुए, या तो हम एक और धार खींचने का फैसला करते हैं - यह कोने के बीच का संबंध है, या हम इसे संचालित नहीं करने का निर्णय लेते हैं। नतीजतन, हम, निश्चित रूप से, एक यादृच्छिक ग्राफ प्राप्त करते हैं - वह है, एक ग्राफ जिसका किनारा संयोग से एक सिक्का उछालने के परिणामस्वरूप उत्पन्न हुआ है। इस तरह के रेखांकन को शास्त्रीय या Erds-Renyi रेखांकन कहा जाता है। "



बिजली कानून

“यादृच्छिक रेखांकन के सिद्धांत में कई समस्याएं हैं। हम यादृच्छिक ग्राफ के समान रंगीन संख्या के बारे में बात कर सकते हैं। एक बहुत ही सुंदर दिलचस्प विज्ञान है कि एरड्यून्स-रेनी मॉडल के अनुसार एक यादृच्छिक ग्राफ की वर्णक्रमीय संख्या कैसे व्यवहार करती है। व्यावहारिक कार्य जो यादृच्छिक रेखांकन के दृष्टिकोण से बहुत दिलचस्प हैं, यादृच्छिक ग्राफ़ के पर्याप्त मॉडल के निर्माण के कार्य हैं जो कुछ वास्तविक नेटवर्क के व्यवहार का वर्णन करते हैं।
वास्तविक नेटवर्क को समझा जा सकता है, उदाहरण के लिए, इंटरनेट के रूप में, जिनके कोने (व्याख्या के आधार पर) या तो साइटें, या पृष्ठ, या कुछ अन्य संरचनात्मक इकाइयाँ हैं। और पसलियां आमतौर पर हाइपरलिंक होती हैं। यह एक भारी वस्तु को बदल देता है जो समय के साथ बदलता है। ग्राफ किसी तरह विकसित हो रहा है। नई साइटें दिखाई देती हैं, उनके बीच नए कनेक्शन दिखाई देते हैं।
यदि हम स्थानिक व्याख्या पर लौटते हैं, तो हमें एक अणु मिलता है जो समय के साथ बढ़ता है, इसमें कुछ, इसके विपरीत, गायब हो जाता है, ढह जाता है। कनेक्शन गायब हो जाते हैं, नए दिखाई देते हैं।

यह पता चलता है कि एक अणु जो उदाहरण के लिए, इंटरनेट का वर्णन करता है या कुछ जैविक नेटवर्क, परिवहन नेटवर्क, नेटवर्क का वर्णन करता है जो समाजशास्त्र में उत्पन्न होते हैं, बेतरतीब ढंग से नहीं बदलते हैं, लेकिन कुछ दिलचस्प सांख्यिकीय कानूनों का पालन करते हैं। आप एक तरफ, अभ्यास में निरीक्षण कर सकते हैं कि ये पैटर्न कैसे काम करते हैं, और दूसरी तरफ, यादृच्छिक ग्राफ़ के पर्याप्त मॉडल के साथ आने की कोशिश करें जो शास्त्रीय मॉडल से अलग हैं (क्योंकि शास्त्रीय मॉडल अभी भी इसका वर्णन नहीं करते हैं) जो कि सबसे अधिक संभावना है वही गुण जो हमने व्यवहार में देखे।

उदाहरण के लिए, यह ज्ञात है। इंटरनेट पर वर्टिकल की डिग्रियों का वितरण क्या है, अर्थात मोटे तौर पर, इंटरनेट ग्राफ में बेतरतीब ढंग से चयनित वर्टेक्स की संभावना है कि किनारों की संख्या का एक पूर्व निर्धारित डिग्री है जो इससे जुड़े हुए हैं। यह वितरण बहुत विशिष्ट तरीके से व्यवहार करता है। इसे पावर लॉ कहा जाता है। ”

स्पैम के साथ क्या करना है

“कल्पना कीजिए कि आपके पास कुछ प्रकार के यादृच्छिक ग्राफ़ मॉडल हैं जो वास्तव में बहुत पर्याप्त रूप से और अच्छी तरह से इंटरनेट का वर्णन इस अर्थ में करते हैं कि, इसकी संभाव्य विशेषताओं के संदर्भ में, यह पूरी तरह से इंटरनेट से अनुभवजन्य रूप से प्राप्त आंकड़ों को फिट बैठता है। यही है, हम जानते हैं कि कुछ कानूनों के अनुसार एक वेब ग्राफ विकसित हो रहा है। और, लो और निहारना, हम एक यादृच्छिक ग्राफ के एक मॉडल के साथ आए, जिसमें एक उच्च संभावना के साथ, इन सभी कानूनों को पूरा किया जाता है। यह एक मुश्किल काम है, लेकिन आंशिक रूप से हल किया गया है। हमारे पास पहले से ही कुछ पहला अनुमान है कि कैसे इंटरनेट के व्यवहार को ठीक से मॉडल किया जाए। कल्पना कीजिए कि यह पूरी तरह से हल है।

उदाहरण के लिए, हमारे पास एक आदर्श मॉडल है जो भविष्यवाणी करता है कि अगर कोई बाहरी गलत प्रभाव नहीं है तो इंटरनेट को कैसे व्यवहार करना चाहिए। अब आइए कल्पना करें कि हमें किसी प्रकार के स्पैम को पकड़ने की आवश्यकता है जिसे लिंक चरित्र कहा जाता है। स्पैम की लिंक प्रकृति को निम्नानुसार संरचित किया गया है - दुर्भावनापूर्ण ऑप्टिमाइज़र द्वारा निर्मित कुछ संरचना है।

संरचना, स्वाभाविक रूप से, यह सुनिश्चित करने के लिए डिज़ाइन की गई है कि जो साइटें इस संरचना के अंदर हैं, वे खोज प्रक्रिया में ढूंढना आसान हैं। यानी आप किसी तरह की खोज क्वेरी पूछ रहे हैं। आप इसका पर्याप्त उत्तर चाहते हैं। और स्पैमर यह सुनिश्चित करने का प्रयास करते हैं कि आपको इसका उत्तर मिल जाए, उन साइटों से मिलकर जो स्पैमर से दिलचस्प हैं। और वे जारी करने में इन साइटों को कृत्रिम रूप से हवा देते हैं। विशेष रूप से, एक महत्वपूर्ण मुद्दा कारक, निश्चित रूप से, इस साइट के लिंक की संख्या या उन लोगों के कुछ उद्धरणों की संख्या है जो आपको और इतने पर उद्धृत करते हैं।
संरचना के चारों ओर ग्राफ की स्थानीय संरचना को देखना महत्वपूर्ण है जिसे स्पैमर ने बनाया हो सकता है। एक नियम के रूप में, वे संरचनाओं का निर्माण करते हैं जो वास्तव में कसकर पर्याप्त रूप से लिंक किए जाते हैं ताकि खोज इंजन को मूर्ख बनाया जा सके। खोज इंजन सोचेंगे, “ओह, यह एक अच्छी साइट है। वास्तव में ऐसी साइटें हैं जो अत्यधिक उद्धृत हैं। इसलिए, उन्हें मुद्दे के शीर्ष तक दिया जाना चाहिए। ” और इसलिए स्पैमर जीत जाते हैं।

हम क्या कर सकते हैं? हम कुछ एल्गोरिथ्म का उपयोग कर सकते हैं (स्वाभाविक रूप से, मैं यह नहीं कह रहा हूं कि कौन सा) कई को पकड़ने के लिए, कई संरचनाएं जो संभावित रूप से खराब हो सकती हैं, अर्थात्, काफी घनी, सघन रूप से परस्पर जुड़ी हुई। और फिर देखो: दुनिया के इस आदर्श मॉडल में, जिसे हम ग्राफ सिद्धांत और संभाव्यता सिद्धांत का उपयोग करके आए थे, प्रत्येक विशिष्ट संरचना की उपस्थिति (एल्गोरिदम का उपयोग करके पाए जाने वाले) की उच्च संभावना या कम है?

यदि, यादृच्छिक ग्राफ मॉडल के दृष्टिकोण से, जिसे एक उचित इंटरनेट के व्यवहार का वर्णन करने के लिए डिज़ाइन किया गया है, तो ऐसी संरचना की संभावना अधिक है, फिर स्पैमर का डिज़ाइन, संभवतः, इसे किसी भी तरह से कम नहीं कर सकता है। उसे दूर जाने के लिए वेटिंग स्थानों को असाइन करने की कोई आवश्यकता नहीं है। और अगर हमारे आदर्श मॉडल के ढांचे के भीतर उसकी संभावना बेहद कम है, तो हमें पहले से ही किसी तरह उस पर संदेह करने की जरूरत है। हो सकता है कि उसने रैंकिंग में किसी तरह का झंडा लगाया हो, ताकि वह दिखाई न दे, शायद उच्चतम स्थिति पर। या शायद प्रतिबंधित कर दिया गया। आपको अपनी आंखों से देखना होगा। अगर वह वास्तव में बुरा है, तो आइए प्रतिबंध लगाते हैं। ऐसी कई संरचनाएँ नहीं हैं। क्यों नहीं? लेकिन यह सब स्वचालित रूप से किया जा सकता है, इस उम्मीद का लाभ उठाते हुए कि हमारे पास एक अच्छे मॉडल और वास्तविकता के ढांचे के भीतर है। यही है, वास्तव में, किनारों की संख्या (लिंक) और इसी तरह। यहां मैं कोई राज नहीं खोलता। ये बहुत ही स्वाभाविक चीजें हैं। ”



भविष्य स्पैम पकड़ने वालों: यह कौन है?

ग्राफ़ थ्योरी और इंटरनेट और नई तकनीकों से जुड़ी समस्याओं के समाधान के लिए, हमें ऐसे वैज्ञानिकों की ज़रूरत है जो कॉम्बिनेटरिक्स और ग्राफ़ थ्योरी, प्रायिकता सिद्धांत और यादृच्छिक प्रक्रियाओं में शामिल हों। प्रयोगशालाएं अब दुनिया भर में खुल रही हैं, और विश्वविद्यालय इस क्षेत्र पर बहुत जोर दे रहे हैं। इसके अलावा, जैव सूचना विज्ञान भी इसके साथ जुड़ा हुआ है। हमने पहले से ही जीवविज्ञानियों द्वारा प्राप्त आंकड़ों के भंडारण और प्रसंस्करण के कार्य के बारे में बात की है, अधिक सटीक रूप से, सूक्ष्म जीवविज्ञानी कोंस्टेंटिन सेवरिनोव।
ऐसे विशेषज्ञों को न केवल इंटरनेट पर, सूचना के नियंत्रण और प्रसार के संबंध में, बल्कि बैंकिंग संस्थानों में, वित्तीय संकटों के मुद्दों के अध्ययन में भी आवश्यक है, जो यादृच्छिक ग्राफ़ के सिद्धांत से भी जुड़े हैं।

आंद्रेई रैगरोडस्की: “मैं आपको संक्षेप में बताऊंगा कि यैंडेक्स में मेरा विभाग वास्तव में क्या करता है। यह एक काफी बड़ा विभाग है, जो अब तीस से अधिक शोधकर्ताओं और डेवलपर्स को रोजगार देता है। यह इस तरह से बनाया गया है कि विभाग का एक महत्वपूर्ण हिस्सा है जो यैंडेक्स उत्पाद भाग में बनाया गया है, और यह प्रत्यक्ष डेवलपर्स से अपने कार्यों का हिस्सा प्राप्त करता है - उन लोगों से, जो खोज करते हैं, जो मुख्य रूप से एक खोज के रूप में यांडेक्स के लिए दिलचस्प हैं। सिस्टम, कुछ सेवाओं का निर्माण करता है। ये लोग विशुद्ध रूप से गणितीय प्रकृति के नहीं, बल्कि इसके विपरीत, सार्थक परियोजनाओं के कार्यान्वयन के लिए कुछ गणितीय विचारों को लागू करने की कोशिश में लगे हुए हैं।

और विभाग का एक टुकड़ा है, जो वास्तव में, इस तरह के विचारों को उत्पन्न करता है। यही है, सब कुछ काफी प्राकृतिक तरीके से बनाया गया है। एक टुकड़ा है जो सीधे बिक्री पर है। एक टुकड़ा है जो विचारों की पीढ़ी, औद्योगिक सम्मेलनों और शुद्ध गणितीय सामग्री की पत्रिकाओं में दोनों के वैज्ञानिक प्रकाशनों का उत्पादन करता है। और यहां अनुसंधान के मुख्य क्षेत्र हैं जो हम आचरण करते हैं? बेशक, हम रेखांकन में बहुत रुचि रखते हैं। और हम विभिन्न ग्राफ़ के मॉडल बनाते हैं जो वेब का पर्याप्त वर्णन करते हैं। शायद, हम अभी तक सही मॉडल बनाने में कामयाब नहीं हुए हैं। लेकिन इस दिशा में हमारी काफी अच्छी प्रगति है। हमें ऐसे मॉडल मिलते हैं जो वास्तव में वेब के व्यवहार का पर्याप्त वर्णन करते हैं। जैसा कि मैंने कहा, वे भी अभ्यास में लाने का प्रबंधन करते हैं।
मशीन लर्निंग के अध्ययन से संबंधित एक दिशा है। यादृच्छिक रेखांकन के अमूर्त सिद्धांत की समस्याओं से संबंधित एक दिशा है। "

आप एंड्री को सुन सकते हैं और लिंक पर यैंडेक्स के अंदरूनी हिस्सों को देख सकते हैं ।