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

উচ্চ এবং নিম্ন মাত্রায় র্যান্ডম জ্যামিতিক গ্রাফের এন্ট্রপি

মৌলিক তথ্য

  • পেপার আইডি: 2503.11418
  • শিরোনাম: Entropy of Random Geometric Graphs in High and Low Dimensions
  • লেখক: Oliver Baker, Carl P. Dettmann (ব্রিস্টল বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: math.PR (সম্ভাবনা তত্ত্ব)
  • প্রকাশনার সময়: ২০২৫ সালের ২৬ আগস্ট (arXiv প্রি-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2503.11418v3

সারসংক্ষেপ

এই পেপারটি বহুমাত্রিক কেন্দ্রীয় সীমা উপপাদ্য (CLT) ব্যবহার করে ঘনক এবং টোরাসের উপর র্যান্ডম জ্যামিতিক গ্রাফ (RGGs) এর উচ্চ-মাত্রিক সীমা বিতরণ অধ্যয়ন করে। গবেষণায় দেখা যায় যে যখন নোডগুলি সমানভাবে বিতরণ করা হয়, তখন টোরাসের উপর RGGs বিতরণ Erdős-Rényi (ER) সেটে সংগ্রহ করে, কিন্তু টোরাসের উপর অসমান বিতরণ নোডের RGGs এবং ঘনকের উপর ১ এর চেয়ে বেশি কার্টোসিস সহ যেকোনো নোড বিতরণের RGGs ER সেট থেকে আলাদা। এই ক্ষেত্রগুলিতে, বিতরণের সর্বোচ্চ এন্ট্রপি ER সেটের চেয়ে কম কিন্তু সমরূপতা বজায় রাখে। নরম RGGs উভয় জ্যামিতিক কাঠামোতে ER সেটে সংগ্রহ করে। নিবন্ধটি CLT এর Edgeworth সংশোধন বিকশিত করে এবং উভয় জ্যামিতিক কাঠামোতে RGGs এর Shannon এন্ট্রপির জন্য মাত্রায় O(d−1/2)\mathcal{O}(d^{-1/2}) অগ্রণী পদ প্রাপ্ত করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

  1. নেটওয়ার্ক জটিলতা বোঝার প্রয়োজন: আধুনিক ডেটা বিজ্ঞানে, কম্পিউটার দৃষ্টিভঙ্গি থেকে বড় ভাষা মডেল পর্যন্ত, সবকিছুতে উচ্চ-মাত্রিক ডেটাসেট জড়িত। উদাহরণস্বরূপ, MNIST ডেটাসেটে ৭৮৪টি বৈশিষ্ট্য রয়েছে এবং GPT-3 এর এম্বেডিং স্থান ১২২৮৮ মাত্রার। উচ্চ-মাত্রিক স্থানে নেটওয়ার্ক নির্মাণের জ্যামিতিক বৈশিষ্ট্য বোঝা অত্যন্ত গুরুত্বপূর্ণ।
  2. গ্রাফ এন্ট্রপি তত্ত্বের বিকাশ: ১৯৫৫ সালে Rashevsky গ্রাফ এন্ট্রপি ধারণা প্রবর্তনের পর থেকে, র্যান্ডম নেটওয়ার্কের অনিশ্চয়তা বা জটিলতা নির্ধারণ একটি গুরুত্বপূর্ণ গবেষণা ক্ষেত্র হয়ে উঠেছে, যার মধ্যে Shannon এন্ট্রপি, Von Neumann এন্ট্রপি, Gibbs এন্ট্রপি এবং অন্যান্য সংজ্ঞা রয়েছে।
  3. র্যান্ডম জ্যামিতিক গ্রাফের সীমাবদ্ধতা: যদিও RGG মডেল পারকোলেশন, সংযোগযোগ্যতা, কেন্দ্রীয়তা পরিমাপ ইত্যাদি দিক থেকে যথেষ্ট অধ্যয়ন করা হয়েছে, তবে সেট-স্তরের বৈশিষ্ট্য (যেমন Shannon এন্ট্রপি) সম্পর্কে গবেষণা কম, বিশেষ করে উচ্চ-মাত্রিক ক্ষেত্রে।

গবেষণার প্রেরণা

  1. তাত্ত্বিক শূন্যতা: বর্তমানে নোড অবস্থানে শর্তাধীন ছাড়া অসীমিত সেটের এন্ট্রপি বিশ্লেষণাত্মকভাবে সর্বাধিক করা যায় না
  2. উচ্চ-মাত্রিক আচরণ: উচ্চ-মাত্রিক সীমায় RGGs ER গ্রাফে সংগ্রহ করে কিনা এবং এন্ট্রপির স্কেলিং আচরণ বোঝার প্রয়োজন
  3. ব্যবহারিক প্রয়োগ: উচ্চ-মাত্রিক ডেটায় নিকটতম গ্রাফ অ্যালগরিদমের জন্য তাত্ত্বিক ভিত্তি প্রদান করা

মূল অবদান

  1. প্রথম বিশ্লেষণাত্মক গণনা: এক-মাত্রিক ঘনক এবং টোরাসের উপর ৩-নোড কঠিন RGG সেটের এন্ট্রপি বিশ্লেষণাত্মকভাবে গণনা করা
  2. সংখ্যাসূচক সিমুলেশন পদ্ধতি: নিম্ন-মাত্রিক নরম RGGs সর্বোচ্চ এন্ট্রপির সংখ্যাসূচক অনুমানের পদ্ধতি বিকশিত করা
  3. সংগ্রহ তত্ত্ব: টোরাস TdT^d এ অসমান বিতরণ নোডের কঠিন RGG ER সীমা থেকে বিচ্যুত হওয়া প্রমাণ করা
  4. সর্বজনীনতা ফলাফল: ঘনক [0,1]d[0,1]^d এ ১ এর চেয়ে বেশি কার্টোসিস সহ যেকোনো i.i.d. নোড বিতরণের কঠিন RGG কখনও ER সীমায় সংগ্রহ করে না তা প্রমাণ করা
  5. মাত্রা স্কেলিং: Edgeworth সংশোধন ব্যবহার করে উভয় জ্যামিতিক কাঠামোতে RGGs এন্ট্রপির মাত্রা স্কেলিং নিয়ম প্রাপ্ত করা

পদ্ধতির বিস্তারিত বিবরণ

কাজের সংজ্ঞা

র্যান্ডম জ্যামিতিক গ্রাফ সেটের Shannon এন্ট্রপি অধ্যয়ন করা, যেখানে:

  • ইনপুট: জ্যামিতিক ডোমেইন (ঘনক বা টোরাস), নোড বিতরণ, সংযোগ ব্যাসার্ধ
  • আউটপুট: গ্রাফ সেটের এন্ট্রপি এবং উচ্চ-মাত্রিক সীমায় এর আচরণ
  • সীমাবদ্ধতা: নোড সংখ্যা n নির্দিষ্ট, মাত্রা d→∞ এর সময় সংযোগ ব্যাসার্ধ r₀ d এর উপর নির্ভর করে

মূল গাণিতিক কাঠামো

১. র্যান্ডম জ্যামিতিক গ্রাফ সংজ্ঞা

কঠিন RGG: যখন এবং শুধুমাত্র যখন ρ(Xi,Xj)≤r0\rho(X_i, X_j) \leq r_0 হয় তখন প্রান্ত (i,j)(i,j) বিদ্যমান নরম RGG: প্রান্ত (i,j)(i,j) সম্ভাবনা p(ρ(Xi,Xj)/r0)p(\rho(X_i, X_j)/r_0) সহ বিদ্যমান

২. দূরত্ব মেট্রিক

  • ঘনক: ইউক্লিডীয় দূরত্ব ∥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}

३. কেন্দ্রীয় সীমা উপপাদ্য কাঠামো

স্ট্যান্ডার্ডাইজড দূরত্ব সংজ্ঞায়িত করা: 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

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

১. বহুমাত্রিক CLT প্রয়োগ

উচ্চ-মাত্রিক দূরত্ব সমস্যাকে বহুমাত্রিক গাউসীয় বিতরণে রূপান্তরিত করা, সহভেরিয়েন্স ম্যাট্রিক্স Σ\Sigma এর কাঠামো সংগ্রহ আচরণ নির্ধারণ করে:

  • টোরাস সমান বিতরণ: ΣT\Sigma_T কর্ণ ম্যাট্রিক্স → ER তে সংগ্রহ করে
  • ঘনক যেকোনো বিতরণ: Σc\Sigma_c অ-কর্ণ → ER তে সংগ্রহ করে না

२. কার্টোসিস বিচার মানদণ্ড

প্রমাণ করা যে সন্নিহিত দূরত্ব অসম্পর্কিত হওয়ার প্রয়োজনীয় এবং পর্যাপ্ত শর্ত হল স্থানাঙ্ক বিতরণের কার্টোসিস ১ এর সমান, যা শুধুমাত্র প্যারামিটার ১/२ এর বার্নুলি বিতরণে ঘটে।

३. 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} এবং কঠিন সংযোগ

উচ্চ-মাত্রিক তাত্ত্বিক বিশ্লেষণ

  • নোড বিতরণ: সমান বিতরণ, ছাঁটা গাউসীয় বিতরণ
  • সংগ্রহ বিচার: সহভেরিয়েন্স ম্যাট্রিক্স কাঠামো বিশ্লেষণের মাধ্যমে

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

১. নির্ভুল এন্ট্রপি গণনা (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

२. নিম্ন-মাত্রিক সংখ্যাসূচক ফলাফল

সারণী ३ বিভিন্ন জ্যামিতি এবং সংযোগ ফাংশনের সর্বোচ্চ এন্ট্রপি দেখায়:

জ্যামিতিη=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 সর্বোচ্চ এন্ট্রপি ३.০ এর কাছাকাছি
  • এন্ট্রপি η বৃদ্ধির সাথে হ্রাস পায়
  • টোরাস এন্ট্রপি সাধারণত ঘনকের চেয়ে বেশি

३. উচ্চ-মাত্রিক সংগ্রহ আচরণ

উপপাদ্য সারসংক্ষেপ:

জ্যামিতিসংযোগ ফাংশন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 সংশোধন প্রভাব

চিত্র ५ ४-নোড কঠিন RGG এর এন্ট্রপি অনুমান দেখায়:

  • গাউসীয় অনুমান: শুধুমাত্র CLT ব্যবহার করা
  • Edgeworth সংশোধন: O(d−1/2)O(d^{-1/2}) পদ অন্তর্ভুক্ত করা
  • সংখ্যাসূচক সিমুলেশন: মন্টে কার্লো পদ্ধতি

ফলাফল দেখায় যে Edgeworth অনুমান d≥15 এ দশমিক পয়েন্টের ২ স্থান পর্যন্ত নির্ভুল।

সম্পর্কিত কাজ

গ্রাফ এন্ট্রপি তত্ত্ব

  • Rashevsky (1955): প্রথম গ্রাফ এন্ট্রপি ধারণা প্রবর্তন করেন
  • তথ্য তত্ত্ব পদ্ধতি: Shannon এন্ট্রপি, Von Neumann এন্ট্রপি এবং অন্যান্য একাধিক সংজ্ঞা
  • স্থানিক নেটওয়ার্ক: Coon এবং অন্যদের স্থানিক নেটওয়ার্ক সেট এন্ট্রপি গবেষণা

উচ্চ-মাত্রিক র্যান্ডম জ্যামিতিক গ্রাফ

  • Devroye এবং অন্যরা (2011): ইউনিট গোলক উপর RGG ER গ্রাফে সংগ্রহ করে
  • Erba এবং অন্যরা (2020): হাইপারকিউব উপর RGG এর ক্লিক সংখ্যা 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. তাত্ত্বিক গবেষণা: র্যান্ডম গ্রাফ তত্ত্ব, তথ্য তত্ত্ব, পরিসংখ্যান পদার্থবিজ্ঞান ইত্যাদি মৌলিক গবেষণা

সংদর্ভ

পেপারটি ৪০টি গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:

  • গ্রাফ এন্ট্রপি তত্ত্বের ভিত্তি সাহিত্য
  • র্যান্ডম জ্যামিতিক গ্রাফের ক্লাসিক কাজ
  • উচ্চ-মাত্রিক সম্ভাবনা তত্ত্ব পদ্ধতি
  • তথ্য তত্ত্ব এবং পরিসংখ্যান তত্ত্ব
  • সম্পর্কিত প্রয়োগ ক্ষেত্র গবেষণা

সামগ্রিক মূল্যায়ন: এটি র্যান্ডম জ্যামিতিক গ্রাফ এন্ট্রপি তত্ত্বে একটি উচ্চ-মানের তাত্ত্বিক গবেষণা পেপার যা গুরুত্বপূর্ণ অগ্রগতি অর্জন করেছে। যদিও গণনা জটিলতা এবং ব্যবহারিক প্রয়োগ দিক থেকে সীমাবদ্ধতা রয়েছে, তবে এর তাত্ত্বিক অবদান এবং পদ্ধতি উদ্ভাবন এই ক্ষেত্রের আরও বিকাশের জন্য একটি দৃঢ় ভিত্তি স্থাপন করে।