مدل واتس و استروگاتز

مدل واتس و استروگاتز (انگلیسی: Watts and Strogatz model) یک مدل تولید گراف تصادفی است که گراف‌هایی با ویژگی دنیای کوچک شامل طول مسیر متوسط کوتاه و ضریب خوشگی بالا تولید می‌کند. این مدل توسط دانکن جی واتس و استیون استروگاتز در کار مشترکشان در مقالهٔ نیچر ۱۹۹۸ پیشنهاد شده بود.

انگیزه ساخت مدل

مدل اردوش-رنیی مدلی برای ساختن شبکه های تصادفی است که توسط پال اردوش و آلفرد رنیی برای ساخت شبکه های تصادفی ارائه شد. در این مدل تعداد مشخصی راس ابتدا در نظر گرفته می شوند و سپس به دو روش شبکه تصادفی ساخته می شود که در یکی، تعداد یال ها ثابت اند و به طور تصادفی بین راس ها پخش می شوند. در روش دیگر، احتمال متصل بودن هر دو راس مقدار ثابت p است و برای ساخت شبکه کافی است از هر راس مورد نظر به احتمال p به راس دیگری یال وصل شود و به احتمال یک منهای این احتمال یالی وصل نشود.

اما این مدل، با وجود داشتن ویژگی دنیای کوچک، دو ویژگی مشاهده شده در بسیاری از شبکه های واقعی را ندارد:

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

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

روش ساخت

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

جستارهای وابسته

• مدل اردوش-رنیی
• شبکه اجتماعی

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Watts and Strogatz model». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۱ مارس ۲۰۱۷.