🔬 condensed matter

The distribution of eccentricities in random regular graphs

यह शोधपत्र रैंडम रेगुलर ग्राफ में विकेंद्रता (eccentricities) के पूर्ण वितरण के लिए एक क्लोज्ड-फॉर्म विश्लेषणात्मक अभिव्यक्ति व्युत्पन्न करता है, जो समान डिग्री के बावजूद नोड विकेंद्रताओं में गैर-तुच्छ विविधताओं को प्रकट करता है और माध्य, बहुलक तथा प्रसरण के सटीक सूत्र प्रदान करता है जो बड़े विरल नेटवर्क (large sparse networks) के विश्लेषण के लिए बेंचमार्क के रूप में कार्य करते हैं।

मूल लेखक: Dor Lev-Ari, Ofer Biham, Eytan Katzav

प्रकाशित 2026-07-17

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Dor Lev-Ari, Ofer Biham, Eytan Katzav

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

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

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

उन्होंने यहाँ क्या खोजा, आइए देखते हैं। सबसे पहले, उन्होंने एक सटीक सूत्र (formula) निकाला जो यह भविष्यवाणी करता है कि किसी घर की 'एक्सेन्ट्रिसिटी' क्या होगी। इसे एक मौसम पूर्वानुमान की तरह समझें, लेकिन बारिश के बजाय, यह भविष्यवाणी करता है कि एक घर शहर की सीमाओं से कितनी दूर है। उन्होंने पाया कि यह वितरण एक आकार का पालन करता है जिसे 'गमबेल डिस्ट्रीब्यूशन' (Gumbel distribution) के नाम से जाना जाता है (यह चरम स्थितियों से निपटने वाले एक विशिष्ट प्रकार के बेल कर्व का एक फैंसी नाम है)। उनके द्वारा बनाए गए सूत्र में तीन मुख्य सामग्रियां हैं: शहर का आकार ( $N$ ), प्रत्येक घर में सड़कों की संख्या ( $c$ ), और कुछ गणितीय स्थिरांक (constants)।

उनकी खोज का सबसे दिलचस्प हिस्सा यह है कि जैसे-जैसे शहर बढ़ता है, "सामान्य" दूरी कैसे व्यवहार करती है। यदि आप सबसे आम दूरी को शहर के आकार के विरुद्ध दर्शाते हैं, तो यह एक ढलान की तरह सुचारू रूप से ऊपर नहीं बढ़ती है। इसके बजाय, यह एक सीढ़ी की तरह दिखती है। कुछ समय के लिए, सबसे आम दूरी, मान लीजिए 5 कदम पर रहती है। फिर, जैसे ही शहर थोड़ा सा बड़ा होता है, यह अचानक 6 कदमों पर कूद जाती है, वहाँ कुछ समय के लिए रुकती है, और फिर 7 कदमों पर कूद जाती है। लेखक इस वितरण के शिखर को "मोड" (mode) कहते हैं। उन्होंने सिद्ध किया कि यह सीढ़ी हमेशा "औसत" दूरी के निकटतम पूर्णांक (whole number) होती है। इसलिए, यदि गणित कहता है कि औसत दूरी 5.8 है, तो लगभग सभी के लिए सबसे आम दूरी 6 होगी।

उन्होंने यह भी देखा कि ये दूरियाँ कितनी भिन्न होती हैं। एक सुचारू, निरंतर दुनिया में, आप उम्मीद कर सकते हैं कि भिन्नता बहुत कम होगी। लेकिन क्योंकि एक शहर में दूरियों को पूरे कदमों में गिना जाता है (आप 5.5 कदम नहीं चल सकते), इसलिए जैसे-जैसे शहर बढ़ता है, यह भिन्नता एक हृदय की धड़कन की तरह ऊपर-नीचे होती रहती है। जब शहर 5 से 6 की दूरी पर जाने वाला होता है, तो भिन्नता अपने उच्चतम स्तर पर पहुँच जाती है क्योंकि कुछ घर अभी भी 5 पर अटके हुए हैं जबकि अन्य 6 तक पहुँच चुके हैं। इन "टिपिंग पॉइंट्स" (निर्णायक बिंदुओं) पर, भिन्नता लगभग 0.25 होती है, जो कि एक सिक्के के उछाल वाले परिदृश्य के लिए अधिकतम संभव है जहाँ आधे घर एक दूरी पर हैं और आधे अगले स्तर पर।

शोधकर्ताओं ने अपने गणित का परीक्षण करने के लिए इन शहरों के कंप्यूटर सिमुलेशन चलाए, जिसमें विभिन्न आकारों के हजारों नेटवर्क बनाए गए। उन्होंने पाया कि उनके सूत्र कंप्यूटर के परिणामों से पूरी तरह मेल खाते हैं, विशेष रूप से जब शहर बड़े हो जाते हैं। उदाहरण के लिए, एक शहर जहाँ हर घर में 5 सड़कें ( $c=5$ ) हैं, जब शहर में लगभग 160 घर होते हैं, तो लगभग हर कोई किनारे से 5 कदम दूर होता है। लेकिन जैसे ही यह शहर बढ़कर 440 घर हो जाता है, अचानक लगभग हर कोई 6 कदम की दूरी पर होता है।

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

तकनीकी सारांश: रैंडम रेगुलर ग्राफ में विलक्षणता (Eccentricities) का वितरण

समस्या विवरण
रैंडम रेगुलर ग्राफ (RRGs), जहाँ प्रत्येक नोड का समान डिग्री $c$ होता है, नेटवर्क सिद्धांत में एक मौलिक समूह हैं। जबकि इन ग्राफों की स्थानीय संरचना समान डिग्री वितरण द्वारा परिभाषित होती है, उनकी बड़े पैमाने की संरचना लघुतम पथ लंबाई के वितरण (DSPL) और नोड विलक्षणता (eccentricity) द्वारा लक्षित होती है। एक नोड की विलक्षणता को उस नोड से नेटवर्क के किसी भी अन्य नोड की अधिकतम दूरी के रूप में परिभाषित किया जाता है। यद्यपि सभी नोड्स की डिग्री समान होती है, फिर भी विलक्षणता में गैर-तुच्छ (non-trivial) भिन्नताएं दिखाई देती हैं। यह शोध पत्र विलक्षणता के पूर्ण वितरण (DoE) के लिए एक बंद-रूप विश्लेषणात्मक अभिव्यक्ति (closed-form analytical expression) के अभाव को संबोधित करता है, यह देखते हुए कि मौजूदा साहित्य अक्सर पूर्ण सांख्यिकीय वितरण के बजाय एकल विशिष्ट लंबाई पैमानों (जैसे माध्य या व्यास) पर ध्यान केंद्रित करता है। विलक्षणता के वितरण (DoE) को समझना ब्रॉडकास्टिंग और वैश्विक प्रसार जैसे व्यावहारिक अनुप्रयोगों के लिए महत्वपूर्ण है, जहाँ नेटवर्क प्रदर्शन सबसे खराब स्थिति वाले विलंब समय (अधिकतम विलक्षणता) द्वारा निर्धारित होता है।

कार्यप्रणाली
लेखक $N$ नोड्स और $c \ge 3$ डिग्री वाले RRGs के लिए DoE प्राप्त करने हेतु एक्सट्रीम वैल्यू थ्योरी (extreme value theory) की विधियों का उपयोग करते हैं। व्युत्पत्ति निम्नलिखित चरणों में आगे बढ़ती है:

DSPL में आधार: अध्ययन DSPL की पूंछ (tail) के ज्ञात बंद-रूप विश्लेषणात्मक अभिव्यक्ति $P(L > \ell)$ का उपयोग करता है, जो एक विविक्त गोम्पर्ट वितरण (discrete Gompertz distribution) का अनुसरण करती है।
एक्सट्रीम वैल्यू थ्योरी का अनुप्रयोग: एक नोड की विलक्षणता को अन्य $N-1$ नोड्स की दूरियों के अधिकतम मान के रूप में मानते हुए, लेखक DoE को मॉडल करते हैं। पर्याप्त बड़े नेटवर्क में दूरियों के बीच कमजोर सहसंबंध (weak correlations) मानते हुए, अधिकतम का संचयी वितरण (cumulative distribution) अंतर्निहित DSPL के टेल वितरण का उपयोग करके अनुमानित किया जाता है।
विश्लेषणात्मक व्युत्पत्ति: एक्सट्रीम वैल्यू फ्रेमवर्क में DSPL टेल को प्रतिस्थापित करके, लेखक विलक्षणताओं के टेल वितरण $P(E > \ell)$ के लिए एक बंद-रूप अभिव्यक्ति प्राप्त करते हैं।
सांख्यिकीय क्षण (Statistical Moments): टेल-सम फॉर्मूला और यूलर-मैकरोनि समेशन तकनीक का उपयोग करके, लेखक माध्य विलक्षणता $\langle E \rangle$ , मोड $E_{\text{mode}}$ , और प्रसरण $\text{Var}(E)$ के लिए बंद-रूप अभिव्यक्तियाँ प्राप्त करते हैं।
सत्यापन: विश्लेषणात्मक परिणामों को स्टब-मैचिंग प्रक्रिया के माध्यम से उत्पन्न किए गए और स्वयं-लूप (self-loops) तथा बहु-किनारों (multiple edges) को समाप्त करने के लिए एज-स्विचिंग प्रक्रिया द्वारा परिष्कृत किए गए RRGs के कंप्यूटर सिमुलेशन के विरुद्ध सत्यापित किया गया। सिमुलेशन को विभिन्न आकार $N$ और डिग्री $c$ के लिए 1,000 नेटवर्क इंस्टेंस पर औसत निकाला गया।

प्रमुख योगदान और परिणाम

बंद-रूप वितरण (Closed-Form Distribution): प्राथमिक योगदान विलक्षणताओं के टेल वितरण का व्युत्पन्न है:
$P(E > \ell) \simeq 1 - \exp\left[ -\exp\left( -\frac{e^{b\ell} - \mu}{\beta} \right) \right]$
जहाँ $b = \ln(c-1)$ एक आकार पैरामीटर (shape parameter) है, $\beta = \frac{c-2}{c}N$ एक स्केल पैरामीटर है, और $\mu = \frac{c-2}{c}N \ln N$ एक लोकेशन पैरामीटर है। यह वितरण गंबल (Gumbel) वितरण के समान है लेकिन इसमें एक रैखिक तर्क के बजाय एक एक्सपोनेंशियल टर्म (exponential term) है।
माध्य विलक्षणता (Mean Eccentricity): माध्य विलक्षणता के लिए एक बंद-रूप अभिव्यक्ति प्राप्त की गई है:
$\langle E \rangle \simeq \frac{\ln N}{\ln(c-1)} + \frac{\ln \ln N}{\ln(c-1)} - \frac{\ln c - \ln(c-2)}{\ln(c-1)} + \frac{1}{2} + O\left(\frac{1}{\ln N}\right)$
लेखक नोट करते हैं कि जबकि सिमुलेशन परिणाम पूर्णांक मानों में स्थिर होते हैं, विश्लेषणात्मक अभिव्यक्ति एक सुचारू कंटूर (smoothed contour) प्रदान करती है जो स्केलिंग व्यवहार को स्पष्ट करती है।
मोड और सीढ़ीनुमा प्रोफाइल (Staircase Profile): DoE का मोड $E_{\text{mode}}$ , नेटवर्क आकार $N$ के फलन के रूप में एक सीढ़ीनुमा प्रोफाइल प्रदर्शित करता है। लेखक प्रदर्शित करते हैं कि मोड माध्य के निकटतम पूर्णांक है: $E_{\text{mode}} = \text{Round}(\langle E \rangle)$ । मोड के पूर्णांक मानों के बीच संक्रमण बिंदुओं को लैम्बर्ट $W$ फलन का उपयोग करके निर्धारित किया जाता है।
प्रसरण और दोलन (Variance and Oscillations): $\text{Var}(E)$ की गणना की गई है और दिखाया गया है कि यह $N$ के फलन के रूप में दोलन प्रदर्शित करता है। ये दोलन विलक्षणता की विविक्त प्रकृति से उत्पन्न होते हैं। प्रसरण उन स्टेप किनारों के पास चरम पर पहुँचता है जहाँ मोड $\ell$ से $\ell+1$ में बदल जाता है, और लगभग $1/4$ का अधिकतम मान प्राप्त करता है जब वितरण प्रभावी रूप से बाइनरी होता है ( $P(E=\ell) \approx P(E=\ell+1) \approx 1/2$ )।
परिमित-आकार प्रभाव (Finite-Size Effects): विश्लेषणात्मक परिणाम बड़े $N$ के लिए सिमुलेशन के साथ उत्कृष्ट सहमति दिखाते हैं। छोटे नेटवर्क में देखे गए विसंगतियों को परिमित-आकार प्रभावों, विशेष रूप से टेल वितरण के संक्रमण बिंदुओं के पास, के रूप में जिम्मेदार ठहराया गया है।

महत्व
यह शोध पत्र दावा करता है कि केवल एक एकल विशिष्ट लंबाई पैमाने के बजाय विलक्षणताओं का पूर्ण वितरण प्रदान करना, RRGs की बड़े पैमाने की संरचना का विस्तृत दृश्य प्रदान करता है। व्युत्पन्न विश्लेषणात्मक अभिव्यक्तियाँ बड़े स्पार्स (sparse) नेटवर्क में विलक्षणता गणना के एल्गोरिद्मिक दृष्टिकोण के लिए बेंचमार्क के रूप में कार्य करती हैं। परिणाम पुष्टि करते हैं कि समान डिग्री वाले नेटवर्क में भी, विलक्षणता काफी भिन्न होती है, और इन विविधताओं को व्युत्पन्न वितरण द्वारा पकड़ा जाता है। यह कार्य पुष्टि करता है कि DoE एक संकीर्ण वितरण है, जिसका अर्थ है कि नेटवर्क व्यास (अधिकतम विलक्षणता) और त्रिज्या (न्यूनतम विलक्षणता) के बीच का अंतर क्रम 1 (order 1) का है। लेखक निष्कर्ष निकालते हैं कि ये निष्कर्ष ब्रॉडकास्टिंग और वैश्विक प्रसार प्रोटोकॉल जैसे व्यावहारिक अनुप्रयोगों के लिए प्रासंगिक हैं जहाँ नेटवर्क प्रदर्शन सबसे लंबे विलंब समय द्वारा निर्धारित होता है।

इसी तरह के और पेपर