گراف تصادفی کوچک جهان (Small-World Random Graph)، در ریاضیات (Mathematics)

انواع گراف های تصادفی (Random Graphs) را در آموزش زیر شرح دادیم :

گراف تصادفی کوچک جهان (Small-World Random Graph) :

این مدل که توسط واتس و استروگاتز در سال ۱۹۹۸ معرفی شد، برای توضیح دو ویژگی مهم در شبکه های اجتماعی طراحی شد: ضریب خوشگی بالا (High Clustering Coefficient) و میانگین فاصله کم (Low Average Distance). ساختار پایه این مدل یک گراف منظم حلقوی (مانند یک دایره) است که هر رأس به همسایگان نزدیک خود متصل است (ضریب خوشگی بالا). سپس با احتمال مشخصی، تعدادی از یال ها را برداشته و دوباره به رأس های دیگر به طور تصادفی وصل می کنیم (اتصال مجدد - Rewiring). این یال های تصادفی جدید که "اتصالات دوربرد" (Long-range Connections) نامیده می شوند، میانگین فاصله بین رأس ها را به شدت کاهش می دهند. نتیجه گرافی است که هم مانند جوامع واقعی خوشه بندی بالایی دارد و هم مانند مدل تصادفی، مسیرهای کوتاهی برای ارتباط بین هر دو گره وجود دارد.