نموذج الكتل العشوائية (Stochastic Block Model — SBM) — الكشف الاحتمالي عن المجتمعات في الشبكات
- السنة
- 1983
- النوع
- Probabilistic generative graph model
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
نموذج الكتل العشوائية (SBM)، الذي قدمه Holland و Laskey و Leinhardt (1983)، هو نموذج توليدي احتمالي للرسوم البيانية يقوم بتعيين العقد إلى كتل كامنة ويقدر احتمالات الاتصال بين الكتل بشكل بارامتري. إنه النهج الأساسي للكشف عن المجتمعات، وتحديد النواة المحيطية، واكتشاف الهياكل الهرمية في تحليل الشبكات.
الفكرة الحدسية وراء الطريقة
تخيل شبكة اجتماعية حيث يتجمع الأشخاص في مجموعات - زملاء، عائلة، فرق رياضية - وتكون الاتصالات داخل المجموعة أكثر احتمالاً من الاتصالات بين المجموعات. يضفي نموذج الكتل العشوائية الطابع الرسمي على هذه الحدس: فهو يفترض وجود تسمية مجموعة مخفية لكل عقدة، وأن احتمال وجود حافة بين أي عقدتين يعتمد فقط على المجموعات التي تنتمي إليها هاتان العقدتان. يعني ملاءمة النموذج إيجاد التسميات المخفية التي تفسر نمط الحواف المرصود على أفضل وجه. النتيجة هي تقسيم مبدئي للشبكة إلى كتل، مدعوم إحصائيًا، دون الحاجة إلى أن تكون المجموعات تجمعات كثيفة - يستوعب النموذج هياكل النواة المحيطية وحتى الأنماط غير المتجانسة حيث تتجاوز الاتصالات بين المجموعات تلك التي داخل المجموعات.
التاريخ
تم تقديم نموذج الكتل العشوائية بواسطة Holland و Laskey و Leinhardt في ورقتهم عام 1983 حول الشبكات الاجتماعية كتعميم احتمالي لأعمال النمذجة الكتلية السابقة في تحليل الشبكات الاجتماعية. لمدة عقدين ظلت أداة نظرية في المقام الأول؛ اكتسبت زخمًا عمليًا مع تطوير خوارزميات الاستدلال القابلة للتطوير - variational EM و MCMC - في العقد الأول من القرن الحادي والعشرين. تم تقديم نموذج الكتل العشوائية المصحح بالدرجة بواسطة Karrer و Newman (2011) لمعالجة مشكلة عدم تجانس الدرجة. قامت مراجعة Lee و Wilkinson عام 2019 في Applied Network Science بتوحيد عائلة الامتدادات، والتي تغطي نماذج التقسيم المزروعة، و SBM ذات العضوية المختلطة، والتنويعات الهرمية. اليوم، يعد SBM ونسله الإطار الاحتمالي المرجعي للكشف عن المجتمعات وتجميع الرسوم البيانية.
متى تُستخدم
استخدم نموذج الكتل العشوائية عندما يكون لديك شبكة تحتوي على 50 عقدة على الأقل وتريد اكتشاف بنية مجموعة كامنة دون افتراض أن المجموعات يجب أن تكون تجمعات كثيفة. إنه مناسب للرسوم البيانية الموجهة أو غير الموجهة، الموزونة أو غير الموزونة، ويناسب مهام الاستكشاف وكذلك التصنيف. يُفضل تنويع DCSBM عندما تختلف درجات العقد بشكل كبير. إذا كانت الشبكة تحتوي على أقل من 20 عقدة، فلا يمكن تقدير بنية المجتمع بشكل موثوق ويجب استخدام مقاييس وصفية أبسط بدلاً من ذلك. الافتراضات: عضويات الكتل كامنة وغير مرصودة؛ يُفترض أن مصفوفة اتصال الكتل متجانسة داخل كل زوج من الكتل؛ ويجب اختيار K بواسطة BIC أو عامل بايز بدلاً من تحديده بشكل عشوائي.
الحدود والاعتبارات
- يتطلب ما لا يقل عن 50 عقدة تقريبًا للاستدلال الموثوق؛ الرسوم البيانية الصغيرة جدًا تنتج حلولاً غير مستقرة.
- الاستدلال مكلف حسابيًا للرسوم البيانية الكبيرة: يلزم استخدام variational EM أو MCMC، ولا يضمن التقارب.
- يفشل افتراض التجانس لنموذج الكتل العشوائية الأساسي داخل أزواج الكتل عندما تختلف معدلات الاتصال داخل الكتلة - يخفف DCSBM هذا ولكنه لا يقضي عليه.
- لا يزال اختيار الكتلة عبر BIC أو عامل بايز يقلل من التجزئة أو يفرط في تجزئتها إذا كانت الشبكة تحتوي على مجتمعات منفصلة بشكل ضعيف.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- إطار عمل احتمالي مبدئي يسمح باختيار النموذج عبر BIC أو عامل بايز، متجنبًا خيارات المعلمات العشوائية.
- يستوعب مجموعة واسعة من الأنماط الهيكلية - المجتمعات، النواة المحيطية، الثنائية، والهرمية - بما يتجاوز افتراض التجمع الكثيف للطرق الخوارزمية.
- يعالج التنويع المصحح بالدرجة الرسوم البيانية ذات توزيعات الدرجات غير المتجانسة والمحاور دون تشويه تعيينات الكتل.
- يوفر احتمالات عضوية لاحقة، مما يتيح تعيينات عقد ناعمة أو غير مؤكدة بدلاً من التقسيمات الصلبة.
التطبيقات
- الكشف عن مجتمعات البحث في شبكات الاقتباس والتعاون في العلوم الاجتماعية والطبيعية.
- تحديد الوحدات الوظيفية في الشبكات البيولوجية مثل تفاعل البروتين والرسوم البيانية المشتركة للتعبير الجيني.
- اكتشاف شرائح العملاء أو حلقات الاحتيال في الشبكات المعاملاتية والمالية.
- توصيف بنية النواة المحيطية في شبكات التجارة بين المنظمات أو بين البلدان.
- قياس وتقييم خوارزميات الكشف عن المجتمع الأخرى باستخدام الرسوم البيانية الاصطناعية التي تم إنشاؤها بواسطة SBM كحقيقة أساسية.
كيف يعمل
كيف يعمل
يحدد المحلل نطاقًا مرشحًا لعدد الكتل K ويختار تنويعًا: يفترض نموذج الكتل العشوائية الأساسي توزيع درجة متجانس داخل الكتلة، بينما يضيف نموذج الكتل العشوائية المصحح بالدرجة (DCSBM) معلمات درجة على مستوى العقدة للتعامل مع المحاور وتسلسلات الدرجات غير المتجانسة. يعتمد اختيار التنويع على توزيع الدرجة للرسم البياني المرصود.
بالنظر إلى مصفوفة التجاور، يقدر النموذج عضويات الكتل ومصفوفة K×K لاحتمالات الاتصال باستخدام خوارزمية استدلال. بالنسبة للرسوم البيانية الصغيرة إلى المتوسطة، يكون تعظيم الدقيق ممكنًا؛ بالنسبة للرسوم البيانية الكبيرة، يتم استخدام توقع التعظيم المتغير (variational EM) أو أخذ عينات سلسلة ماركوف مونت كارلو (MCMC) لجعل الاستدلال قابلاً للتتبع.
عدد الكتل K غير معروف مسبقًا ويجب اختياره من البيانات. معايير الاختيار المفضلة هي معيار المعلومات البايزي (BIC) وعامل بايز، وكلاهما يعاقب على تعقيد النموذج ويختار K الذي يوازن بشكل أفضل بين الملاءمة والبارسيموني. مبدأ الحد الأدنى لطول الوصف (MDL) هو أساس تطبيق graph-tool.
بمجرد تحديد K الأمثل وتعيينات الكتل، يتم فحص مصفوفة اتصال الكتل لوصف الهيكل: تتوافق الكتل المتجانسة مع المجتمعات، والكتل غير المتجانسة مع الأنماط الشبيهة بالثنائية، والملفات الشخصية المختلطة مع ترتيبات النواة المحيطية. يتم الإبلاغ عن عضويات العقد مع احتمالات لاحقة حيث توفرها خوارزمية الاستدلال.
الأخطاء الشائعة
- تحديد K بشكل عشوائي بدلاً من اختياره بواسطة BIC أو عامل بايز ينتج عنه تقسيمات غير موثوقة - استخدم دائمًا معيار اختيار نموذج مبدئي.
- تطبيق نموذج الكتل العشوائية الأساسي على رسم بياني بتسلسل درجة غير متجانس (محاور، توزيع درجة قانون القوة) يضخم تقديرات عدد الكتل؛ استخدم DCSBM بدلاً من ذلك.
- معالجة عضوية الكتلة على أنها مؤكدة عندما يكون الاحتمال منتشرًا فوق الثقة - أبلغ عن عدم اليقين عند توفره.
- خلط مخرجات SBM مع المجتمعات الحقيقية: يجد النموذج بنية كامنة معقولة إحصائيًا، وليس بالضرورة مجموعات ذات معنى اجتماعي. تحقق من صحة المعرفة بالمجال.
- تشغيل SBM على أقل من 20 عقدة ينتج عنه حلول منحلة - ارجع إلى مقاييس الشبكة الوصفية أو الكشف البسيط عن المجتمع للرسوم البيانية الصغيرة.
الأسئلة الشائعة
كيف يختلف نموذج الكتل العشوائية عن الكشف عن المجتمع القائم على النمطية؟
تعظيم النمطية (مثل Louvain، Leiden) يحسن هدفًا استدلاليًا يفترض ضمنيًا مجتمعات متجانسة ومتساوية الحجم تقريبًا ولديه حد دقة معروف يمنع اكتشاف المجتمعات الصغيرة. SBM هو نموذج توليدي احتمالي بافتراضات صريحة؛ يتم اختيار عدد الكتل عن طريق اختيار النموذج (BIC أو عامل بايز) بدلاً من التحسين الاستدلالي، ويمكنه اكتشاف الهياكل غير المتجانسة والنواة المحيطية التي تفوتها الطرق القائمة على النمطية.
متى يجب أن أستخدم DCSBM بدلاً من SBM الأساسي؟
استخدم DCSBM عندما يكون توزيع درجة العقدة غير متجانس - على سبيل المثال، عندما تستحوذ مجموعة صغيرة من المحاور على نسبة كبيرة من الحواف، أو عندما يتبع تسلسل الدرجة قانون قوة تقريبي. يعامل SBM الأساسي جميع العقد داخل الكتلة على أنها قابلة للتبديل، مما يتسبب في سحب المحاور إلى كتل زائفة خاصة بها. يضيف DCSBM حد تصحيح الدرجة الذي يفصل الموضع الهيكلي عن الدرجة، مما ينتج عنه تعيينات كتل أكثر قابلية للتفسير في مثل هذه الرسوم البيانية.
كيف أختار عدد الكتل K؟
قم بملاءمة النماذج لمجموعة من قيم K واختر القيمة التي تقلل BIC أو تزيد عامل بايز (أو تعادل تقليل طول الوصف). لا تختر K بناءً على الفحص البصري للرسم البياني أو التوقعات المسبقة. معظم التطبيقات (graph-tool، blockmodels في R) تقوم بأتمتة هذا البحث. يوصى أيضًا بتحليل الحساسية - التحقق مما إذا كانت بنية الكتلة النوعية تتغير عند تغيير K بواحد.
ما هو الحد الأدنى لحجم الشبكة ليكون SBM موثوقًا؟
يحدد السجل حدًا أدنى يبلغ 50 عقدة للاستدلال الموثوق. مع أقل من 20 عقدة، لا يمكن للنموذج تحديد بنية مجتمع ذات معنى وسيقوم بملاءمة الضوضاء - استخدم إحصائيات الشبكة الوصفية أو الكشف البسيط عن المجتمع بدلاً من ذلك. بين 20 و 50 عقدة، يجب التعامل مع النتائج على أنها استكشافية وتفسيرها بحذر.
طرق ذات صلة
المصادر
Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.
افتح مرجع DOIتم النسخ.Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.
افتح مرجع DOIتم النسخ.