Skip to content
بازگشت به نتایج جست‌وجو

مدل بلوک تصادفی — تشخیص جامعه احتمالی در شبکه‌ها

سال
1983
نوع
Probabilistic generative graph model

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

مدل بلوک تصادفی (SBM)، که توسط هالند، لَسکِی و لِین‌هارت (۱۹۸۳) معرفی شد، یک مدل مولد احتمالی برای گراف‌ها است که گره‌ها را به بلوک‌های پنهان تخصیص می‌دهد و احتمالات اتصال بین بلوک‌ها را به صورت پارامتری تخمین می‌زند. این رویکرد پایه‌ای برای تشخیص جامعه، شناسایی هسته-پیرامون و کشف ساختار سلسله‌مراتبی در تحلیل شبکه است.

شهود پشت روش

یک شبکه اجتماعی را تصور کنید که در آن افراد به گروه‌هایی - همکاران، خانواده، تیم‌های ورزشی - تقسیم می‌شوند و اتصالات درون یک گروه محتمل‌تر از اتصالات بین گروه‌ها است. مدل بلوک تصادفی این شهود را فرموله می‌کند: فرض می‌کند که برای هر گره یک برچسب گروه پنهان وجود دارد و احتمال یک یال بین هر دو گره تنها به گروه‌هایی که آن دو گره به آن‌ها تعلق دارند بستگی دارد. برازش مدل به معنای یافتن برچسب‌های پنهان است که الگوی یال مشاهده‌شده را به بهترین نحو توضیح می‌دهند. نتیجه یک تقسیم‌بندی اصولی و مبتنی بر آمار شبکه به بلوک‌ها است، بدون نیاز به اینکه گروه‌ها کلیپ‌های متراکم باشند — مدل ساختارهای هسته-پیرامون و حتی الگوهای ناهمسان‌ساز را که اتصالات بین‌گروهی از اتصالات درون‌گروهی بیشتر است، در بر می‌گیرد.

تاریخ

مدل بلوک تصادفی توسط هالند، لَسکِی و لِین‌هارت در مقاله سال ۱۹۸۳ خود در Social Networks به عنوان تعمیم احتمالی کارهای قبلی مدل‌سازی بلوکی در تحلیل شبکه اجتماعی معرفی شد. برای دو دهه عمدتاً یک ابزار نظری باقی ماند؛ با توسعه الگوریتم‌های استنتاج مقیاس‌پذیر - variational EM و MCMC - در دهه ۲۰۱۰، محبوبیت عملی پیدا کرد. مدل بلوک تصادفی تصحیح‌شده با درجه توسط کارِر و نیومن (۲۰۱۱) برای رسیدگی به مشکل ناهمگنی درجه معرفی شد. بررسی سال ۲۰۱۹ توسط لی و ویلکینسون در Applied Network Science خانواده‌ای از افزونه‌ها را تثبیت کرد که مدل‌های پارتیشن کاشته شده، SBM عضویت ترکیبی و نسخه‌های سلسله‌مراتبی را پوشش می‌دهد. امروزه SBM و نوادگان آن چارچوب احتمالی مرجع برای تشخیص جامعه و خوشه‌بندی گراف هستند.

چه زمانی استفاده شود

هنگامی که شبکه‌ای با حداقل ۵۰ گره دارید و می‌خواهید ساختار گروه پنهان را بدون فرض اینکه گروه‌ها باید کلیپ‌های متراکم باشند، کشف کنید، از مدل بلوک تصادفی استفاده کنید. این مدل برای گراف‌های جهت‌دار یا بدون جهت، وزن‌دار یا بدون وزن مناسب است و هم برای وظایف اکتشافی و هم طبقه‌بندی کاربرد دارد. نسخه DCSBM زمانی ترجیح داده می‌شود که درجه گره‌ها به طور قابل توجهی متفاوت باشد. اگر گراف کمتر از ۲۰ گره داشته باشد، ساختار جامعه را نمی‌توان به طور قابل اعتماد تخمین زد و باید از معیارهای توصیفی ساده‌تر استفاده شود. مفروضات: عضویت بلوک‌ها پنهان و مشاهده نشده هستند؛ ماتریس اتصال بلوک برای هر جفت بلوک همگن فرض می‌شود؛ و K باید با BIC یا فاکتور بیز انتخاب شود نه اینکه دلخواه تعیین شود.

محدودیت‌ها و ملاحظات

  • حداقل حدود ۵۰ گره برای تخمین قابل اعتماد بلوک لازم است؛ گراف‌های بسیار کوچک راه‌حل‌های ناپایدار تولید می‌کنند.
  • استنتاج برای گراف‌های بزرگ از نظر محاسباتی پرهزینه است: نیاز به variational EM یا MCMC است و همگرایی تضمین نمی‌شود.
  • فرض همگنی SBM پایه در بین جفت بلوک‌ها زمانی که نرخ اتصال درون بلوکی متفاوت است، شکسته می‌شود - DCSBM این مشکل را کاهش می‌دهد اما کاملاً از بین نمی‌برد.
  • انتخاب بلوک از طریق BIC یا فاکتور بیز همچنان می‌تواند در صورت داشتن جوامع ضعیف جدا شده، کم یا بیش از حد تقسیم کند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

  • تشخیص جوامع تحقیقاتی در شبکه‌های استناد و همکاری در علوم اجتماعی و طبیعی.
  • شناسایی ماژول‌های عملکردی در شبکه‌های بیولوژیکی مانند گراف‌های تعامل پروتئین-پروتئین و هم‌بیانی ژن.
  • کشف بخش‌های مشتری یا حلقه‌های تقلب در شبکه‌های تراکنشی و مالی.
  • توصیف ساختار هسته-پیرامون در شبکه‌های تجاری بین سازمانی یا بین کشوری.
  • معیارسنجی و ارزیابی سایر الگوریتم‌های تشخیص جامعه با استفاده از گراف‌های مصنوعی تولید شده توسط SBM به عنوان حقیقت زمینه‌ای.

چگونه کار می‌کند

چگونه کار می‌کند

1

تحلیلگر یک دامنه کاندید برای تعداد بلوک K را مشخص می‌کند و یک نسخه را انتخاب می‌کند: SBM پایه فرض می‌کند توزیع درجه همگن درون بلوکی، در حالی که SBM تصحیح‌شده با درجه (DCSBM) پارامترهای درجه در سطح گره را برای مدیریت هاب‌ها و دنباله‌های درجه ناهمگن اضافه می‌کند. انتخاب نسخه بر اساس توزیع درجه گراف مشاهده‌شده است.

2

با توجه به ماتریس مجاورت، مدل عضویت بلوک‌ها و یک ماتریس K×K از احتمالات اتصال را با استفاده از یک الگوریتم استنتاج تخمین می‌زند. برای گراف‌های کوچک تا متوسط، حداکثرسازی دقیق امکان‌پذیر است؛ برای گراف‌های بزرگ، انتظار-بیشینه‌سازی متغیر (variational EM) یا نمونه‌برداری زنجیره مارکوف مونت کارلو (MCMC) برای قابل‌فهم کردن استنتاج استفاده می‌شود.

3

تعداد بلوک K از قبل مشخص نیست و باید از داده‌ها انتخاب شود. معیارهای انتخاب ترجیحی عبارتند از معیار اطلاعات بیزی (BIC) و فاکتور بیزی، که هر دو پیچیدگی مدل را جریمه می‌کنند و K را که بهترین تعادل بین برازش و ایجاز را برقرار می‌کند، انتخاب می‌کنند. اصل حداقل طول توصیف (MDL) اساس پیاده‌سازی graph-tool است.

4

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

دام‌های رایج

  • تعیین دلخواه K به جای انتخاب آن با BIC یا فاکتور بیز، پارتیشن‌های غیرقابل اعتماد تولید می‌کند - همیشه از یک معیار انتخاب مدل اصولی استفاده کنید.
  • اعمال SBM پایه بر روی گرافی با دنباله درجه ناهمگن (هاب‌ها، توزیع درجه قانون توان) تخمین تعداد بلوک را متورم می‌کند؛ به جای آن از DCSBM استفاده کنید.
  • در نظر گرفتن عضویت بلوک به عنوان قطعی زمانی که پسین پراکنده است، اطمینان را بیش از حد بیان می‌کند - عدم قطعیت را در صورت وجود گزارش دهید.
  • اشتباه گرفتن خروجی SBM با جوامع واقعی: مدل ساختار پنهان قابل قبولی از نظر آماری پیدا می‌کند، نه لزوماً گروه‌های معنادار جامعه‌شناختی. با دانش دامنه اعتبارسنجی کنید.
  • اجرای SBM بر روی کمتر از ۲۰ گره راه‌حل‌های تباهیده تولید می‌کند - برای گراف‌های کوچک به معیارهای توصیفی شبکه یا تشخیص جامعه ساده بازگردید.

پرسش‌های متداول

مدل بلوک تصادفی چگونه با تشخیص جامعه مبتنی بر مدولاریتی متفاوت است؟

حداکثرسازی مدولاریتی (مانند Louvain، Leiden) یک هدف ابتکاری را بهینه می‌کند که به طور ضمنی جوامع همسان‌ساز و تقریباً هم‌اندازه را فرض می‌کند و دارای حد تفکیک‌پذیری شناخته‌شده‌ای است که از تشخیص جوامع کوچک جلوگیری می‌کند. SBM یک مدل مولد احتمالی با مفروضات صریح است؛ تعداد بلوک با انتخاب مدل (BIC یا فاکتور بیز) به جای بهینه‌سازی ابتکاری انتخاب می‌شود و می‌تواند ساختارهای ناهمسان‌ساز و هسته-پیرامون را که روش‌های مبتنی بر مدولاریتی از دست می‌دهند، تشخیص دهد.

چه زمانی باید از DCSBM به جای SBM پایه استفاده کنم؟

زمانی از DCSBM استفاده کنید که توزیع درجه گره ناهمگن باشد - به عنوان مثال، زمانی که تعداد کمی هاب بخش بزرگی از یال‌ها را تشکیل می‌دهند، یا زمانی که دنباله درجه از یک قانون توان تقریبی پیروی می‌کند. SBM پایه همه گره‌ها را در یک بلوک قابل تعویض در نظر می‌گیرد، که باعث می‌شود هاب‌ها به بلوک‌های جعلی خود کشیده شوند. DCSBM یک جمله تصحیح درجه اضافه می‌کند که موقعیت ساختاری را از درجه جدا می‌کند و تخصیص بلوک قابل تفسیرتری را در چنین گراف‌هایی تولید می‌کند.

چگونه تعداد بلوک K را انتخاب کنم؟

مدل‌ها را برای طیفی از مقادیر K برازش دهید و مدلی را انتخاب کنید که BIC را حداقل کند یا فاکتور بیز را حداکثر کند (یا به طور معادل طول توصیف را حداقل کند). K را بر اساس بازرسی بصری گراف یا انتظارات قبلی انتخاب نکنید. اکثر پیاده‌سازی‌ها (graph-tool، blockmodels در R) این جستجو را خودکار می‌کنند. تحلیل حساسیت - بررسی اینکه آیا ساختار بلوک کیفی هنگام تغییر K به میزان یک تغییر می‌کند - نیز توصیه می‌شود.

حداقل اندازه شبکه برای قابل اعتماد بودن SBM چقدر است؟

رجیستری حداقل ۵۰ گره را برای استنتاج قابل اعتماد مشخص می‌کند. با کمتر از ۲۰ گره، مدل نمی‌تواند ساختار جامعه معناداری را شناسایی کند و نویز را برازش می‌دهد - به جای آن از آمار شبکه توصیفی یا تشخیص جامعه ساده استفاده کنید. نتایج بین ۲۰ تا ۵۰ گره باید به عنوان اکتشافی در نظر گرفته شوند و با احتیاط تفسیر شوند.

روش‌های مرتبط

منابع

  1. Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.

    باز کردن مرجع DOI
    کپی شد.
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

    باز کردن مرجع DOI
    کپی شد.