2025-11-13T21:58:11.125664

Hypothesis testing for the dimension of random geometric graph

Yuan, Yu
Random geometric graphs (RGGs) offer a powerful tool for analyzing the geometric and dependence structures in real-world networks. For example, it has been observed that RGGs are a good model for protein-protein interaction networks. In RGGs, nodes are randomly distributed over an $m$-dimensional metric space, and edges connect the nodes if and only if their distance is less than some threshold. When fitting RGGs to real-world networks, the first step is probably to input or estimate the dimension $m$. However, it is not clear whether the prespecified dimension is equal to the true dimension. In this paper, we investigate this problem using hypothesis testing. Under the null hypothesis, the dimension is equal to a specific value, while the alternative hypothesis asserts the dimension is not equal to that value. We propose the first statistical test. Under the null hypothesis, the proposed test statistic converges in law to the standard normal distribution, and under the alternative hypothesis, the test statistic is unbounded in probability. We derive the asymptotic distribution by leveraging the asymptotic theory of degenerate U-statistics with kernel function dependent on the number of nodes. This approach differs significantly from prevailing methods used in network hypothesis testing problems. Moreover, we also propose an efficient approach to compute the test statistic based on the adjacency matrix. Simulation studies show that the proposed test performs well. We also apply the proposed test to multiple real-world networks to test their dimensions.
academic

র‍্যান্ডম জ্যামিতিক গ্রাফের মাত্রার জন্য অনুমান পরীক্ষা

মৌলিক তথ্য

  • পেপার আইডি: 2510.11844
  • শিরোনাম: র‍্যান্ডম জ্যামিতিক গ্রাফের মাত্রার জন্য অনুমান পরীক্ষা
  • লেখক: মিংগাও ইউয়ান, ফেং ইউ (দ্য ইউনিভার্সিটি অফ টেক্সাস অ্যাট এল পাসো)
  • শ্রেণীবিভাগ: stat.ME (পরিসংখ্যান - পদ্ধতিবিদ্যা)
  • প্রকাশনার সময়: ২০২৫ সালের ১৩ অক্টোবর (arXiv প্রাক-প্রকাশনা)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.11844

সারসংক্ষেপ

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

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

সমস্যা সংজ্ঞা

  1. মূল সমস্যা: বাস্তব নেটওয়ার্কে র‍্যান্ডম জ্যামিতিক গ্রাফ ফিট করার সময়, প্রাক-নির্ধারিত বা অনুমানকৃত মাত্রা m প্রকৃত মাত্রার সমান কিনা তা কীভাবে যাচাই করতে হয়
  2. ব্যবহারিক চাহিদা: বিদ্যমান গবেষণায়, গবেষকরা সাধারণত সরাসরি মাত্রা মান অনুমান করেন (যেমন প্রোটিন ইন্টারঅ্যাকশন নেটওয়ার্কে m=2,3,4 অনুমান করেন), কিন্তু পরিসংখ্যানগত যাচাইকরণ পদ্ধতির অভাব রয়েছে
  3. প্রয়োগের গুরুত্ব: RGGs প্রোটিন ইন্টারঅ্যাকশন নেটওয়ার্ক, সামাজিক নেটওয়ার্ক, মস্তিষ্ক নেটওয়ার্ক এবং অন্যান্য অনেক ক্ষেত্রে ব্যাপকভাবে প্রয়োগ করা হয়

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

  1. পদ্ধতিগত শূন্যতা: এটি RGG মাত্রার জন্য প্রথম অনুমান পরীক্ষা পদ্ধতি
  2. তাত্ত্বিক চ্যালেঞ্জ: অবক্ষয়িত U-পরিসংখ্যানের অসিম্পটোটিক তত্ত্ব পরিচালনা করতে হবে, যার কার্নেল ফাংশন নেটওয়ার্ক আকারের উপর নির্ভর করে
  3. ব্যবহারিক মূল্য: নেটওয়ার্ক বিশ্লেষণের জন্য কঠোর মাত্রা যাচাইকরণ সরঞ্জাম প্রদান করা

মূল অবদান

  1. অগ্রগামী পদ্ধতি: র‍্যান্ডম জ্যামিতিক গ্রাফ মাত্রা অনুমান পরীক্ষার জন্য প্রথম পরিসংখ্যানগত পদ্ধতি প্রস্তাব করা
  2. তাত্ত্বিক উদ্ভাবন:
    • অবক্ষয়িত U-পরিসংখ্যান তত্ত্বের উপর ভিত্তি করে পরীক্ষা পরিসংখ্যানের অসিম্পটোটিক বিতরণ প্রতিষ্ঠা করা
    • কার্নেল ফাংশন নমুনা আকার n-এর উপর নির্ভর করে, যা মান U-পরিসংখ্যান তত্ত্ব থেকে আলাদা
  3. গণনাগত দক্ষতা: সংলগ্নতা ম্যাট্রিক্সের উপর ভিত্তি করে দক্ষ গণনা পদ্ধতি প্রদান করা, যা বহুবার নেস্টেড লুপ এড়ায়
  4. তাত্ত্বিক গ্যারান্টি:
    • শূন্য অনুমানের অধীনে পরিসংখ্যান মান স্বাভাবিক বিতরণে সংবেদনশীল হয়
    • বিকল্প অনুমানের অধীনে পরীক্ষার শক্তি 1-এ প্রবণ হয়
  5. অভিজ্ঞতামূলক যাচাইকরণ: অনুকরণ ডেটা এবং 6টি বাস্তব নেটওয়ার্কে পদ্ধতির কার্যকারিতা যাচাই করা

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

কাজের সংজ্ঞা

প্রদত্ত নেটওয়ার্ক সংলগ্নতা ম্যাট্রিক্স A ~ G_n(m, r_n), অনুমান পরীক্ষা করুন:

  • H_0: m = m_0 (শূন্য অনুমান: মাত্রা প্রাক-নির্ধারিত মান m_0 এর সমান)
  • H_1: m ≠ m_0 (বিকল্প অনুমান: মাত্রা m_0 এর সমান নয়)

র‍্যান্ডম জ্যামিতিক গ্রাফ মডেল

সংজ্ঞা: ইউনিট হাইপারকিউব 0,1^m-এ, নোড X_i স্বাধীনভাবে সমানভাবে বিতরণ করা হয়, দূরত্ব সংজ্ঞায়িত হয়:

d(X_i, X_j) = max_{1≤k≤m} {min{|X_{ik} - X_{jk}|, 1 - |X_{ik} - X_{jk}|}}

যখন d(X_i, X_j) ≤ r_n, নোড i এবং j এর মধ্যে একটি প্রান্ত বিদ্যমান।

পরীক্ষা পরিসংখ্যান নির্মাণ

মূল পরিসংখ্যান D_n সংজ্ঞায়িত হয়:

D_n = Σ_{i≠j≠k} A_{ij}A_{jk}A_{ki} - (3/4)^{m_0} Σ_{i≠j≠k} A_{ij}A_{ik}

ডিজাইন চিন্তাভাবনা:

  • প্রথম পদ নেটওয়ার্কে ত্রিভুজ সংখ্যা গণনা করে
  • দ্বিতীয় পদ শূন্য অনুমানের অধীনে প্রত্যাশিত সংশোধন
  • শূন্য অনুমানের অধীনে D_n ≈ 0, বিকল্প অনুমানের অধীনে D_n উল্লেখযোগ্যভাবে 0 থেকে বিচলিত হয়

অসিম্পটোটিক বিতরণ তত্ত্ব

প্রধান উপপাদ্য: শর্ত r_n = o(1) এবং nr_n^m = ω(1) এর অধীনে, শূন্য অনুমান H_0 এর অধীনে:

√(2D_n)/(n²σ̂_{n2}) ⇒ N(0,1)

যেখানে ভেরিয়েন্স অনুমান σ̂²_ পাঁচটি পরিসংখ্যান S_1 থেকে S_5 এর রৈখিক সমন্বয় দ্বারা দেওয়া হয়।

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

  1. অবক্ষয়িত U-পরিসংখ্যান পরিচালনা:
    • D_n কে অবক্ষয়িত U-পরিসংখ্যান ফর্মে প্রকাশ করা
    • কার্নেল ফাংশন n-এর উপর নির্ভর করে এমন অ-মান কেস পরিচালনা করা
    • Fan-Li (1996) এর অসিম্পটোটিক তত্ত্ব প্রয়োগ করা
  2. ম্যাট্রিক্স গণনা অপ্টিমাইজেশন:
    D_n = tr(A³) + 2tr(A) - (3/4)^{m_0}(1^T(A² - A)1 + 2tr(A))
S_1 = 1^T[A² ⊙ A² ⊙ A - A² ⊙ A]1

    O(n⁴) নেস্টেড লুপ গণনা এড়ানো
  3. শক্তি বিশ্লেষণ: বিকল্প অনুমানের অধীনে পরিসংখ্যানের ক্রম Θ(n√(r_n^m)), পরীক্ষার শক্তি 1-এ প্রবণ নিশ্চিত করে

পরীক্ষা সেটআপ

অনুকরণ পরীক্ষা

  1. পরামিতি সেটিং:
    • নেটওয়ার্ক আকার: n ∈ {40, 50, 60, 70, 100, 130}
    • সংযোগ ব্যাসার্ধ: r_n ∈ {0.09, 0.10, 0.11, 0.27, 0.29, 0.31}
    • মাত্রা: m ∈ {1, 2, 3}
    • তাৎপর্য স্তর: α = 0.05
  2. পরীক্ষা ডিজাইন:
    • প্রথম ধরনের ত্রুটি: শূন্য অনুমানের অধীনে 1000টি নেটওয়ার্ক তৈরি করা
    • পরীক্ষার শক্তি: বিকল্প অনুমানের অধীনে 1000টি নেটওয়ার্ক তৈরি করা

বাস্তব ডেটা

6টি বাস্তব নেটওয়ার্ক পরীক্ষা করা হয়েছে:

  1. রাসায়নিক তথ্যবিজ্ঞান নেটওয়ার্ক (4টি): ENZYMES সিরিজ, নোড হল যৌগ
  2. মস্তিষ্ক নেটওয়ার্ক (1টি): macaque-rhesus-brain-2, নোড হল মস্তিষ্কের অঞ্চল
  3. সামাজিক নেটওয়ার্ক (1টি): reptilia-tortoise-network-bsv, কচ্ছপ সামাজিক নেটওয়ার্ক

মূল্যায়ন মেট্রিক্স

  1. প্রথম ধরনের ত্রুটির হার: শূন্য অনুমান সত্য হলে প্রত্যাখ্যান করার সম্ভাবনা
  2. পরীক্ষার শক্তি: বিকল্প অনুমান সত্য হলে শূন্য অনুমান প্রত্যাখ্যান করার সম্ভাবনা
  3. p-মান: বাস্তব নেটওয়ার্কের মাত্রা অনুমানের জন্য ব্যবহৃত

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

অনুকরণ ফলাফল

প্রথম ধরনের ত্রুটি নিয়ন্ত্রণ:

  • সমস্ত সেটিংয়ে অভিজ্ঞতামূলক প্রথম ধরনের ত্রুটির হার 0.040-0.064 এর মধ্যে, নামমাত্র স্তর 0.05 এর কাছাকাছি
  • অসিম্পটোটিক স্বাভাবিক বিতরণ অনুমান সীমিত নমুনায় ভাল কর্মক্ষমতা প্রদর্শন করে

পরীক্ষার শক্তি:

  • H_0: m=1 হলে, m=2 এর শক্তি 0.920-1.000 এর মধ্যে, m=3 এর শক্তি 0.645-0.997 এর মধ্যে
  • H_0: m=2 হলে, m=1 এর শক্তি সর্বদা 1.000, m=3 এর শক্তি 0.927-1.000 এর মধ্যে
  • শক্তি n এবং r_n বৃদ্ধির সাথে বৃদ্ধি পায়, তাত্ত্বিক প্রত্যাশার সাথে সামঞ্জস্যপূর্ণ

বাস্তব নেটওয়ার্ক ফলাফল

নেটওয়ার্কnঘনত্বঅনুমানকৃত মাত্রাp-মান
ENZYMES-g147400.210m=20.696
ENZYMES-g196500.138m=30.653
ENZYMES-g532740.085m=50.140
macaque-rhesus-brain-2910.152m=30.161
reptilia-tortoise-network-bsv1360.040m=40.162

গুরুত্বপূর্ণ আবিষ্কার: বিভিন্ন নেটওয়ার্কের বিভিন্ন মাত্রা রয়েছে, যা মাত্রা পরীক্ষার গুরুত্ব তুলে ধরে।

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

র‍্যান্ডম জ্যামিতিক গ্রাফ তত্ত্ব

  1. ক্লাসিক সাহিত্য: Penrose এবং অন্যদের মৌলিক তাত্ত্বিক কাজ
  2. সর্বশেষ উন্নয়ন: Duchemin & De Castro (2023) এর সমীক্ষা
  3. মাত্রা অনুমান: Atamanchuk এবং অন্যদের (2024) সামঞ্জস্যপূর্ণ অনুমান পদ্ধতি

নেটওয়ার্ক অনুমান পরীক্ষা

  1. গ্রাফ কাঠামো পরীক্ষা: Gao & Lafferty (2017), Jin এবং অন্যদের (2018)
  2. সম্প্রদায় কাঠামো পরীক্ষা: Lei (2016), Yuan এবং অন্যদের (2022)
  3. এই পেপারের উদ্ভাবন: জ্যামিতিক গ্রাফ মাত্রার জন্য প্রথম অনুমান পরীক্ষা

প্রয়োগ ক্ষেত্র

  1. জৈব নেটওয়ার্ক: Higham এবং অন্যদের (2008) প্রোটিন নেটওয়ার্কে প্রয়োগ
  2. মস্তিষ্ক নেটওয়ার্ক: কার্যকরী সংযোগ নেটওয়ার্ক বিশ্লেষণ
  3. সামাজিক নেটওয়ার্ক: মতামত প্রচার এবং স্থানিক বিতরণ মডেলিং

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. তাত্ত্বিক অবদান: RGG মাত্রা অনুমান পরীক্ষার সম্পূর্ণ তাত্ত্বিক কাঠামো প্রতিষ্ঠা করা
  2. পদ্ধতির কার্যকারিতা: অনুকরণ এবং অভিজ্ঞতামূলক ফলাফল পদ্ধতির নির্ভরযোগ্যতা যাচাই করে
  3. ব্যবহারিক মূল্য: নেটওয়ার্ক বিশ্লেষণের জন্য গুরুত্বপূর্ণ পরিসংখ্যানগত সরঞ্জাম প্রদান করা

সীমাবদ্ধতা

  1. মডেল অনুমান:
    • নোডগুলি ইউনিট হাইপারকিউবে সমানভাবে বিতরণ করা হয় বলে অনুমান করা
    • নির্দিষ্ট দূরত্ব পরিমাপ ফাংশন ব্যবহার করা
    • নেটওয়ার্ক বিরল হওয়ার প্রয়োজন (r_n = o(1))
  2. গণনাগত জটিলতা: যদিও গণনা অপ্টিমাইজ করা হয়েছে, অতি বৃহৎ আকারের নেটওয়ার্কের জন্য এখনও চ্যালেঞ্জ হতে পারে
  3. মাত্রা পরিসীমা: প্রধানত নিম্ন মাত্রার ক্ষেত্রে যাচাই করা হয়েছে, উচ্চ মাত্রার কর্মক্ষমতা আরও গবেষণার অপেক্ষায় রয়েছে

ভবিষ্যত দিকনির্দেশনা

  1. মডেল সম্প্রসারণ: অ-সমান বিতরণ, অন্যান্য দূরত্ব পরিমাপ বিবেচনা করা
  2. উচ্চ মাত্রার ক্ষেত্র: উচ্চ মাত্রার RGG এর জন্য পরীক্ষা পদ্ধতি গবেষণা করা
  3. একাধিক পরীক্ষা: একযোগে একাধিক মাত্রা মান পরীক্ষা করার পদ্ধতি
  4. বেয়েসীয় পদ্ধতি: মাত্রার জন্য বেয়েসীয় অনুমান পদ্ধতি বিকাশ করা

গভীর মূল্যায়ন

শক্তি

  1. তাত্ত্বিক কঠোরতা:
    • দৃঢ় U-পরিসংখ্যান তত্ত্বের উপর ভিত্তি করে
    • সম্পূর্ণ অসিম্পটোটিক বিশ্লেষণ এবং শক্তি অধ্যয়ন
    • কঠোর গাণিতিক প্রমাণ
  2. পদ্ধতি উদ্ভাবন:
    • RGG মাত্রা পরীক্ষার প্রথম পদ্ধতি
    • চতুর পরিসংখ্যান ডিজাইন
    • দক্ষ গণনা বাস্তবায়ন
  3. ব্যাপক পরীক্ষা:
    • পর্যাপ্ত অনুকরণ যাচাইকরণ
    • বৈচিত্র্যময় বাস্তব নেটওয়ার্ক পরীক্ষা
    • বিস্তারিত কর্মক্ষমতা বিশ্লেষণ
  4. ব্যবহারিক মূল্য:
    • ব্যবহারিক চাহিদা সমাধান করা
    • বাস্তবায়ন এবং প্রয়োগ সহজ
    • পরবর্তী গবেষণার ভিত্তি স্থাপন করা

অপূর্ণতা

  1. প্রয়োগের পরিসীমা:
    • শুধুমাত্র বিরল নেটওয়ার্কের জন্য প্রযোজ্য
    • মডেল অনুমানের প্রতি সংবেদনশীল
    • বাস্তব নেটওয়ার্ক সম্পূর্ণভাবে RGG মডেল মেনে নাও চলতে পারে
  2. পদ্ধতি সীমাবদ্ধতা:
    • শুধুমাত্র দ্বিমুখী পরীক্ষা সম্পাদন করতে পারে
    • অনুমান ত্রুটির প্রভাব বিবেচনা করা হয়নি
    • অসাধারণ মানের প্রতি দৃঢ়তা সম্পূর্ণভাবে গবেষণা করা হয়নি
  3. পরীক্ষা গভীরতা:
    • বাস্তব নেটওয়ার্ক সংখ্যা তুলনামূলকভাবে সীমিত
    • অন্যান্য মাত্রা অনুমান পদ্ধতির সাথে তুলনার অভাব
    • পদ্ধতি ব্যর্থতার ক্ষেত্রে গভীর বিশ্লেষণ অনুপস্থিত

প্রভাব

  1. একাডেমিক মূল্য:
    • গুরুত্বপূর্ণ পদ্ধতিগত শূন্যতা পূরণ করা
    • নেটওয়ার্ক বিশ্লেষণের জন্য নতুন সরঞ্জাম প্রদান করা
    • সম্পর্কিত গবেষণা দিক উদ্দীপিত করতে পারে
  2. ব্যবহারিক তাৎপর্য:
    • জৈব তথ্যবিজ্ঞান, সামাজিক নেটওয়ার্ক বিশ্লেষণ ইত্যাদি ক্ষেত্রে সরাসরি প্রয়োগ
    • নেটওয়ার্ক মডেলিংয়ের বৈজ্ঞানিকতা উন্নত করা
    • মডেল নির্বাচনের জন্য পরিসংখ্যানগত ভিত্তি প্রদান করা
  3. পুনরুৎপাদনযোগ্যতা:
    • বিস্তারিত গণনা সূত্র প্রদান করা
    • স্পষ্ট অ্যালগরিদম বর্ণনা
    • সফটওয়্যার বাস্তবায়ন সুবিধাজনক

প্রযোজ্য পরিস্থিতি

  1. জৈব নেটওয়ার্ক: প্রোটিন ইন্টারঅ্যাকশন নেটওয়ার্কের মাত্রা যাচাইকরণ
  2. সামাজিক নেটওয়ার্ক: স্থানিক এমবেডিং মডেলের মাত্রা নির্বাচন
  3. মস্তিষ্ক নেটওয়ার্ক: কার্যকরী সংযোগ নেটওয়ার্কের জ্যামিতিক কাঠামো বিশ্লেষণ
  4. যোগাযোগ নেটওয়ার্ক: ওয়্যারলেস সেন্সর নেটওয়ার্কের টপোলজি বিশ্লেষণ

তথ্যসূত্র

এই পেপারটি 40টি গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যা র‍্যান্ডম জ্যামিতিক গ্রাফ তত্ত্ব, নেটওয়ার্ক বিশ্লেষণ, পরিসংখ্যান তত্ত্ব এবং অন্যান্য অনেক দিক কভার করে, গবেষণার জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে। মূল তথ্যসূত্রগুলির মধ্যে রয়েছে Fan & Li (1996) এর U-পরিসংখ্যান তত্ত্ব, Higham এবং অন্যদের (2008) প্রোটিন নেটওয়ার্ক প্রয়োগ, এবং সাম্প্রতিক সম্পর্কিত সমীক্ষা নিবন্ধ।

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