2025-11-21T11:49:15.652907

Entropy of Random Geometric Graphs in High and Low Dimensions

Baker, Dettmann
We use a multivariate central limit theorem (CLT) to study the distribution of random geometric graphs (RGGs) on the cube and torus in the high-dimensional limit with general node distributions. We find that the distribution of RGGs on the torus converges to the Erd\H os-Rényi (ER) ensemble when the nodes are uniformly distributed, but that the distribution for RGGs with non-uniformly distributed nodes on the torus, and for RGGs with any distribution of nodes with kurtosis greater than 1 on the cube is different. In these cases, the distribution has a lower maximum entropy than the ER ensemble, but is still symmetric. Soft RGGs in either geometry converge to the ER ensemble. An Edgeworth correction to the CLT is then developed to derive the $\mathcal{O}\left(d^{-\frac{1}{2}}\right)$ sub-leading term of the Shannon entropy of RGGs in dimension for both geometries. We also provide numerical approximations of maximum entropy in low-dimensional hard and soft RGGs, and calculate exactly the entropy of hard RGGs with 3 nodes in the one-dimensional cube and torus.
academic

उच्च और निम्न आयामों में यादृच्छिक ज्यामितीय ग्राफ की एंट्रॉपी

मूल जानकारी

  • पेपर ID: 2503.11418
  • शीर्षक: Entropy of Random Geometric Graphs in High and Low Dimensions
  • लेखक: Oliver Baker, Carl P. Dettmann (ब्रिस्टल विश्वविद्यालय)
  • वर्गीकरण: math.PR (प्रायिकता सिद्धांत)
  • प्रकाशन समय: 26 अगस्त 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2503.11418v3

सारांश

यह पेपर घन और टोरस पर यादृच्छिक ज्यामितीय ग्राफ (RGGs) की उच्च-आयामी सीमा वितरण का अध्ययन करने के लिए बहुभिन्नरूपी केंद्रीय सीमा प्रमेय (CLT) का उपयोग करता है। अनुसंधान से पता चलता है कि जब नोड्स समान रूप से वितरित होते हैं, तो टोरस पर RGGs वितरण Erdős-Rényi (ER) समुच्चय में परिवर्तित होता है, लेकिन टोरस पर गैर-समान वितरण वाले नोड्स के RGGs के लिए, और घन पर किसी भी कर्टोसिस > 1 वाले नोड वितरण के RGGs के लिए, वितरण ER समुच्चय से भिन्न होता है। इन मामलों में, वितरण की अधिकतम एंट्रॉपी ER समुच्चय से कम है, लेकिन समरूपता बनी रहती है। सॉफ्ट RGGs दोनों ज्यामितीय संरचनाओं में ER समुच्चय में परिवर्तित होते हैं। लेख CLT के Edgeworth सुधार को विकसित करता है और दोनों ज्यामितीय संरचनाओं में RGGs की Shannon एंट्रॉपी के लिए आयाम में O(d−1/2)\mathcal{O}(d^{-1/2}) क्रम की प्रमुख अवधि प्राप्त करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

  1. नेटवर्क जटिलता को समझने की आवश्यकता: आधुनिक डेटा विज्ञान में, कंप्यूटर दृष्टि से लेकर बड़े भाषा मॉडल तक, सभी उच्च-आयामी डेटासेट से संबंधित हैं। उदाहरण के लिए, MNIST डेटासेट में 784 विशेषताएं हैं, और GPT-3 की एम्बेडिंग स्पेस 12288-आयामी है। उच्च-आयामी स्पेस में नेटवर्क निर्माण की ज्यामितीय विशेषताओं को समझना महत्वपूर्ण है।
  2. ग्राफ एंट्रॉपी सिद्धांत का विकास: 1955 में Rashevsky द्वारा ग्राफ एंट्रॉपी की अवधारणा प्रस्तुत करने के बाद से, यादृच्छिक नेटवर्क की अनिश्चितता या जटिलता को निर्धारित करना एक महत्वपूर्ण अनुसंधान क्षेत्र बन गया है, जिसमें Shannon एंट्रॉपी, Von Neumann एंट्रॉपी, Gibbs एंट्रॉपी आदि कई परिभाषाएं शामिल हैं।
  3. यादृच्छिक ज्यामितीय ग्राफ की सीमाएं: हालांकि RGG मॉडल को percolation, connectivity, centrality measures आदि के संदर्भ में अच्छी तरह से अध्ययन किया गया है, लेकिन समुच्चय-स्तरीय गुणों (जैसे Shannon एंट्रॉपी) पर अनुसंधान कम है, विशेष रूप से उच्च-आयामी मामलों में।

अनुसंधान की प्रेरणा

  1. सैद्धांतिक रिक्तता: वर्तमान में बिना बाधा के समुच्चय की एंट्रॉपी को विश्लेषणात्मक रूप से अधिकतम करने का कोई तरीका नहीं है, जब तक कि नोड स्थिति पर शर्त न लगाई जाए
  2. उच्च-आयामी व्यवहार: यह समझने की आवश्यकता है कि क्या RGGs उच्च-आयामी सीमा में ER ग्राफ में परिवर्तित होते हैं, और एंट्रॉपी का स्केलिंग व्यवहार क्या है
  3. व्यावहारिक अनुप्रयोग: उच्च-आयामी डेटा में निकटता ग्राफ एल्गोरिदम के लिए सैद्धांतिक आधार प्रदान करना

मुख्य योगदान

  1. प्रथम विश्लेषणात्मक गणना: एक-आयामी घन और टोरस पर 3-नोड हार्ड RGG समुच्चय की एंट्रॉपी की विश्लेषणात्मक गणना
  2. संख्यात्मक सिमुलेशन विधि: निम्न-आयामी सॉफ्ट RGGs की अधिकतम एंट्रॉपी के लिए संख्यात्मक सन्निकटन विधि विकसित करना
  3. अभिसरण सिद्धांत: टोरस TdT^d पर गैर-समान वितरण वाले नोड्स के हार्ड RGG के ER सीमा से विचलन को साबित करना
  4. सार्वभौमिकता परिणाम: घन [0,1]d[0,1]^d में किसी भी कर्टोसिस > 1 वाले i.i.d. नोड वितरण के हार्ड RGG कभी भी ER सीमा में परिवर्तित नहीं होते, यह साबित करना
  5. आयाम स्केलिंग: Edgeworth सुधार का उपयोग करके दोनों ज्यामितीय संरचनाओं में RGGs एंट्रॉपी के आयाम स्केलिंग नियम प्राप्त करना

विधि विवरण

कार्य परिभाषा

यादृच्छिक ज्यामितीय ग्राफ समुच्चय की Shannon एंट्रॉपी का अध्ययन, जहां:

  • इनपुट: ज्यामितीय डोमेन (घन या टोरस), नोड वितरण, कनेक्शन त्रिज्या
  • आउटपुट: ग्राफ समुच्चय की एंट्रॉपी और उच्च-आयामी सीमा में इसका व्यवहार
  • बाधा: नोड्स की संख्या n निश्चित, आयाम d→∞ जब कनेक्शन त्रिज्या r₀ d पर निर्भर करता है

मुख्य गणितीय ढांचा

1. यादृच्छिक ज्यामितीय ग्राफ परिभाषा

हार्ड RGG: किनारा (i,j) तब और केवल तब मौजूद है जब ρ(Xi,Xj)≤r0\rho(X_i, X_j) \leq r_0सॉफ्ट RGG: किनारा (i,j) संभावना p(ρ(Xi,Xj)/r0)p(\rho(X_i, X_j)/r_0) के साथ मौजूद है

2. दूरी मेट्रिक्स

  • घन: यूक्लिडियन दूरी ∥x∥\|x\|
  • टोरस: ρT(x,y)=∑i=1dmin⁡(∣xi−yi∣,1−∣xi−yi∣)2\rho_T(x,y) = \sqrt{\sum_{i=1}^d \min(|x_i - y_i|, 1-|x_i - y_i|)^2}

3. केंद्रीय सीमा प्रमेय ढांचा

मानकीकृत दूरी परिभाषित करें: qij=1d∑k=1dqijkq_{ij} = \frac{1}{\sqrt{d}}\sum_{k=1}^d q_{ij}^k जहां qijk=∣Xik−Xjk∣2−μcq_{ij}^k = |X_i^k - X_j^k|^2 - \mu_c

तकनीकी नवाचार बिंदु

1. बहुभिन्नरूपी CLT अनुप्रयोग

उच्च-आयामी दूरी समस्या को बहुभिन्नरूपी गाऊसी वितरण में परिवर्तित करना, सहप्रसरण मैट्रिक्स Σ\Sigma की संरचना अभिसरण व्यवहार को निर्धारित करती है:

  • टोरस समान वितरण: ΣT\Sigma_T विकर्ण मैट्रिक्स → ER में अभिसरण
  • घन किसी भी वितरण: Σc\Sigma_c गैर-विकर्ण → ER में अभिसरण नहीं

2. कर्टोसिस विभेदक मानदंड

साबित किया कि आसन्न दूरियां असंबंधित हैं यदि और केवल यदि निर्देशांक वितरण की कर्टोसिस 1 के बराबर है, जो केवल पैरामीटर 1/2 के साथ Bernoulli वितरण में होता है।

3. Edgeworth विस्तार

तीसरे क्रम का सुधार विकसित करना: f(q)≈N(0,Σ)(q)[1+16d∑∣α∣=3E[qα]Hα(q)]f(q) \approx N(0,\Sigma)(q)\left[1 + \frac{1}{6\sqrt{d}}\sum_{|\alpha|=3} E[q^\alpha]H_\alpha(q)\right]

प्रायोगिक सेटअप

निम्न-आयामी सटीक गणना

  • आयाम: d=1, n=3
  • ज्यामिति: एक-आयामी घन 0,1 और टोरस T¹
  • विधि: प्रत्येक ग्राफ संभावना pkp_k की विश्लेषणात्मक एकीकरण गणना

संख्यात्मक सिमुलेशन

  • पैरामीटर रेंज: d∈{1,2,3}, n=3
  • नमूना संख्या: L=10⁸ ग्राफ
  • कनेक्शन फ़ंक्शन: Rayleigh क्षय p(r/r0)=exp⁡(−(r/r0)η)p(r/r_0) = \exp(-(r/r_0)^η), η∈{1,2,3,4,5,6} और हार्ड कनेक्शन

उच्च-आयामी सैद्धांतिक विश्लेषण

  • नोड वितरण: समान वितरण, truncated Gaussian वितरण
  • अभिसरण निर्णय: सहप्रसरण मैट्रिक्स संरचना विश्लेषण के माध्यम से

प्रायोगिक परिणाम

मुख्य परिणाम

1. सटीक एंट्रॉपी गणना (d=1, n=3)

टोरस T¹:

  • इष्टतम कनेक्शन त्रिज्या: r0^=1/4\hat{r_0} = 1/4
  • अधिकतम औसत कनेक्शन संभावना: pˉmax=1/2\bar{p}_{max} = 1/2

घन 0,1:

  • इष्टतम कनेक्शन त्रिज्या: r0^=0.283\hat{r_0} = 0.283
  • अधिकतम औसत कनेक्शन संभावना: pˉmax=0.486≠1/2\bar{p}_{max} = 0.486 \neq 1/2

2. निम्न-आयामी संख्यात्मक परिणाम

तालिका 3 विभिन्न ज्यामिति और कनेक्शन फ़ंक्शन की अधिकतम एंट्रॉपी दिखाती है:

ज्यामितिη=1η=2η=3η=4η=5η=6हार्ड कनेक्शन
0,12.9942.9452.8882.8492.8262.8122.771
T¹2.9982.9822.9292.8932.8702.8542.812

अवलोकन:

  • सॉफ्ट RGGs अधिकतम एंट्रॉपी 3.0 के करीब हैं
  • एंट्रॉपी η बढ़ने के साथ घटती है
  • टोरस एंट्रॉपी आमतौर पर घन से अधिक है

3. उच्च-आयामी अभिसरण व्यवहार

प्रमेय सारांश:

ज्यामितिकनेक्शन फ़ंक्शनG(n,p) में अभिसरण?एंट्रॉपी व्यवहार
TdT^d - समान नोड्सहार्ड✓= H(G(n,p))
TdT^d - गैर-समान नोड्सहार्ड✗< H(G(n,p))
TdT^dसॉफ्ट✓= H(G(n,p))
[0,1]d[0,1]^dहार्ड✗< H(G(n,p))
[0,1]d[0,1]^dसॉफ्ट✓= H(G(n,p))

विलोपन प्रयोग

Edgeworth सुधार प्रभाव

चित्र 5 4-नोड हार्ड RGG की एंट्रॉपी अनुमान दिखाता है:

  • गाऊसी सन्निकटन: केवल CLT का उपयोग करना
  • Edgeworth सुधार: O(d−1/2)O(d^{-1/2}) पद सहित
  • संख्यात्मक सिमुलेशन: Monte Carlo विधि

परिणाम दिखाते हैं कि Edgeworth अनुमान d≥15 पर दशमलव के 2 स्थानों तक सटीक है।

संबंधित कार्य

ग्राफ एंट्रॉपी सिद्धांत

  • Rashevsky (1955): पहली बार ग्राफ एंट्रॉपी की अवधारणा प्रस्तुत की
  • सूचना सिद्धांत विधि: Shannon एंट्रॉपी, Von Neumann एंट्रॉपी आदि कई परिभाषाएं
  • स्थानिक नेटवर्क: Coon आदि द्वारा स्थानिक नेटवर्क समुच्चय एंट्रॉपी अनुसंधान

उच्च-आयामी यादृच्छिक ज्यामितीय ग्राफ

  • Devroye आदि (2011): इकाई गोले पर RGG का ER ग्राफ में अभिसरण
  • Erba आदि (2020): हाइपरक्यूब पर RGG की clique संख्या ER सीमा से विचलन
  • ज्यामितीय पहचान: हस्ताक्षरित त्रिकोण, विश्वास प्रसार आदि विधियों का उपयोग

तकनीकी विधियां

  • केंद्रीय सीमा प्रमेय: बहुभिन्नरूपी CLT का उच्च-आयामी ज्यामिति में अनुप्रयोग
  • Edgeworth विस्तार: उच्च-क्रम सुधार सिद्धांत

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. ज्यामितीय संरचना की महत्ता: टोरस की आवधिक सीमा शर्तें और घन की सीमा प्रभाव विभिन्न अभिसरण व्यवहार का कारण बनती हैं
  2. नोड वितरण का प्रभाव: केवल टोरस पर समान वितरण ER सीमा तक पहुंच सकता है
  3. कनेक्शन फ़ंक्शन की भूमिका: सॉफ्ट कनेक्शन फ़ंक्शन दूरी निर्भरता को समाप्त करते हैं, हमेशा ER समुच्चय में परिवर्तित होते हैं
  4. आयाम स्केलिंग: एंट्रॉपी विचलन की गति उच्च-आयामी सीमा से O(d−1/2)O(d^{-1/2}) है

सीमाएं

  1. नोड संख्या सीमा: सटीक गणना केवल छोटे n (n≤7) के लिए लागू होती है
  2. वितरण धारणा: निर्देशांक स्वतंत्र समान वितरण की आवश्यकता है
  3. संख्यात्मक सटीकता: उच्च-आयामी संख्यात्मक सिमुलेशन की कम्प्यूटेशनल जटिलता
  4. सैद्धांतिक अंतराल: घन में एंट्रॉपी अधिकतम मान की वैश्विकता अभी तक साबित नहीं हुई है

भविष्य की दिशाएं

  1. विस्तारित ज्यामिति: अन्य LpL^p गोले और ज्यामितीय संरचनाओं का अध्ययन करना
  2. गैर-स्वतंत्र वितरण: निर्देशांक सहसंबद्ध लेकिन समान वितरण के मामलों पर विचार करना
  3. ज्यामितीय पहचान: सूचना सिद्धांत-आधारित ज्यामितीय पहचान एल्गोरिदम विकसित करना
  4. अलेबल नेटवर्क: अलेबल ग्राफ की एंट्रॉपी विश्लेषण तक विस्तार करना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक कठोरता: RGG समुच्चय एंट्रॉपी के प्रथम सटीक विश्लेषणात्मक परिणाम, गणितीय व्युत्पत्ति पूर्ण और सटीक
  2. विधि नवाचार: बहुभिन्नरूपी CLT और Edgeworth विस्तार को चतुराई से संयोजित करना, उच्च-आयामी ज्यामितीय ग्राफ विश्लेषण के लिए नए उपकरण प्रदान करना
  3. परिणाम गहराई: ज्यामितीय संरचना, नोड वितरण और कनेक्शन फ़ंक्शन के एंट्रॉपी पर मूलभूत प्रभाव को प्रकट करना
  4. व्यावहारिक मूल्य: उच्च-आयामी डेटा विश्लेषण में निकटता ग्राफ विधियों के लिए सैद्धांतिक आधार प्रदान करना

कमियां

  1. कम्प्यूटेशनल जटिलता: सटीक विधि केवल अत्यंत छोटे पैमाने की समस्याओं (n=3) के लिए लागू होती है
  2. धारणा सीमाएं: निर्देशांक स्वतंत्रता धारणा व्यावहारिक अनुप्रयोगों में बहुत मजबूत हो सकती है
  3. संख्यात्मक चुनौतियां: उच्च-आयामी संख्यात्मक विधियों की सटीकता और दक्षता समस्याएं
  4. सैद्धांतिक पूर्णता: कुछ महत्वपूर्ण परिणाम (जैसे घन एंट्रॉपी अधिकतम मान की वैश्विकता) अभी भी अनुमान हैं

प्रभाव

  1. शैक्षणिक योगदान: यादृच्छिक ज्यामितीय ग्राफ सिद्धांत को सूचना सिद्धांत दृष्टिकोण प्रदान करना
  2. अंतर-विषय मूल्य: संभाव्यता सिद्धांत, सूचना सिद्धांत और नेटवर्क विज्ञान को जोड़ना
  3. पद्धति महत्व: Edgeworth सुधार विधि अन्य उच्च-आयामी ज्यामितीय समस्याओं तक विस्तारित की जा सकती है
  4. अनुप्रयोग संभावनाएं: मशीन लर्निंग में ज्यामितीय डेटा विश्लेषण के लिए सैद्धांतिक समर्थन प्रदान करना

लागू परिदृश्य

  1. उच्च-आयामी डेटा विश्लेषण: कंप्यूटर दृष्टि, प्राकृतिक भाषा प्रसंस्करण आदि क्षेत्रों में विशेषता स्पेस विश्लेषण
  2. नेटवर्क मॉडलिंग: सामाजिक नेटवर्क, जैविक नेटवर्क आदि जिनमें ज्यामितीय संरचना है
  3. एल्गोरिदम डिजाइन: k-निकटतम पड़ोसी, क्लस्टरिंग आदि दूरी-आधारित एल्गोरिदम अनुकूलन
  4. सैद्धांतिक अनुसंधान: यादृच्छिक ग्राफ सिद्धांत, सूचना सिद्धांत, सांख्यिकीय भौतिकी आदि मौलिक अनुसंधान

संदर्भ

पेपर 40 महत्वपूर्ण संदर्भों का हवाला देता है, जिसमें शामिल हैं:

  • ग्राफ एंट्रॉपी सिद्धांत की मूल साहित्य
  • यादृच्छिक ज्यामितीय ग्राफ की शास्त्रीय कार्य
  • उच्च-आयामी संभाव्यता सिद्धांत विधियां
  • सूचना सिद्धांत और सांख्यिकीय सिद्धांत
  • संबंधित अनुप्रयोग क्षेत्र अनुसंधान

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