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

آشکارسازی جامعه — خوشه‌بندی گراف در شبکه‌ها

معرفی‌شده توسط
Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
سال
2002–2019 (algorithm family)
نوع
Graph-partitioning / clustering algorithm family

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

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

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

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

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

  • بهینه‌سازی مدولاریتی مستعد بهینه‌های محلی است؛ نتایج ممکن است در اجراهای مختلف متفاوت باشند و باید به عنوان بهترین نتیجه از چندین اجرا گزارش شوند.
  • محدودیت وضوح به این معنی است که جوامع بسیار کوچک در شبکه‌های بزرگ ممکن است با هم ادغام شوند و ساختار دقیق را پنهان کنند.
  • نتایج به نحوه تعریف وزن یال‌ها حساس هستند؛ طرح‌های وزن‌دهی مختلف می‌توانند تقسیم‌بندی‌های معنادار متفاوتی را ایجاد کنند.
  • پیچیدگی گیروان-نیومن O(m²n) است و در شبکه‌های بزرگ غیرعملی است؛ لوون یا لیدن باید برای مقیاس ترجیح داده شوند.

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

نقاط قوت

  • نیاز به تعیین تعداد جوامع از قبل ندارد — اندازه تقسیم‌بندی توسط داده‌ها تعیین می‌شود.
  • مقیاس‌پذیر به شبکه‌های بزرگ: لوون و لیدن در زمان تقریباً خطی اجرا می‌شوند و آنها را برای شبکه‌هایی با میلیون‌ها گره عملی می‌سازند.
  • لیدن جوامع متصل و از نظر داخلی منسجم را تضمین می‌کند و نقص جامعه جدا از هم لوون را اصلاح می‌کند.
  • قابل اعمال بر روی شبکه‌های بدون وزن و وزن‌دار بدون فرض توزیعی بر روی داده‌ها.

کاربردها

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

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

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

1

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

2

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

3

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

4

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

دام‌های رایج

  • اجرای الگوریتم یک بار و در نظر گرفتن نتیجه واحد به عنوان حقیقت زمینی — همیشه چندین بار اجرا کنید و بهترین مدولاریتی را گزارش دهید یا از روش‌های گروهی استفاده کنید.
  • نادیده گرفتن محدودیت وضوح: در شبکه‌های پراکنده بزرگ، جوامع کوچک اما واقعی می‌توانند بدون هشدار در جوامع بزرگتر جذب شوند.
  • اعمال الگوریتم‌های مبتنی بر مدولاریتی بر روی شبکه‌هایی با کمتر از ۲۰ گره — ساختار جامعه را نمی‌توان در آن مقیاس به طور قابل اعتماد شناسایی کرد.
  • اشتباه گرفتن امتیاز مدولاریتی بالا با ساختار جامعه واقعی تأیید شده؛ مدولاریتی یک معیار کیفیت تقسیم‌بندی است، نه یک آزمون استنباطی برای اینکه آیا جوامع از نظر آماری معنی‌دار هستند یا خیر.

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

کدام الگوریتم را باید انتخاب کنم — لوون، لیدن، گیروان-نیومن، یا اینفو‌مپ؟

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

آیا نیاز دارم تعداد جوامع را از قبل مشخص کنم؟

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

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

امتیاز مدولاریتی Q یک معیار کیفیت داخلی داده را فراهم می‌کند؛ مقادیر بالاتر از حدود ۰.۳-۰.۵ نشان‌دهنده ساختار جامعه غیر بدیهی است. فراتر از آن، جوامع باید در برابر دانش دامنه، ویژگی‌های گره، یا برچسب‌های خارجی اعتبارسنجی شوند. Q بالا به تنهایی اثبات کننده اهمیت جامعه‌شناختی یا زیست‌شناختی نیست.

اگر نتایج در اجراهای مختلف متفاوت باشند چه اتفاقی می‌افتد؟

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

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

منابع

  1. Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.

    باز کردن مرجع DOI
    کپی شد.
  2. Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.

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