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
  • العنوان: Hypothesis testing for the dimension of random geometric graph
  • المؤلفون: Mingao Yuan, Feng Yu (جامعة تكساس في إل باسو)
  • التصنيف: stat.ME (الإحصاء - المنهجية)
  • تاريخ النشر: 13 أكتوبر 2025 (نسخة 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}|}}

توجد حافة بين العُقد i و j عندما d(X_i, X_j) ≤ r_n.

بناء إحصائي الاختبار

تُعرّف إحصائية 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. شبكة الدماغ (شبكة واحدة): macaque-rhesus-brain-2، العُقد عبارة عن مناطق دماغية
  3. الشبكة الاجتماعية (شبكة واحدة): reptilia-tortoise-network-bsv، الشبكة الاجتماعية للسلاحف

مؤشرات التقييم

  1. معدل الخطأ من النوع الأول: احتمالية رفض الفرضية الصفرية عندما تكون صحيحة
  2. قوة الاختبار: احتمالية رفض الفرضية الصفرية عندما تكون الفرضية البديلة صحيحة
  3. القيمة الاحتمالية: المستخدمة للاستدلال على بُعد الشبكات الحقيقية

نتائج التجارب

نتائج المحاكاة

التحكم في الخطأ من النوع الأول:

  • معدل الخطأ التجريبي من النوع الأول في جميع الإعدادات يتراوح بين 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الكثافةالبُعد المستدلالقيمة الاحتمالية
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 مرجعاً مهماً، تغطي نظرية الرسم البياني الهندسي العشوائي وتحليل الشبكات والنظرية الإحصائية وغيرها، مما يوفر أساساً نظرياً صلباً للبحث. تشمل المراجع الرئيسية نظرية إحصائيات U لـ Fan & Li (1996)، وتطبيق شبكات البروتين لـ Higham وآخرين (2008)، والمقالات الاستقصائية الحديثة ذات الصلة.

التقييم الشامل: هذه ورقة عالية الجودة في المنهجية الإحصائية، تتميز بالابتكار النظري وتصميم الطريقة والتحقق التجريبي. على الرغم من وجود بعض القيود، فإنها تقدم مساهمة مهمة لمجال تحليل الشبكات، وتتمتع بقيمة أكاديمية وعملية عالية.