رسم بياني هندسي عشوائي

الموسوعة الحرة

في نظرية الرسم البياني ، يعتبر الرسم البياني الهندسي العشوائي ( RGG ) أبسط شبكة مكانية من الناحية الرياضية ، وهو عبارة عن رسم بياني غير موجه يتم إنشاؤه عن طريق وضع N عقدة بشكل عشوائي في مساحة مترية معينة (وفقًا لتوزيع احتمالي محدد) وربط عقدتين برابط إذا وفقط إذا كانت المسافة بينهما في نطاق معين، على سبيل المثال أصغر من نصف قطر جوار معين، r .

تُشابه الرسوم البيانية الهندسية العشوائية الشبكات الاجتماعية البشرية الحقيقية في عدة جوانب. فعلى سبيل المثال، تُظهر هذه الرسوم تلقائيًا بنية مجتمعية - أي تجمعات من العقد ذات نمطية عالية. ولا تُنشئ خوارزميات توليد الرسوم البيانية العشوائية الأخرى، مثل تلك المُولّدة باستخدام نموذج إردوش-ريني أو نموذج باراباسي-ألبرت (BA)، هذا النوع من البنية. إضافةً إلى ذلك، تُظهر الرسوم البيانية الهندسية العشوائية ترابطًا في درجة العقد وفقًا لبُعدها المكاني: [ 1 ] فالعقد "الشائعة" (ذات الروابط الكثيرة) من المرجح أن تكون مرتبطة بعقد شائعة أخرى.

تُعرف نظرية الترشيح في الرسم البياني الهندسي العشوائي (دراسة اتصاله الشامل) أحيانًا بنموذج قرص جيلبرت [ 2 ] نسبةً إلى عمل إدغار جيلبرت ، الذي قدّم هذه الرسوم البيانية ونظرية الترشيح فيها في ورقة بحثية عام 1961. [ 3 ] ومن التطبيقات العملية للرسوم البيانية الهندسية العشوائية نمذجة الشبكات المخصصة . [ 4 ] كما تُستخدم هذه الرسوم البيانية لتقييم خوارزميات الرسوم البيانية.

تعريف

توليد رسم بياني هندسي عشوائي لمعاملات اتصال مختلفة r.

فيما يلي، لنفترض أن  G = ( V , E ) يمثل رسمًا بيانيًا غير موجه بمجموعة رؤوس V ومجموعة حواف E ⊆ V × V. يُرمز إلى حجمي المجموعتين بـ | V | = n و | E | = m . بالإضافة إلى ذلك، ما لم يُذكر خلاف ذلك، يُؤخذ في الاعتبار الفضاء المتري [ 0,1) d مع المسافة الإقليدية ، أي لأي نقاطx،y∈[0،1)د{\displaystyle x,y\in [0,1)^{d}}تُعرَّف المسافة الإقليدية بين x و y على النحو التالي:

د(x،y)=||x-y||2=∑أنا=1د(xأنا-yأنا)2{\displaystyle d(x,y)=||xy||_{2}={\sqrt {\sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}}.

الرسم البياني الهندسي العشوائي (RGG) هو رسم بياني هندسي غير موجه ، حيث تُختار العقد عشوائيًا من التوزيع المنتظم للفضاء الأساسي [ 0,1) d . [ 5 ] يكون رأسان p و q ∈ V متصلين إذا، وفقط إذا، كانت المسافة بينهما أقل من قيمة محددة مسبقًا r ∈ (0,1) ، باستثناء أي حلقات . وبالتالي، فإن المعاملين r و n يصفان الرسم البياني الهندسي العشوائي وصفًا كاملًا.

الخوارزميات

خوارزمية ساذجة

يتمثل النهج البسيط في حساب المسافة بين كل رأس وكل رأس آخر.ن(ن-1)2{\textstyle {\frac {n(n-1)}{2}}}الاتصالات الممكنة التي يتم فحصها، والتعقيد الزمني للخوارزمية البسيطة هوΘ(ن2){\textstyle \Theta (n^{2})}يتم توليد العينات باستخدام مولد أرقام عشوائية (RNG) على[0،1)د{\displaystyle [0,1)^{d}}عمليًا، يمكن تنفيذ ذلك باستخدام مولدات الأرقام العشوائية d على[0،1){\displaystyle [0,1)}، مولد أرقام عشوائية واحد لكل بُعد.

الشفرة الزائفة

V := generateSamples( n ) // توليد n عينة في مكعب الوحدة. لكل p ∈ V ، لكل q ∈ V \{p} ، إذا كانت المسافة ( p ، q ) ≤ r ، فأضف اتصالًا ( p ، q ) // أضف الحافة (p، q) إلى بنية بيانات الحافة. ​​نهاية الشرط نهاية الحلقة نهاية الحلقة

بما أن هذه الخوارزمية غير قابلة للتوسع (كل رأس يحتاج إلى معلومات عن كل رأس آخر)، فقد قدم كل من Holtgrewe et al. و Funke et al. خوارزميات جديدة لهذه المشكلة.

الخوارزميات الموزعة

هولتغروي وآخرون

كانت هذه الخوارزمية، التي اقترحها هولتغروي وآخرون، أول خوارزمية لتوليد RGG موزعة للبعد الثاني. [ 6 ] وهي تقسم المربع الواحد إلى خلايا متساوية الحجم بطول ضلع لا يقل عنر{\displaystyle r}بالنسبة لعدد معينP=ص2{\displaystyle P=p^{2}}من بين المعالجات، يتم تخصيص معالج لكل منهاكص×كص{\textstyle {k \over p}\times {k \over p}}الخلايا، حيثك=⌊1/ر⌋.{\textstyle k=\left\lfloor {1/r}\right\rfloor .}لتبسيط الأمور،P{\textstyle P}يُفترض أن يكون عددًا مربعًا، ولكن يمكن تعميم ذلك على أي عدد من المعالجات. ثم يقوم كل معالج بتوليدنP{\textstyle {\frac {n}{P}}}يتم توزيع الرؤوس على أصحابها. ثم تُرتّب الرؤوس حسب رقم الخلية التي تقع فيها، باستخدام خوارزمية الفرز السريع على سبيل المثال . بعد ذلك، يرسل كل معالج معلومات الرؤوس في الخلايا الحدودية إلى المعالجات المجاورة له، بحيث يمكن لكل وحدة معالجة حساب الحواف في قسمها بشكل مستقل عن الوحدات الأخرى. زمن التشغيل المتوقع هويا(نPسجل⁡نP){\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}يُعطى الحد الأعلى لتكلفة الاتصال لهذه الخوارزمية بواسطةتيألل-تo-ألل(ن/P،P)+تيألل-تo-ألل(1،P)+تيصoأنانت-تo-صoأنانت(ن/(ك⋅P)+2){\displaystyle T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)}، أينتيألل-تo-ألل(ل،ج){\displaystyle T_{all-to-all}(l,c)}يشير إلى الوقت اللازم لإجراء اتصال شامل بين جميع الأطراف برسائل طولها l بت إلى c من شركاء الاتصال.تيصoأنانت-تo-صoأنانت(ل){\displaystyle T_{point-to-point}(l)}هو الوقت المستغرق للاتصال من نقطة إلى نقطة لرسالة طولها l بت.

بما أن هذه الخوارزمية ليست خالية من الاتصال، فقد اقترح فونك وآخرون [ 6 ] مولد RGG موزع قابل للتوسع للأبعاد الأعلى، والذي يعمل بدون أي اتصال بين وحدات المعالجة.

فونكي وآخرون

الأسلوب المستخدم في هذه الخوارزمية [ 6 ] مشابه لأسلوب هولتغروي: تقسيم المكعب الواحد إلى أجزاء متساوية الحجم، طول ضلعها لا يقل عن r . لذا، في حالة d = 2، ستكون هذه الأجزاء مربعة، وفي حالة d = 3، ستكون مكعبات. وبما أنه لا يمكن استيعاب أكثر من⌊1/ر⌋{\textstyle {\left\lfloor {1/r}\right\rfloor }}عدد الأجزاء لكل بُعد، ويتم تحديد عدد الأجزاء بحد أقصى⌊1/ر⌋د{\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}كما في السابق، يتم تخصيص معالج لكل معالج⌊1/ر⌋دP{\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}تُقسّم البيانات إلى أجزاء، حيث يُولّد كل معالج الرؤوس. ولتحقيق عملية خالية من الاتصالات، يُولّد كل معالج نفس الرؤوس في الأجزاء المجاورة باستخدام التوزيع العشوائي الزائف لدوال التجزئة المُهيأة . وبهذه الطريقة، يحسب كل معالج نفس الرؤوس، ولا حاجة لتبادل معلومات الرؤوس.

بالنسبة للبعد الثالث، أظهر فونك وآخرون أن وقت التشغيل المتوقع هويا(م+نP+سجل⁡P){\textstyle O({\frac {m+n}{P}}+\log {P})}، دون أي تكلفة للاتصال بين وحدات المعالجة.

ملكيات

الرؤوس المعزولة والاتصال

في الحالة الخاصة التيد=2{\textstyle d=2}احتمالية أن يكون رأس واحد معزولاً في شبكة RGG هي(1-πر2)ن-1{\textstyle (1-\pi r^{2})^{n-1}}[ 7 ] ليكن​X{\textstyle X}ليكن المتغير العشوائي الذي يحسب عدد الرؤوس المعزولة. إذن، القيمة المتوقعة لـX{\textstyle X}يكونهـ(X)=ن(1-πر2)ن-1=نهـ-πر2ن-يا(ر4ن){\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n)}. على المدىμ=نهـ-πر2ن{\textstyle \mu =ne^{-\pi r^{2}n}}يوفر معلومات حول اتصال شبكة RGG. لـμ⟶0{\textstyle \mu \longrightarrow 0}، فإن RGG متصلة بشكل شبه مؤكد تقاربياً.μ⟶∞{\displaystyle \mu \longrightarrow \infty }، فإن RGG منفصل بشكل شبه مؤكد تقريبًا. و لـμ=Θ(1){\textstyle \mu =\Theta (1)}، يحتوي RGG على مكون ضخم يغطي أكثر منن2{\textstyle {\frac {n}{2}}}الرؤوس وX{\displaystyle X}يتم توزيعها وفقًا لتوزيع بواسون ذي المعاملμ{\displaystyle \mu }ويترتب على ذلك أنه إذاμ=Θ(1){\textstyle \mu =\Theta (1)}، احتمال أن تكون شبكة RGG متصلة هوP[X=0]∼هـ-μ{\textstyle P[X=0]\sim e^{-\mu }}واحتمالية عدم اتصال RGG هيP[X>0]∼1-هـ-μ{\textstyle P[X>0]\sim 1-e^{-\mu }}.

لأيلص{\textstyle l_{p}}-نورم (1≤ص≤∞{\textstyle 1\leq p\leq \infty }) ولأي عدد من الأبعادد>2{\displaystyle d>2}تمتلك شبكة RGG عتبة اتصال حادة عندر∼(ln⁡(ن)αص،دن)1د{\textstyle r\sim \left({\ln(n) \over \alpha _{p,d}n}\right)^{1 \over d}}مع ثابتαص،د{\displaystyle \alpha _{p,d}}في الحالة الخاصة للفضاء ثنائي الأبعاد والمعيار الإقليدي (د=2{\displaystyle d=2}وص=2{\displaystyle p=2}وهذا ينتج عنهر∼ln⁡(ن)πن{\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}.

الهاميلتونية

لقد ثبت أنه في الحالة ثنائية الأبعاد، فإن العتبةر∼ln⁡(ن)πن{\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}كما يوفر معلومات حول وجود دورة هاميلتونية ( مسار هاميلتوني ). [ 8 ] لأيϵ>0{\displaystyle \epsilon >0}، لور∼ln⁡(ن)(π+ϵ)ن{\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}إذاً، فإنّ RGG لا تحتوي على دورة هاميلتونية بشكل شبه مؤكد، وإذار∼ln⁡(ن)(π-ϵ)ن{\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}لأيϵ>0{\textstyle \epsilon >0}، إذن فإن RGG لديه دورة هاميلتونية بشكل شبه مؤكد.

معامل التجميع

يعتمد معامل التجميع لشبكات RGG فقط على بُعد d للفضاء الأساسي [ 0,1) d . معامل التجميع هو [ 9 ]

جد=1-حد(1){\textstyle C_{d}=1-H_{d}(1)}حتىد{\displaystyle d}وجد=32-حد(12){\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}للفرديد{\displaystyle d}أينحد(x)=1π∑أنا=xد2Γ(أنا)Γ(أنا+12)(34)أنا+12{\displaystyle H_{d}(x)={1 \over {\sqrt {\pi }}}\sum _{i=x}^{d \over 2}{\Gamma (i) \over \Gamma (i+{1 \over 2})}\left({3 \over 4}\right)^{i+{1 \over 2}}}للأحجام الكبيرةد{\displaystyle d}، وهذا يتبسط إلىجد∼32πد(34)د+12{\displaystyle C_{d}\sim 3{\sqrt {2 \over \pi d}}\left({3 \over 4}\right)^{d+1 \over 2}}.

الرسوم البيانية الهندسية العشوائية المعممة

في عام 1988، عمّم برنارد واكسمان [ 10 ] نموذج RGG القياسي من خلال تقديم دالة اتصال احتمالية بدلاً من الدالة الحتمية التي اقترحها جيلبرت. وكان المثال الذي قدمه واكسمان عبارة عن دالة أسية ممتدة حيث توجد عقدتانأنا{\displaystyle i}وج{\displaystyle j}الاتصال باحتمالية معطاة بواسطةحأناج=βهـ-رأناجر0{\textstyle H_{ij}=\beta e^{-{r_{ij} \over r_{0}}}}أينرأناج{\displaystyle r_{ij}}هو الفصل الإقليدي وβ{\displaystyle \beta }،ر0{\displaystyle r_{0}}هي معلمات يحددها النظام. يُشار إلى هذا النوع من الرسوم البيانية الهندسية العشوائية ذات دالة الاتصال الاحتمالية غالبًا باسم الرسم البياني الهندسي العشوائي المرن، والذي يمتلك الآن مصدرين للعشوائية؛ موقع العقد (الرؤوس) وتكوين الروابط (الحواف). وقد تم تعميم دالة الاتصال هذه بشكل أكبر في الأدبيات.حأناج=βهـ-(رأناجر0)η{\textstyle H_{ij}=\beta e^{-\left({r_{ij} \over r_{0}}\right)^{\eta }}}والتي تُستخدم غالبًا لدراسة الشبكات اللاسلكية دون تداخل. المعاملη{\displaystyle \eta }يمثل هذا كيفية اضمحلال الإشارة مع المسافة، عندماη=2{\displaystyle \eta =2}مساحة حرة،η>2{\displaystyle \eta >2}تُحاكي النماذج بيئة أكثر ازدحامًا مثل بلدة (= 6 نماذج لمدن مثل نيويورك) بينماη<2{\displaystyle \eta <2}تُحاكي هذه النماذج بيئات عاكسة للغاية. نلاحظ ذلك بالنسبة لـη=1{\displaystyle \eta =1}هو نموذج واكسمان، بينما هوη→∞{\displaystyle \eta \to \infty }وβ=1{\textstyle \beta =1}لدينا نموذج RGG القياسي. وبشكل بديهي، تُجسد هذه الأنواع من دوال الاتصال كيفية تناقص احتمالية إنشاء رابط مع المسافة.

نظرة عامة على بعض نتائج Soft RGG

في حالة الكثافة العالية لشبكة ذات دالة اتصال أسية، يكون عدد العقد المعزولة موزعًا وفقًا لتوزيع بواسون، وتحتوي الشبكة الناتجة على مكون عملاق فريد وعقد معزولة فقط. [ 11 ] لذلك، بضمان عدم وجود عقد معزولة، تكون الشبكة في حالة الكثافة العالية متصلة بالكامل؛ على غرار النتائج الموضحة في [ 12 ] لنموذج القرص. غالبًا ما تُدرس خصائص هذه الشبكات، مثل مركزية الوساطة [ 13 ] والاتصال [ 11 ]، في حالة الكثافة العالية.→∞{\displaystyle \to \infty }وهذا يعني غالبًا أن تأثيرات الحدود تصبح ضئيلة. مع ذلك، في الواقع العملي حيث تكون الشبكات محدودة، وإن كانت قد تكون كثيفة للغاية، فإن تأثيرات الحدود ستؤثر على الاتصال الكامل؛ في الواقع، أظهرت الدراسة [ 14 ] أن الاتصال الكامل، باستخدام دالة اتصال أسية، يتأثر بشكل كبير بتأثيرات الحدود، حيث تقل احتمالية اتصال العقد القريبة من زاوية/وجه نطاق ما مقارنةً بتلك الموجودة في الجزء الأكبر من الشبكة. ونتيجةً لذلك، يمكن التعبير عن الاتصال الكامل كمجموع مساهمات الجزء الأكبر من الشبكة وحدودها الهندسية. وقد أظهر تحليل أكثر عمومية لدوال الاتصال في الشبكات اللاسلكية أن احتمالية الاتصال الكامل يمكن تقريبها جيدًا من خلال بضع لحظات لدالة الاتصال وهندسة المنطقة. [ 15 ]

مراجع

  1. ↑ أنطونيوني، ألبرتو؛ توماسيني، ماركو (28 سبتمبر 2012). "ارتباطات الدرجات في الرسوم البيانية الهندسية العشوائية". مجلة Physical Review E. 86 ( 3) 037101. arXiv : 1207.2573 . Bibcode : 2012PhRvE..86c7101A . doi : 10.1103/ PhysRevE.86.037101 . PMID 23031054. S2CID 14750415 .  
  2. ↑ بوبروفسكي، عمر؛ كاهل، ماثيو (2018). "طوبولوجيا المجمعات الهندسية العشوائية: دراسة استقصائية". مجلة الطوبولوجيا التطبيقية والحسابية . 1 ( 3-4 ): 331-364 . arXiv : 1409.4734 . doi : 10.1007/s41468-017-0010-0 . MR 3975557 . 
  3. ↑ جيلبرت، إدغار ن (1961). "شبكات المستوية العشوائية". مجلة جمعية الرياضيات الصناعية والتطبيقية . 9 (4): 533-543 . doi : 10.1137/0109045 .
  4. ↑ نيكوفي، مازيار (28 يونيو 2007). "انتشار الديدان في الشبكات اللاسلكية المخصصة". المجلة الجديدة للفيزياء . 9 (6): 189. arXiv : 0707.2293 . Bibcode : 2007NJPh....9..189N . doi : 10.1088/1367-2630/9/6/189 . S2CID 203944 . 
  5. ↑ بنروز، ماثيو. (2003). الرسوم البيانية الهندسية العشوائية . أكسفورد: مطبعة جامعة أكسفورد. ISBN 0-19-850626-0. OCLC 51316118 . 
  6. 1 2 3 فون لوز، موريتز؛ ستراش، دارين؛ شولز، كريستيان؛ بنشوك، مانويل؛ ساندرز، بيتر؛ ماير، أولريش؛ لام، سيباستيان؛ فونكه، دانيال (2017-10-20). "توليد الرسوم البيانية الموزعة على نطاق واسع بدون اتصال". arXiv : 1710.07565v3 [ cs.DC ].
  7. ↑ بيريز، خافيير؛ ميتشه، ديتر؛ دياز، جوزيب (13-02-2007). "الرسوم البيانية الهندسية العشوائية الديناميكية". arXiv : cs/0702074 .
  8. ↑ بيريز، إكس.؛ ميتش، دي.؛ دياز، ج. (2006-07-07). "عتبة حادة لهاملتونية الرسوم البيانية الهندسية العشوائية". arXiv : cs/0607023 .
  9. ↑ كريستنسن، مايكل؛ دال، جاسبر (1 مارس 2002). "الرسوم البيانية الهندسية العشوائية". مجلة Physical Review E. 66 ( 1 الجزء 2) 016121. arXiv : cond - mat/0203026 . Bibcode : 2002PhRvE..66a6121D . doi : 10.1103/PhysRevE.66.016121 . PMID 12241440. S2CID 15193516 .  
  10. ↑ واكسمان، برنارد م (1988). "توجيه الاتصالات متعددة النقاط". مجلة IEEE للمجالات المختارة في الاتصالات . 6 (9): 1617-1622 . doi : 10.1109/49.12889 .
  11. 1 2 ماو، جي؛ أندرسون، بي دي (2013). "اتصال الشبكات اللاسلكية الكبيرة في ظل نموذج اتصال عام". معاملات IEEE في نظرية المعلومات . 59 (3): 1761-1772 . Bibcode : 2013ITIT...59.1761M . doi : 10.1109/tit.2012.2228894 . S2CID 3027610 . 
  12. ↑ بينروز، ماثيو د (1997). "أطول حافة في الشجرة الممتدة الدنيا العشوائية". حوليات الاحتمالات التطبيقية : 340-361.
  13. ↑ جايلز، ألكسندر ب.؛ جورجيو، أوريستيس؛ ديتمان، كارل ب. (2015). "مركزية الوساطة في الشبكات الهندسية العشوائية الكثيفة". المؤتمر الدولي للاتصالات IEEE لعام 2015 (ICC) . الصفحات 6450-6455 . arXiv : 1410.8521 . Bibcode : 2014arXiv1410.8521K . doi : 10.1109/ICC.2015.7249352 . ISBN  978-1-4673-6432-4. S2CID 928409 . 
  14. ↑ كون، ج؛ ديتمان، سي بي؛ جورجيو، أو (2012). "الاتصال الكامل: الزوايا والحواف والوجوه". مجلة الفيزياء الإحصائية . 147 (4): 758-778 . arXiv : 1201.3123 . Bibcode : 2012JSP...147..758C . doi : 10.1007/s10955-012-0493-y . S2CID 18794396 . 
  15. ↑ ديتمان، سي بي؛ جورجيو، أو (2016). "الرسوم البيانية الهندسية العشوائية ذات دوال الاتصال العامة". مجلة Physical Review E. 93 ( 3) 032313. arXiv : 1411.3617 . Bibcode : 2016PhRvE..93c2313D . doi : 10.1103 / physreve.93.032313 . PMID 27078372. S2CID 124506496 .