مدل بلوکی تصادفی
مدل بلوکی تصادفی یک مدل تولیدی برای شبکه‌های تصادفی است. شبکه‌های تولید شده توسط این مدل شامل چندین اجتماع خواهند بود که زیرمجموعه‌هایی هستند که توزیع درجات رئوس مشابهی دارند. برای مثال ممکن است یال‌های بین رئوس در یک اجتماع بیشتر از اجتماعی دیگر باشند. مدل بلوکی تصادفی در آمار، یادگیری ماشین و علوم شبکه به عنوان یک معیار کارآمد برای شناسایی ساختارهای اجتماعی در اطلاعات مربوط به یک شبکه (گراف) اهمیت پیدا می‌کند.
یک مدل بلوکی تصادفی پارامترهای زیر را به عنوان ورودی دریافت می‌کند:
پس از دریافت این پارامترها، شبکه با فرایند زیر تشکیل می‌شود:
هر راس از اجتماع i به رأسی از اجتماع j با احتمالی که در المان i و j ماتریس P (formula_4) داده شده‌است متصل می‌شود. ساختاری که شکل می‌گیرد به صورت بلوک‌های داده شده در بردار پارش خواهد بود.
در صورتی که ماتریس احتمال ثابت باشد، به عنوان مثال formula_5 برای تمامی i و jها، آن گاه شبکهٔ حاصل از این مدل یک گراف اردوش رنیی با تعداد رئوس n و احتمال اتصال p خواهد بود. این حالت خاص یک حالت تبهگن است، بدین صورت که تقسیم‌بندی شبکه به چند اجتماع عملاً بی‌معنی خواهد بود، اما ارتباط بین این دو مدل را نمایش می‌دهد.
"مدل پارتیشن‌بندی انتصابی حالت" خاص دیگری است که المان‌های قطری ماتریس احتمال ثابتی مانند formula_6 و المان‌های غیرقطری آن ثابتی دیگر مانند formula_7 هستند؛ بنابراین دو رأس در یک اجتماع با احتمال formula_6 با یک یال به هم متصل می‌شوند، در حالی که دو راس در دو اجتماع مختلف دارای یک یال با احتمال formula_7 خواهند بود. گاهی اوقات چیزی که به عنوان مدل بلوکی تصادفی شناخته می‌شود همین حالت خاص می‌باشد. حالتی که در آن formula_10 باشد یک مدل همگزین و حالتی که در آن formula_11 باشد ناهمگزین (دیگرگزین) نامیده می‌شود.
در حالت کلی مدل بلوکی تصادفی با ماتریس احتمال formula_4، یک شبکه همگزین قوی است در صورتی که formula_13 برای المان‌هایی که j و k برابر نیستند. به عبارت دیگر در شبکهٔ همگزین قوی، المان‌های قطری از همه المان‌های غیرقطری بزرگ‌تر هستند. همچنین یک شبکه همگزین ضعیف نام خواهد داشت اگر برای ماتریس احتمال آن برای i و jهای نابرابر داشته باشیم formula_14. به عبارت دیگر در شبکهٔ همگزین ضعیف هر المان قطری تنها نیاز دارد تا از سایر المان‌های روی همان سطر و ستون بیشتر باشد. با برعکس کردن نامساوی‌ها تعریف حالت‌های ناهمگزین قوی و ضعیف بدست می‌آید. بازیابی ساختار اجتماع در شبکه‌ها اغلب در حالت‌های بلوکی با شرایط همگزینی یا ناهمگزینی از این نوع آسان‌تر است.
بخش عمدهٔ پژوهش‌های مربوط به الگوریتم‌های شناسایی اجتماع‌ها به سه قسمت کلی تقسیم می‌شود: شناسایی، بازیابی جزئی و بازیابی کلی.
هدف از الگوریتم‌های شناسایی تعیین این موضوع است که در گراف داده شده ساختار شبکه‌ای نهان وجود دارد یا خیر. به بیان دقیق‌تر، یک گراف ممکن است توسط یک مدل بلوکی با پارامترهایی خاص یا توسط مدل اردوش رنیی تولید شده باشد. وظیفهٔ الگوریتم شناسایی این است که تعیین کند کدام یک از این دو ساختار در شبکهٔ داده شده حاکم است.
هدف در بازیابی جزئی این است که ساختار اجتماع‌های موجود در شبکه به صورت تخمینی تعیین شود، به این صورت که ساختار اجتماع حدس زده شده نسبت به یک حدس تصادفی، همبستگی بیشتری با ساختار واقعی داشته باشد.
در بازیابی کلی، هدف بازیابی دقیق ساختار نهفته در شبکه است. اندازه جامعه‌ها و ماتریس احتمال ممکن است شناخته شده یا ناشناس باشند.
بازیابی کامل می‌تواند در محدوده‌ای توسط برآورد بیشینه درست نمایی انجام شود، اما این کار به معنی حل یک مسئله قیدی یا مسئله خوش‌رفتارسازی است که مسئله‌ای NP کامل به‌شمار می‌آید. از این رو هیچ الگوریتم مشخص و بهینه‌ای برای برآورد بیشینه درست نمایی وجود ندارد.
چندین نسخه از این مدل وجود دارد. تنها با یک تغییر جزئی می‌توان به جای جداسازی اجتماع‌ها به صورت تعینی، رأس‌ها را به صورت احتمالی از یک تابع توزیع چنددسته‌ای دسته‌بندی کرد. از دیگر گونه‌های این مدل می‌توان مدل بلوکی انتخابی و مدل بلوکی چندعضویتی را نام برد.