نموذج الكتل العشوائي

يُعدّ نموذج الكتلة العشوائية نموذجًا توليديًا للرسوم البيانية العشوائية . يميل هذا النموذج إلى إنتاج رسوم بيانية تحتوي على مجتمعات ، وهي مجموعات فرعية من العقد تتميز بارتباطها ببعضها البعض بكثافات حواف محددة. على سبيل المثال، قد تكون الحواف أكثر شيوعًا داخل المجتمعات منها بين المجتمعات. طُرحت صياغته الرياضية لأول مرة عام 1983 في مجال تحليل الشبكات الاجتماعية بواسطة بول دبليو هولاند وآخرون ^{[ 1 ]} . يُعدّ نموذج الكتلة العشوائية مهمًا في الإحصاء ، والتعلم الآلي ، وعلم الشبكات ، حيث يُستخدم كمعيار مفيد لاستعادة بنية المجتمع في بيانات الرسوم البيانية.

يأخذ نموذج الكتلة العشوائية المعلمات التالية:

• الرقم${\displaystyle n}$من الرؤوس؛
• تقسيم مجموعة الرؤوس${\displaystyle \{1,\ldots ,n\}}$إلى مجموعات فرعية منفصلة${\displaystyle C_{1},\ldots ,C_{r}}$، والتي تسمى المجتمعات ؛
• متناظر${\displaystyle r\times r}$مصفوفة${\displaystyle P}$من احتمالات الحواف.

ثم يتم اختيار مجموعة الحواف عشوائياً على النحو التالي: أي رأسين${\displaystyle u\in C_{i}}$و${\displaystyle v\in C_{j}}$يتم ربطها بواسطة حافة باحتمالية${\displaystyle P_{ij}}$مثال على ذلك: إذا كان لدينا رسم بياني مع ${\displaystyle n}$تستعيد الرؤوس، حيث يتم أخذ عينات من الحواف كما هو موضح، المجموعات ${\displaystyle C_{1},\ldots ,C_{r}}$.

إذا كانت مصفوفة الاحتمالات ثابتة، بمعنى أن${\displaystyle P_{ij}=p}$للجميع${\displaystyle i,j}$، فالنتيجة هي نموذج إردوس-ريني${\displaystyle G(n,p)}$هذه الحالة متدهورة - يصبح التقسيم إلى مجتمعات غير ذي صلة - لكنها توضح علاقة وثيقة بنموذج إردوش-ريني.

يُعد نموذج التقسيم المزروع حالة خاصة تكون فيها قيم مصفوفة الاحتمال${\displaystyle P}$ثابتة${\displaystyle p}$على القطر وثابت آخر${\displaystyle q}$خارج القطر. وبالتالي، يشترك رأسان داخل نفس المجموعة في حافة باحتمالية${\displaystyle p}$بينما يشترك رأسان في مجتمعين مختلفين في حافة باحتمالية${\displaystyle q}$أحيانًا يُطلق على هذا النموذج المقيد اسم نموذج الكتلة العشوائية. الحالة التي${\displaystyle p>q}$يُطلق عليه نموذج التجميع ، بينما الحالة${\displaystyle p<q}$يُطلق عليه اسم "غير متجانس ".

بالعودة إلى نموذج الكتلة العشوائية العام، يُطلق على النموذج اسم النموذج التجميعي القوي إذا${\displaystyle P_{ii}>P_{jk}}$حينما${\displaystyle j\neq k}$جميع العناصر القطرية تهيمن على جميع العناصر غير القطرية. يُطلق على النموذج اسم "ضعيف التجميع" إذا كان${\displaystyle P_{ii}>P_{ij}}$حينما${\displaystyle i\neq j}$^{[ 2 ]} يُشترط في كل عنصر قطري أن يُهيمن فقط على باقي عناصر صفه وعموده. ^[ 2] توجد أشكال غير متجانسة لهذا المصطلح، وذلك بعكس جميع المتباينات. بالنسبة لبعض الخوارزميات، قد يكون الاسترداد أسهل بالنسبة لنماذج الكتل ذات الشروط المتجانسة أو غير المتجانسة من هذا الشكل. ^{[ 2 ]}

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

تُظهر نماذج الكتل العشوائية تأثير عتبة حادًا يُذكّر بعتبات الترشيح . ^{[ 7 ] [ 3 ] [ 8 ]} لنفترض أننا نسمح بالحجم${\displaystyle n}$ينمو الرسم البياني مع الحفاظ على أحجام المجتمعات بنسب ثابتة. إذا ظلت مصفوفة الاحتمالات ثابتة، تصبح مهام مثل الاسترداد الجزئي والكامل ممكنة لجميع إعدادات المعلمات غير المنحلة. ومع ذلك، إذا قمنا بتقليص مصفوفة الاحتمالات بمعدل مناسب كما${\displaystyle n}$مع زيادة القيم، نلاحظ انتقالًا حادًا في الطور: بالنسبة لبعض إعدادات المعلمات، سيصبح من الممكن تحقيق التعافي باحتمالية تقترب من 1، بينما على الجانب الآخر من عتبة المعلمة، فإن احتمالية التعافي تقترب من 0 بغض النظر عن الخوارزمية المستخدمة.

لتحقيق التعافي الجزئي، فإن المقياس المناسب هو اتخاذ${\displaystyle P_{ij}={\tilde {P}}_{ij}/n}$للثابت${\displaystyle {\tilde {P}}}$مما ينتج عنه رسوم بيانية ذات درجة متوسطة ثابتة. في حالة وجود مجموعتين متساويتين في الحجم، في نموذج التقسيم المزروع المتجانس مع مصفوفة الاحتمالية $${\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}$$ التعافي الجزئي ممكن ^{[ 4 ]} باحتمالية${\displaystyle 1-o(1)}$حينما${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}$، في حين أن أي مقدر يفشل ^{[ 3 ]} في الاستعادة الجزئية باحتمالية${\displaystyle 1-o(1)}$حينما${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}$.

للحصول على تعافي دقيق، يجب اتخاذ المقياس المناسب${\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}$مما ينتج عنه رسوم بيانية ذات درجة متوسطة لوغاريتمية. يوجد هنا عتبة مماثلة: لنموذج التقسيم المزروع التجميعي مع${\displaystyle r}$في المجتمعات متساوية الحجم، تقع العتبة عند${\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}$في الواقع، إن عتبة التعافي الدقيقة معروفة لنموذج الكتلة العشوائية العام بالكامل. ^{[ 5 ]}

من حيث المبدأ، يمكن حل مسألة الاستعادة الدقيقة ضمن نطاقها الممكن باستخدام طريقة الاحتمال الأقصى ، لكن هذا يُعادل حل مسألة قطع مقيدة أو منتظمة، مثل مسألة التنصيف الأدنى، وهي عادةً مسألة NP-كاملة . لذا، لا توجد خوارزميات فعالة معروفة قادرة على حساب تقدير الاحتمال الأقصى بشكل صحيح في أسوأ الحالات.

مع ذلك، تُحقق مجموعة واسعة من الخوارزميات أداءً جيدًا في الحالة المتوسطة، وقد ثبتت العديد من ضمانات الأداء عالية الاحتمالية للخوارزميات في كلٍ من حالات الاستعادة الجزئية والكاملة. تشمل الخوارزميات الناجحة التجميع الطيفي للرؤوس، ^{[ 9 ] [ 4 ] [ 5 ] [ 10 ]} والبرمجة شبه المحددة ، ^{[ 2 ] [ 8 ]} وأشكال نشر المعتقدات ، ^{[ 7 ] [ 11 ]} واكتشاف المجتمعات، ^{[ 12 ]} وغيرها.

توجد عدة صيغ مختلفة لهذا النموذج. إحدى التعديلات الطفيفة تُخصّص الرؤوس للمجتمعات عشوائيًا، وفقًا لتوزيع فئوي ، بدلًا من تقسيم ثابت. ^{[ 5 ]} تشمل الصيغ الأكثر أهمية نموذج الكتلة العشوائية المصحح بالدرجة، ^{[ 13 ]} ونموذج الكتلة العشوائية الهرمي، ^{[ 14 ]} ونموذج الكتلة الهندسية، ^{[ 15 ]} ونموذج الكتلة الخاضعة للرقابة، ونموذج الكتلة ذي العضوية المختلطة. ^{[ 16 ]}

يُعتبر نموذج الكتلة العشوائية نموذجًا موضوعيًا في الشبكات ثنائية الأجزاء. ^{[ 17 ]} في شبكة من المستندات والكلمات، يستطيع نموذج الكتلة العشوائية تحديد المواضيع: وهي مجموعات من الكلمات ذات المعنى المتشابه.

تسمح الرسوم البيانية الموقعة بوجود علاقات إيجابية وسلبية على حد سواء، وتُعدّ نموذجًا شائعًا للعديد من تطبيقات تحليل البيانات، مثل تجميع الارتباطات. ويمكن توسيع نموذج الكتلة العشوائية بسهولة ليشمل الرسوم البيانية الموقعة عن طريق تعيين أوزان موجبة وسالبة للحواف، أو بشكل مكافئ باستخدام الفرق بين مصفوفات التجاور لنموذجين من نماذج الكتلة العشوائية. ^{[ 18 ]}

تشجع مبادرة GraphChallenge ^{[ 19 ]} على اتباع نهج مجتمعي لتطوير حلول جديدة لتحليل الرسوم البيانية والبيانات المتفرقة المستمدة من وسائل التواصل الاجتماعي، وبيانات أجهزة الاستشعار، والبيانات العلمية، وذلك لتمكين اكتشاف العلاقات بين الأحداث أثناء تطورها ميدانيًا. ويُعدّ تقسيم الكتل العشوائي المتدفق أحد التحديات المطروحة منذ عام 2017. ^{[ 20 ]} وقد أظهر التجميع الطيفي أداءً متميزًا مقارنةً بالخوارزمية الأساسية الأصلية، بل وحتى المحسّنة ^{[ 21 ]} ، إذ يُضاهي جودة مجموعاتها مع كونه أسرع منها بعدة مراتب. ^{[ 22 ] [ 23 ]}

• نمذجة الكتل
• خوارزمية جيرفان-نيومان – خوارزمية الكشف عن المجتمعات 
• معيار لانشينيتي-فورتوناتو-راديتشي – صفحات الخوارزمية التي تعرض أوصافًا مختصرة بدون مسافات لإنشاء شبكات معيارية مع مجتمعات