مدل بلوکی تصادفی

مدل بلوکی تصادفی یک مدل تولیدی برای شبکه‌های تصادفی است. شبکه‌های تولید شده توسط این مدل شامل چندین اجتماع خواهند بود که زیرمجموعه‌هایی هستند که توزیع درجات رئوس مشابهی دارند. برای مثال ممکن است یال‌های بین رئوس در یک اجتماع بیشتر از اجتماعی دیگر باشند. مدل بلوکی تصادفی در آمار، یادگیری ماشین و علوم شبکه به عنوان یک معیار کارآمد برای شناسایی ساختارهای اجتماعی در اطلاعات مربوط به یک شبکه (گراف) اهمیت پیدا می‌کند.

تعریف ویرایش

یک مدل بلوکی تصادفی پارامترهای زیر را به عنوان ورودی دریافت می‌کند:

تعداد رأس‌های شبکه (n)
یک بردار پارش شبکه به چندین اجتماع $C_{1},\ldots ,C_{r}$ که هر کدام از $C_{i}$ ها نشان‌دهنده یک اجتماع هستند.
یک ماتریس متقارن $r\times r$ به نام P حاوی احتمال اتصال یال‌ها

پس از دریافت این پارامترها، شبکه با فرایند زیر تشکیل می‌شود:

هر راس از اجتماع i به رأسی از اجتماع j با احتمالی که در المان i و j ماتریس P ( ${\displaystyle P_{ij}}$ ) داده شده‌است متصل می‌شود. ساختاری که شکل می‌گیرد به صورت بلوک‌های داده شده در بردار پارش خواهد بود.

حالت‌های خاص ویرایش

در صورتی که ماتریس احتمال ثابت باشد، به عنوان مثال $P_{ij}=p$ برای تمامی i و jها، آن گاه شبکهٔ حاصل از این مدل یک گراف اردوش رنیی با تعداد رئوس n و احتمال اتصال p خواهد بود. این حالت خاص یک حالت تبهگن است، بدین صورت که تقسیم‌بندی شبکه به چند اجتماع عملاً بی‌معنی خواهد بود، اما ارتباط بین این دو مدل را نمایش می‌دهد.

مدل پارتیشن‌بندی انتصابی حالت خاص دیگری است که المان‌های قطری ماتریس احتمال ثابتی مانند $p$ و المان‌های غیرقطری آن ثابتی دیگر مانند $q$ هستند؛ بنابراین دو رأس در یک اجتماع با احتمال $p$ با یک یال به هم متصل می‌شوند، در حالی که دو راس در دو اجتماع مختلف دارای یک یال با احتمال $q$ خواهند بود. گاهی اوقات چیزی که به عنوان مدل بلوکی تصادفی شناخته می‌شود همین حالت خاص می‌باشد. حالتی که در آن $p>q$ باشد یک مدل همگزین و حالتی که در آن $p<q$ باشد ناهمگزین (دیگرگزین) نامیده می‌شود.

در حالت کلی مدل بلوکی تصادفی با ماتریس احتمال ${\displaystyle P_{ij}}$ ، یک شبکه همگزین قوی است در صورتی که $P_{ii}>P_{jk}$ برای المان‌هایی که j و k برابر نیستند. به عبارت دیگر در شبکهٔ همگزین قوی، المان‌های قطری از همه المان‌های غیرقطری بزرگ‌تر هستند. همچنین یک شبکه همگزین ضعیف نام خواهد داشت اگر برای ماتریس احتمال آن برای i و jهای نابرابر داشته باشیم $P_{ii}>P_{ij}$ . به عبارت دیگر در شبکهٔ همگزین ضعیف هر المان قطری تنها نیاز دارد تا از سایر المان‌های روی همان سطر و ستون بیشتر باشد.^[۱] با برعکس کردن نامساوی‌ها تعریف حالت‌های ناهمگزین قوی و ضعیف بدست می‌آید. بازیابی ساختار اجتماع در شبکه‌ها اغلب در حالت‌های بلوکی با شرایط همگزینی یا ناهمگزینی از این نوع آسان‌تر است.^[۱]

کاربردهای آماری ویرایش

بخش عمدهٔ پژوهش‌های مربوط به الگوریتم‌های شناسایی اجتماع‌ها به سه قسمت کلی تقسیم می‌شود: شناسایی، بازیابی جزئی و بازیابی کلی.

شناسایی ویرایش

هدف از الگوریتم‌های شناسایی تعیین این موضوع است که در گراف داده شده ساختار شبکه‌ای نهان وجود دارد یا خیر. به بیان دقیق‌تر، یک گراف ممکن است توسط یک مدل بلوکی با پارامترهایی خاص یا توسط مدل اردوش رنیی تولید شده باشد. وظیفهٔ الگوریتم شناسایی این است که تعیین کند کدام یک از این دو ساختار در شبکهٔ داده شده حاکم است.^[۲]

بازیابی جزئی ویرایش

هدف در بازیابی جزئی این است که ساختار اجتماع‌های موجود در شبکه به صورت تخمینی تعیین شود، به این صورت که ساختار اجتماع حدس زده شده نسبت به یک حدس تصادفی، همبستگی بیشتری با ساختار واقعی داشته باشد.^[۳]

بازیابی کلی ویرایش

در بازیابی کلی، هدف بازیابی دقیق ساختار نهفته در شبکه است. اندازه جامعه‌ها و ماتریس احتمال ممکن است شناخته شده^[۴] یا ناشناس باشند.^[۵]

حد پایین آماری و رفتار در آستانه بحرانی ویرایش

الگوریتم‌ها ویرایش

بازیابی کامل می‌تواند در محدوده‌ای توسط برآورد بیشینه درست نمایی انجام شود، اما این کار به معنی حل یک مسئله قیدی یا مسئله خوش‌رفتارسازی است که مسئله‌ای NP کامل به‌شمار می‌آید. از این رو هیچ الگوریتم مشخص و بهینه‌ای برای برآورد بیشینه درست نمایی وجود ندارد.

انواع مختلف ویرایش

چندین نسخه از این مدل وجود دارد. تنها با یک تغییر جزئی می‌توان به جای جداسازی اجتماع‌ها به صورت تعینی، رأس‌ها را به صورت احتمالی از یک تابع توزیع چنددسته‌ای دسته‌بندی کرد.^[۴] از دیگر گونه‌های این مدل می‌توان مدل بلوکی انتخابی و مدل بلوکی چندعضویتی را نام برد.^[۶]

منابع ویرایش

↑ ^۱٫۰ ^۱٫۱ Amini, Arash A. ; Levina, Elizaveta (June 2014). "On semidefinite relaxations for the block model". arXiv:1406.5647.
↑ Mossel, Elchanan; Neeman, Joe; Sly, Allan (February 2012). "Stochastic Block Models and Reconstruction". arXiv:1202.1499.
↑ Massoulie, Laurent (November 2013). "Community detection thresholds and the weak Ramanujan property". arXiv:1311.3085.
↑ ^۴٫۰ ^۴٫۱ Abbe, Emmanuel; Sandon, Colin (March 2015). "Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms". arXiv:1503.00609. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «as15a» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
↑ Abbe, Emmanuel; Sandon, Colin (June 2015). "Recovering communities in the general stochastic block model without knowing the parameters". arXiv:1506.03729. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «as15b» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
↑ Airoldi, Edoardo; Blei, David; Feinberg, Stephen; Xing, Eric (May 2007). "Mixed membership stochastic blockmodels". arXiv:0705.4485.

خطای یادکرد: برچسپ <ref> که با نام «decelle11» درون <references> تعریف شده، در متن قبل از آن استفاده نشده است.
خطای یادکرد: برچسپ <ref> که با نام «abh14» درون <references> تعریف شده، در متن قبل از آن استفاده نشده است.
خطای یادکرد: برچسپ <ref> که با نام «lr15» درون <references> تعریف شده، در متن قبل از آن استفاده نشده است.
خطای یادکرد: برچسپ <ref> که با نام «krzakala-pnas» درون <references> تعریف شده، در متن قبل از آن استفاده نشده است.

[al14-1] ۱٫۰ ^۱٫۱ Amini, Arash A. ; Levina, Elizaveta (June 2014). "On semidefinite relaxations for the block model". arXiv:1406.5647.

[mns12-2] Mossel, Elchanan; Neeman, Joe; Sly, Allan (February 2012). "Stochastic Block Models and Reconstruction". arXiv:1202.1499.

[mas13-3] Massoulie, Laurent (November 2013). "Community detection thresholds and the weak Ramanujan property". arXiv:1311.3085.

[as15a-4] ۴٫۰ ^۴٫۱ Abbe, Emmanuel; Sandon, Colin (March 2015). "Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms". arXiv:1503.00609. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «as15a» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).

[as15b-5] Abbe, Emmanuel; Sandon, Colin (June 2015). "Recovering communities in the general stochastic block model without knowing the parameters". arXiv:1506.03729. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «as15b» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).

[ar1-6] Airoldi, Edoardo; Blei, David; Feinberg, Stephen; Xing, Eric (May 2007). "Mixed membership stochastic blockmodels". arXiv:0705.4485.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]