بخشی از مقاله
چکیده
در سالهای اخیر گرایش دان شمندان به کاوش و برر سی شبکههای پیچیده1 به شدت افزایش یافته ا ست. این امر زمانی آغاز شد که دانشمندان دریافتند که بسیاری از شبکههای پیچیدهی استخراج شده از سیستمهای مصنوعی و طبیعی، ویژگیهای مشترکی را دارند که آنها را از گرافهای تصادفی متمایز میسازند. این ویژگیها عبارتند از: پدیدهی جهان کوچک2، توزیع درجات به صورت قانون توانی3 ، و ضریب خوشهبندی بالا.4 در نتیجهی این ویژگیهای ساختاری، اکثر شبکه های پیچیدهی جهان واقعی دارای ساختاری خوشهای به نام جوامع5 ه ستند.
یک جامعه زیرگرافی ا ست که در آن گرهها ات صالات زیادی با گرههای داخل جامعه دا شته و ات صالات ب سیار کمی با گرههای بیرون از جامعه دارند. به طور معمول گرههایی که عضو یک جامعه اند ویژگیهای مشترکی داشته و نقشهای مشابهی را در یک شبکه ایفا میکنند. بنابراین با تشخیص و آزمایش جوامع موجود در یک شبکه میتوان به اطلاعات مفیدی در مورد ساختار و ماهیت آن شبکه د ست یافت.
تف سیر معنایی یک جامعه به نوع شبکهی مورد مطالعه ب ستگی دارد. در شبکهی سوخت و ساز بدن، یک جامعه میتواند نشان دهندهی یک فعالیت زیستی در یک سلول باشد. در شبکهی تراکنش یک سایت تجارت الکترونیکی، یک جامعه مجموعهای از م شتریان م شابه را ن شان میدهد. در شبکهی وب نیز یک جامعه مجموعهای از صفحات با مو ضوعات یک سان را ن شان میدهد. روشهای بسیاری جهت تشخیص جوامع در شبکههای پیچیده ارائه شدهاند. این مقاله به معرفی مفاهیم اولیه، کاربردها، چالشها و روشهای حل مسئلهی تشخیص جوامع میپردازد.
کلمات کلیدی شبکهی پیچیده، تشخیص جوامع، خوشهبندی
مقدمه
آن دست یافت. اگر بخواهیم یک سیستم پیچیده را بهتر درک و توصیف کنیم نیاز داریم که آن را به صورت یک شبکه نمایش دهیم. ب سیاری از در مفهوم تئوری شبکه6، یک شبکهی پیچیده شبکهای است که یک شبکه های موجود در دنیای واقعی میتوانند تو سط یک شبکهی پیچیده سی ستم پیچیده7 را مدل میکند. این شبکه دارای ویژگیهای ساختاری مدل شو ند. شب که های بیولوژیکی، اینترنتی، اطلا عاتی، و اجت ماعی ارزشمندی است که یک شبکهی ساده مانند یک گراف تصادفی فاقد آن نمونه هایی از شبکههای پیچیده هستند. شبکههای پیچیده، توسط گراف8 ویژگیه ا ست.
سی ستمهای پیچیده، نگاهی نو به پدیدههایی ا ست که به نمایش داده می شوند. گراف در تعریف ب سیار ساده و ابتدایی آن، روشی علت ارتباط بین اجزای آن و همچنین ارتباط با دیگر پدیدهها از پیچیدگی برای بیان ارتباط میان مجموعهای از اشیاست. بالایی برخوردارند و رفتار جمعی متفاوتی را بروز میدهند. بدین معنی که با مطالعهی تکتک اجزای یک سی ستم پیچیده نمیتوان به رفتار جمعی یکی از مهمترین ویژگیهای شبکههای پیچیده، ساختار پیمانهای آنها است.
یک شبکهی پیچیده از چندین پیمانه یا جامعه تشکیل شده است که این جوامع دارای ارتباطات داخلی زیاد و ارتباطات خارجی بسیار کمی هستند. جهت تشخیص جوامع یک شبکه لازم است گراف مربوط به آن شبکه خوشه بندی شود. گام اول در مسئلهی خوشه بندی گراف، ارائهی یک تعریف کمی برای واژهی جامعه است. متأسفانه هیچ تعریفی برای این واژه وجود ندارد که مورد قبول عام باشد . به عنوان یک تعریف ابتدایی، جامعه مجموعهای از گرههاست که تعداد یالهای داخل آن مجموعه، از یالهای بین آن مجموعه با دیگر گرههای شبکه به مراتب بیشتر است. عموماً تعریفی که از یک جامعه ارائه میشود به سیستم مورد مطالعه و کاربردهای آن وابسته است.
شبکه ای با ساختار جوامع مشخص میتوان مسئ لهی تشخیص جوامع شب که های پیچ یده را در تقسیمبندی زیر قرار داد : تشخیص جوامع مجزا: 9 در این جا هدف م حاس بهی افرازی از مجموعهی گرههای شبکه است، به طوری که هر گره تنها و تنها ع ضو یک جامعه با شد. اکثر رو شهای موجود جهت ت شخیص جوامع برای حل این مسئله ارائه شدهاند. تشخیص جوامع همپوشان: 10 هدف در اینجا محاسبهی خوشهبندی نرمی از مجموعهی گره های گراف است، به طوری که یک گره میتواند به طور همزمان عضو چندین جامعه باشد.
تشخیص جوامع محلی: 11 در اینجا هدف پیدا کردن جامعهای ا ست که یک گره خاص عضو آن است. به این معنا که دیگر به دنبال خوشه بندی شبکه نیستیم؛ بلکه با در دست داشتن یک گره میخواهیم جامعهی آن گره را به دست آوریم. راهحل این مسئله میتواند در زمینه های متفاوتی از جمله سیستمهای پیشنهادگر مفید واقع شود. تشخیص جوامع در شبکههای پویا: 12 در اینجا هدف خوشهبندی شبکهای ا ست که با گذ شت زمان در حال تغییر ا ست. به این معنا که شبکه دیگر حالت ایستا ندارد، بلکه در حال رشد است .
تشخیص جوامع در شبکههای ن سبت داده شده: 13 در اینجا هدف خوشه بندی شبکهای است که هر یک از گرههای آن شامل اطلاعات و صفاتی ه ستند که به آنها ن سبت داده شدهاند. بنابراین در خو شه بندی گراف، این اطلاعات نیز مورد استفاده قرار میگیرند . ادامهی مقاله به این ترتیب ساماندهی شده ا ست. بخش 2 به معرفی چالشهای موجود در تشخیص جوامع میپردازد. بخش 3 برخی از روشهای حل مسئلهی تشخیص جوامع مجزا را بیان میکند. بخش 4 رو شهای مذکور را با یکدیگر مقای سه میکند؛ و در نهایت بخش 5 مربوط به نتیجهگیری است.
چالشهای تشخیص جوامع در شبکههای پیچیده
پیش از آنکه به معرفی روشهای حل مسئلهی تشخیص جوامع بپردازیم، لازم است با چالشهای موجود در این حوزه آشنا شویم. این چالشها عبارتند از: فراهم کردن مجموعهی داده جهت انجام عمل خوشهبندی، و ارزیابی عملکرد یک خوشهبندی. در ادامه تعدادی از مجموعه دادهها و معیارهای ارزیابی مورد استفاده در تشخیص جوامع معرفی میشوند.
مجموعه دادههای مورد استفاده
جهت حل مسئلهی تشخیص جوامع، دانشمندان روی مجموعهای از گرافهای مطمئن توافق کردهاند. این مجموعه عموماً شامل گرافهای ساخت کامپیوتری14 هستند که در آنها ساختار جوامع میتوانند به صورت دلخواهی طراحی شوند. علاوه بر این گرافها ،گرافهای دنیای واقعی15 نیز میتوانند در ارزیابی الگوریتمها مورد استفاده قرار گیرند. جهت این منظور، گرافهایی از دنیای واقعی انتخاب میشوند که به دلیل اطلاعات موجود در مورد سیستم آنها، ساختار جوامع تعریفشدهای دارند.
گرافهای ساخت کامپیوتر
مجموعهای از گرافهای ساخت کامپیوتر، تو سط مدل L بخ شی کا شته شده16 ساخته می شوند . این مدل، گرافی با g.L گره را در L گروه افرازی می کند، به طوریکه هر گروه تعداد g گره داشته باشد. گرههای همگروه با احتمال Pin و گرههای غیر همگروه با احتمال Pout به یکدیگر متصلاند. اگر Pin>Pout باشد، تراکم یالهای داخل خوشهها از تراکم یالهای بین خوشهای بیشتر خواهد بود و بنابراین گراف، ساختار خوشهای خواهد داشت.
گیروان ونیومن17 حالت خاصی از مدل L بخشی کاشته شده را ارائه دادند. آنها L را برابر4 و g را برابر32 در نظر گرفتند. جهت ارزیابی عملکرد یک الگوریتم توسط مدل گیروان و نیومن، لازم است میزان شباهت بین خوشهبندی حاصل از اجرای الگوریتم روی مدل و خوشهبندی اصلی گراف که شامل چهار خوشهی هم اندازه است، محاسبه شود.
از آنجایی که در گرافهای دنیای واقعی معمولاً درجهی گرهها یکسان نبوده و خوشه ها اندازهی برابری ندارند، مجموعهی آزمایشی دیگری تحت عنوان LFR ارائه شده ا ست. در این مجموعه، فرض میشودکه توزیع در جهی گره ها و ا ندازهی جوامع به صورت توزیع قانون توانی18 با توانهای 1 و τ2 هستند. همچنین هر گره نسبت 1- از یالهایش را با گرههای همجامعهی خود و نسبت از آنها را با گرههایی از جوامع دیگر به اشتراک میگذارد. مقداری بین صفر و یک داشته و پارامتر اختلاط میباشد.
سازندهی LFR چندین پارامتر دارد که با تغییردادن مقادیر آنها میتوان شبکههای مصنوعی متفاوتی ساخت، و با مقایسهی خوشه بندی حاصل از اجرای یک الگوریتم روی این شبکه ها وخوشه بندی اصلی شبکهها، عملکرد آن الگوریتم را مورد ارزیابی قرار داد.
گرافهای دنیای واقعی
گرافهای دنیای واقعی محدودی وجود دارند که اطلاعات دقیقی در مورد ساختار جوامع آنها وجود دارد. در ادامه به معرفی تعدادی از این گرافها میپردازیم.
کلوب کاراتهی زاکاری
زاکاری، 34 نفر از اعضای یک کلوب کاراته را به مدت دو سال تحت نظر داشت. او شبکهای از روابط دوستانهی بین این 34 نفر را ایجاد کرد. در این شبکه، هر کدام از گرهها یکی از اعضای کلوب را نشان میدهد و یالها نمایانگر رابطهی دوستی بین این افراد هستند. پس از یک مشاجره بین مدیر و مربی کلوب، شبکه به دو قسمت تقسیم شد. در نتیجهی این مشاجره، مربی کلوب جدیدی ایجاد کرده و نیمی از اعضای کلوب قبلی را به کلوب خود برد. به این ترتیب، شبکه میتواند به دو جامعه تقسیمبندی شود که حول دو گره مدیر و مربی کلوب تشکیل شدهاند .
شبکهی اجتماعی دلفینها
این شبکه، یک شبکهی اجتماعی غیر جهت دار است که از مشاهدات جامعهای از 62 دلفین طی 7 سال ایجاد شده است. در این شبکه، گرهها نشاندهندهی دلفینها، و یالها نشاندهندهی ارتباطات مکرر دلفینه است.
مجموعهی دادهی فوتبال دانشگاهی آمریکا
این مجموعهی داده، شبکهی م سابقات فوتبال آمریکایی ا ست که از 115 گره تشکیل شده است. هر کدام از این گرهها، نشاندهندهی یک تیم فوتبال میباشد. در این شبکه بین دو گره یال وجود دارد اگر بین تیمهای مربوطه، بازی رخ داده با شد . تیمها به 12 د سته تق سیم می شوند و بازیها معمولاً بین تیمهای عضو دستهی یکسان انجام میگیرند. بنابراین میتوان شبکه را متشکل از 12 جامعه دانست.
کتب سیاسی آمریکایی
این شبکه، یک شبکهی خرید کتابهای سیا سی ا ست که در آن گرهها، کتابهایی در مورد سیاست آمریکا هستند که در فروشگاه برخط فروخته میشوند. یالها نشاندهندهی جفت کتابهایی هستند که معمولاً به صورت همزمان خریداری میشوند.
مجموعهی دادهی بینوایان
این شبکه، ن شاندهندهی ارتباطات بین کاراکترهای ا صلی رمان بینوایان ویکتور هوگو میباشد. گرهها در این شبکه نشاندهندهی کاراکترها، و یالها نشاندهندهی حضور همزمان کاراکترهای مربوطه در یک یا دو فصل از رمان است.
