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

تحلیل مدولاریتی

معرفی‌شده توسط
Newman, M. E. J. & Girvan, M.
سال
2004
نوع
Community detection / graph partitioning
خانواده
Network science

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

اندازه قلم

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

تحلیل مدولاریتی یک روش علم شبکه است که توسط نیومن و گیروان در سال ۲۰۰۴ فرموله شد و ساختار جامعه را در گراف‌ها با اندازه‌گیری اینکه آیا یال‌ها در درون گروه‌ها بیشتر از حد انتظار متمرکز هستند، تشخیص می‌دهد. شاخص کیفی اسکالر Q آن الگوریتم‌هایی را هدایت می‌کند که گره‌ها را به خوشه‌های منسجم تقسیم می‌کنند و آن را به پذیرفته‌شده‌ترین چارچوب برای تشخیص جامعه در شبکه‌های اجتماعی، بیولوژیکی و فناورانه تبدیل کرده است.

شهود پشت روش

اگر تمام یال‌های یک شبکه را به طور تصادفی بازآرایی کنید و درجه هر گره را حفظ کنید، یک مدل پوچ (null model) بدون جوامع واقعی به دست خواهید آورد. مدولاریتی توزیع واقعی یال‌ها را با این مدل پوچ مقایسه می‌کند: اگر یک تقسیم‌بندی، یال‌های درون‌گروهی بسیار بیشتری نسبت به پیش‌بینی مدل پوچ ایجاد کند، Q بالا خواهد بود که نشان‌دهنده ساختار جامعه واقعی است. یک بهینه‌ساز، فضای تقسیم‌بندی‌های ممکن را برای تقسیمی که Q را به حداکثر می‌رساند، جستجو می‌کند و گروه‌بندی‌های طبیعی را که ساختار شبکه نشان می‌دهد، آشکار می‌سازد، بدون اینکه نیاز باشد تحلیلگر تعداد جوامع را از قبل مشخص کند.

تاریخ

تابع مدولاریتی Q در سال ۲۰۰۴ توسط نیومن و گیروان به عنوان بخشی از مجموعه‌ای از تکنیک‌های تشخیص جامعه معرفی شد. مقاله نیومن در سال ۲۰۰۶ در PNAS رویکرد طیفی به بهینه‌سازی مدولاریتی را رسمی کرد و روش لوون (بلوندل و همکاران، ۲۰۰۸) بهینه‌سازی در مقیاس بزرگ را عملی کرد و تحلیل مدولاریتی را در جامعه‌شناسی، زیست‌شناسی و علوم کامپیوتر محبوب ساخت. مشکل محدودیت وضوح توسط فورتوناتو و بارتلمی در سال ۲۰۰۷ شناسایی شد که الگوریتم‌های بهبود یافته‌ای مانند لیدن (تراگ و همکاران، ۲۰۱۹) را که جوامع ضعیف متصل را نیز اصلاح می‌کنند، ایجاد کرد.

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

هنگامی که یک مجموعه داده رابطه‌ای دارید که قابل نمایش به صورت گراف است و می‌خواهید زیرگروه‌های منسجم را بدون پیش‌فرض کردن تعداد آن‌ها شناسایی کنید، از تحلیل مدولاریتی استفاده کنید — به عنوان مثال، شناسایی جناح‌ها در شبکه‌های اجتماعی، ماژول‌های عملکردی در شبکه‌های تعامل پروتئین، یا خوشه‌های موضوعی در شبکه‌های استنادی. این روش برای گراف‌های بدون جهت و جهت‌دار با حداقل چند ده گره و ساختار یال غیربدیهی مناسب است. زمانی که شبکه خیلی کوچک است (کمتر از حدود ۳۰ گره) یا تقریباً کامل است، زمانی که وزن یال‌ها اطلاعات حیاتی را حمل می‌کنند که یک مدل پوچ باینری ساده نادیده می‌گیرد، زمانی که جوامع شناخته شده‌اند که به طور قابل توجهی همپوشانی دارند (به جای آن از روش‌های جامعه همپوشان استفاده کنید)، یا زمانی که به مرزهای آماری تست شده به جای یک هیوریستیک بهینه‌سازی نیاز دارید، از آن استفاده نکنید.

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

  • محدودیت وضوح: بهینه‌سازی مدولاریتی به طور سیستماتیک در تشخیص جوامع کوچکتر از مقیاسی که توسط اندازه شبکه تعیین می‌شود، شکست می‌خورد و ماژول‌های کوچک واقعی را ادغام می‌کند.
  • بهینه‌سازی دقیق NP-hard به این معنی است که در عمل فقط از تقریب‌ها استفاده می‌شود و اجرای متفاوت الگوریتم‌های تصادفی می‌تواند تقسیم‌بندی‌های متفاوتی ایجاد کند.
  • مدل پوچ فرض می‌کند که یک مدل پیکربندی (توالی درجه شبیه به اردوس-رنی) وجود دارد که ممکن است برای شبکه‌هایی با توزیع درجه دم سنگین یا ساختار سلسله مراتبی نامناسب باشد.
  • مرزهای سخت جامعه نمی‌توانند عضویت‌های همپوشان دنیای واقعی را نشان دهند.

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

نقاط قوت

  • نیازی به تعیین تعداد جوامع از قبل نیست؛ تقسیم‌بندی از داده‌ها پدیدار می‌شود.
  • یک اسکالر Q واحد ارائه می‌دهد که مقایسه آسان تقسیم‌بندی‌ها یا شبکه‌های مختلف را تسهیل می‌کند.
  • الگوریتم‌های تقریبی سریع (لوون، لیدن) تا میلیون‌ها گره مقیاس‌پذیر هستند.
  • برای شبکه‌های بدون جهت، جهت‌دار و وزن‌دار با افزونه‌های مناسب قابل استفاده است.
  • به طور گسترده در کتابخانه‌های استاندارد (NetworkX, igraph, Gephi) پیاده‌سازی شده است که مانع استفاده را کاهش می‌دهد.

کاربردها

  • شناسایی جناح‌های اجتماعی، اتاق‌های پژواک، یا خوشه‌های همکاری در شبکه‌های اجتماعی آنلاین و آفلاین.
  • شناسایی ماژول‌های عملکردی در شبکه‌های بیولوژیکی مانند گراف‌های تعامل پروتئین-پروتئین و تنظیم‌کننده ژن.
  • آشکارسازی خوشه‌های موضوعی یا رشته‌ای در شبکه‌های استنادی و هم‌تألیفی.
  • تقسیم‌بندی شبکه‌های مشتری یا محصول در سیستم‌های بازاریابی و توصیه‌گر.
  • تقسیم‌بندی شبکه‌های زیرساختی (شبکه‌های برق، حمل و نقل) برای تحلیل تاب‌آوری.
  • کشف جوامع موضوعی در گراف‌های پیوند یا هم‌وقوعی در زبان‌شناسی محاسباتی.

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

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

1

شبکه به صورت یک ماتریس مجاورت A (یا لیست یال معادل) نمایش داده می‌شود، که در آن ورودی A_ij برابر با ۱ است اگر گره‌های i و j به هم متصل باشند و در غیر این صورت ۰ است. درجه گره‌ها (k_i, k_j) و تعداد کل یال‌ها m به عنوان ورودی‌های فرمول مدولاریتی محاسبه می‌شوند.

2

امتیاز مدولاریتی Q به عنوان کسری از یال‌هایی که در درون جوامع قرار دارند، منهای کسری که تحت مدل پوچ پیکربندی (بازآرایی تصادفی حفظ‌کننده درجه) انتظار می‌رود، تعریف می‌شود. Q از حدود -۰.۵ تا ۱ متغیر است؛ مقادیر بالاتر از حدود ۰.۳ نشان‌دهنده ساختار جامعه معنی‌دار است.

فرمول
Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)
3

از آنجایی که جستجوی جامع در میان تمام تقسیم‌بندی‌های ممکن NP-hard است، الگوریتم‌های عملی به بهینه‌سازی تقریبی می‌پردازند. رویکردهای رایج شامل روش لوون (تجمع حریصانه)، الگوریتم لیدن (یک نوع اصلاح‌شده و سریع‌تر)، بهینه‌سازی طیفی با استفاده از بردارهای ویژه ماتریس مدولاریتی و تبرید شبیه‌سازی شده است.

4

هر گره به جامعه‌ای اختصاص داده می‌شود که Q را برای کل تقسیم‌بندی به حداکثر می‌رساند. این الگوریتم معمولاً یک دندروگرام سلسله مراتبی تولید می‌کند که امکان بازرسی ساختار جامعه را در وضوح‌های مختلف، از ابرجوامع درشت تا خوشه‌های ریز، فراهم می‌آورد.

5

تقسیم‌بندی حاصل با مقدار نهایی Q، بررسی‌های پایداری در طول چندین اجرای الگوریتم و، در جایی که حقیقت زمینی (ground truth) در دسترس است، معیارهای خارجی مانند اطلاعات متقابل نرمال‌شده ارزیابی می‌شود. Q پایین یا نتایج ناپایدار در طول اجراها نشان‌دهنده ساختار جامعه ضعیف یا غایب است.

دام‌های رایج

  • پذیرش یک اجرای منفرد از یک بهینه‌ساز تصادفی بدون بررسی پایداری در طول چندین اجرا یا بذرهای تصادفی.
  • نادیده گرفتن محدودیت وضوح و نتیجه‌گیری اینکه یک جامعه بزرگ ادغام شده واقعاً همگن است.
  • استفاده از مدولاریتی باینری بر روی یک شبکه وزن‌دار بدون تطبیق مدل پوچ برای گنجاندن وزن یال‌ها.
  • در نظر گرفتن Q بالاتر از ۰.۳ به عنوان یک آستانه جهانی برای ساختار 'خوب' بدون در نظر گرفتن نوع و اندازه شبکه.
  • ترکیب کیفیت بهینه‌سازی (Q بالا) با اعتبار تفسیری — جوامع همچنان باید به طور اساسی بررسی شوند.

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

مقدار خوب Q چیست؟

Q بالاتر از حدود ۰.۳ معمولاً به عنوان نشان‌دهنده ساختار جامعه معنی‌دار ذکر می‌شود، اما این آستانه به نوع و اندازه شبکه بستگی دارد. شبکه‌های بسیار بزرگ با ساختار ضعیف می‌توانند Q نزدیک به ۰.۱ داشته باشند و همچنان خوشه‌های قابل تفسیر را آشکار کنند، در حالی که شبکه‌های کوچک و متراکم ممکن است به Q بالاتر از ۰.۵ برسند. همیشه جوامع را به طور اساسی بررسی کنید و به تنهایی به Q تکیه نکنید.

از کدام الگوریتم باید برای حداکثر کردن Q استفاده کنم؟

الگوریتم لیدن (تراگ و همکاران، ۲۰۱۹) در حال حاضر به عنوان پیش‌فرض توصیه شده است: سریع‌تر از روش اصلی لوون است و تمایل آن به تولید جوامع ضعیف متصل را اصلاح می‌کند. برای گراف‌های بسیار بزرگ، لوون یک انتخاب عملی باقی می‌ماند. روش‌های طیفی زمانی ترجیح داده می‌شوند که نتایج تکرارپذیر و قطعی بر روی شبکه‌های کوچکتر نیاز دارید.

آیا تحلیل مدولاریتی می‌تواند جوامع همپوشان را تشخیص دهد؟

بهینه‌سازی مدولاریتی استاندارد هر گره را دقیقاً به یک جامعه اختصاص می‌دهد و نمی‌تواند همپوشانی را تشخیص دهد. اگر انتظار دارید گره‌ها به طور همزمان به چندین گروه تعلق داشته باشند، از روش‌های جامعه همپوشان مانند روش پرکولاسیون کلوخ (clique-percolation method) یا رویکردهای تجزیه ماتریس نامنفی (non-negative matrix factorization) استفاده کنید.

محدودیت وضوح چگونه بر تحلیل من تأثیر می‌گذارد؟

بهینه‌سازی مدولاریتی تمایل دارد جوامع کوچکتر از حدود sqrt(m) یال را در جوامع بزرگتر ادغام کند. این بدان معناست که خوشه‌های کوچک واقعی می‌توانند در شبکه‌های بزرگ نامرئی باشند. برای کاهش این مشکل، پارامتر وضوح (موجود در لیدن و برخی پیاده‌سازی‌های لوون) را تغییر دهید و تقسیم‌بندی‌ها را در چندین مقدار وضوح مقایسه کنید.

آیا باید تحلیل مدولاریتی را بر روی یک شبکه جهت‌دار اعمال کنم؟

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

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

منابع

  1. Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.

    باز کردن مرجع DOI
    کپی شد.
  2. Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.

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