شبکه‌های جهان کوچک
این مطلب درخواستی یکی از دوستان است! :) برای اینکه مطلب مفهوم‌تر باشد سعی کردم از یک منبع کمک بگیرم!
مرجع: http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch20.pdf
۱- درجه جدایی ۶:
یعنی در گراف آن با طی کردن ۶ یال از هر رأسی می‌توانیم به هر رأس دیگری برسیم.
داستان آن از اینجا شروع شده است که یک نفر یک سری نامه برای چند نفر فرستاده و خواسته که آنها برای یک آدم خاص بفرستند یا به کسی بفرستند که آن فرد را می‌شناسد. و به طور میانگین (expected) با ۶ گام نامه‌ها به مقصد رسیده‌اند.
۲- ساختار و تصادفی بودن:
گفتیم به صورت متوسط این اتفاق می‌افتد. این کار را با محاسبه امیدریاضی انجام می‌دهند. می‌شود ساختارهایی ساخت که این خاصیت را دارند، اما سوال اصلی این است که گرافی مثل شبکه‌ی اجتماعی چرا این خاصیت را دارد؟ چون مثلاً در گرافهایی که مطمئنیم این خاصیت برقرار است مثلاً در مثال زیر فرض می‌کنیم هر نفر ۳ دوست دارند که آنها هم ۳ دوست جدید دارند و ...، در حالی که در عمل این طور نیست و اکثراً بین دوست‌های افراد اشتراک هست.
برای اینکه مشکل تعداد دوست‌های جدید را حل کنیم، فرض می‌کنیم هر کسی تعداد دوست جدید کمی دارد ولی به جای آن دوست با فاصله‌ی زیاد از همسایه‌هایش به آن می‌دهیم. مثال زیر را در نظر بگیرید که در آن یک توری داریم و یک سری یال تصادفی به آن اضافه کرده‌ایم.
مدل Watts-Strogatz:
کافی است فقط تعدادی از افراد در شبکه تصادفی، لینک (یال) به یک فرد دور داشته باشند.
جستجوی غیرمتمرکز:
حالا سوال این است که از یک مبدأ به یک مقصد بدون دانستن لینک‌های تصادفی چطور باید یک بسته را بفرستیم؟
هر کسی به صورت محلی این طور عمل می‌کند که بسته را به نزدیک‌ترین همسایه‌اش به هدف می‌فرستد.
این کار در حالت عادی زمان زیادی می‌گیرد ولی اگر طول لینک‌های تصادفی از حدی بیشتر باشد این زمان کم می‌شود.
از اینجا به بعد وارد محاسبات شده است اگر خواستید خودتان بخوانید. من هم فقط سر یک talk رفتم در مورد این و چیز بیشتری نمی‌دانم و اگر بخواهم توضیح بدهم باید خودم اول بخوانم.
