شبکه - قسمت اول

واضح آرشیو وب فارسی:فان پاتوق: شبکه - قسمت اول

در سال.های اخیر، تمرکز پژوهش.گران بر روی توصیف ریاضیاتیِ شبکه.های مختلف است.

با چه احتمالی دو نفر که شما آنها را می.شناسید ممکن است همدیگر را بشناسند؟ مردم دنیا به.طور متوسط با چند نفر در ارتباط مستقیم و با چند نفر در ارتباط غیرمستقیم هستند؟ کوتاه.ترین فاصله.ی ارتباطی میان شما و فردی که هرگز ندیده.اید و نمی.شناسید، چند نفر است؟ و یا پرسش.هایی از این دست که:

برای رسیدن از یک نقطه.ی شهر به نقطه.ی دیگر، کوتاه.ترین مسیر کدام است؟ چطور می.توان ارتباط رشته.های بسیار زیاد و پیچیده.ی عصبی موجود در بدن را، بررسی کرد؟ آیا تاکنون چنین پرسش.هایی برایتان پیش آمده؟ جستجوی پاسخ برای این قبیل پرسش.ها، شاخه.ی جدیدی از علم را پیش روی دانشمندان و پژوهش.گران قرار داده که پایه و اساس آن در نظریه.ی گراف.ها نهفته است. این شاخه که امروزه به.سرعت در حال گسترش است و هر روز کاربردهای بیشتری پیدا می.کند «علم شبکه.ها» یا «Networks science» نام دارد.

شبکه و علم شبکه.ها

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

ساختار شبکه

رئوس (مجموعه.ی یک بعدی از نقاط)
یال.ها (مجموعه.ی دوبعدی از خطوط)
ماتریس همسایگی (ماتریس گراف متناظر با شبکه)
اندازه (تعداد رئوس شبکه)

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

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

تاریخچه

مطالعه.ی شبکه.ها برای تحلیل و بررسی داده.هایی که ارتباطات پیچیده.ای با هم داشتند، پدیدار شد. اولین مقاله.ای که در این زمینه به چاپ رسید، «پل.های هفت.گانه.ی کونیگزبرگ» یا «Seven Bridges of Konigsberg» نام دارد که توسط «لئونارد اویلر» (Leonhard Euler)، در سال 1736 میلادی نوشته شد. توصیف اویلر از راس.ها و یال.ها پایه.ی نظریه.ی گراف است.

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

شیوه.ی حل این مساله، راهنمای بسیاری از مدل.سازی.ها و روش.های تحلیلی بود، اما هنوز کاربردهای وسیع آن به.خوبی شناخته نشده بود.
در سال 1930 «ژاکوب مورنو» (Jacob Moreno) که یک روانشناس بود، نظریه.ی گراف.ها را بر روی یک سیستم اجتماعی به.کار برد و آغازگر تحلیل شبکه.های اجتماعی شد. در این زمان، علم شبکه.ها وارد مرحله.ای شد که اهمیت و میزان کاربرد آن در زمینه.های مختلف به.خوبی برای همه آشکار شد. گام بعدی، ورود نظریه.ی احتمالات به نظریه.ی گراف.ها بود. «پاول اردوش» (Paul Erdos) این گام را برداشت.

در سال.های اخیر، تمرکز پژوهش.گران بر روی توصیف ریاضیاتیِ شبکه.های مختلف است. در این زمان مطالعات بر روی شبکه از حالت ساده و بدیهی گذشته خارج شده بود و شبکه.های مورد بررسی اصطلاحا «شبکه.های پیچیده» (complex networks) نامیده شدند. از ویژگی.های این شبکه.ها اینست که نه کاملا تصادفی هستند و نه کاملا منظم. تلاش برای شبیه.سازی این شبکه.ها منجر به معرفی مدل.هایی مانند «شبکه.ی دنیای کوچک» (small-world networks) توسط «دانکن واتز» (Duncan Watts) و شبکه.ی بی.مقیاس یا (scale-free network) توسط «آلبرت لازلو باراباشی» (Albert-Laszlo Barabasi) شد.

شبکه دنیای کوچک: مدلی از شبکه است که شبکه.های واقعی زیادی را در بر می.گیرد. ایده.ی اولیه.ی این مدل زمانی به.وجود آمد که عده.ای به.دنبال ساختن شبکه.هایی بودند که از قطع کردن بعضی از اتصالات و ایجاد اتصالات جدید در شبکه.های منظم به.وجود آید. از ویژگی.های چنین شبکه.هایی این است که بیشتر راس.ها به هم متصل نیستند ولی تنها با چند گام می.توان به بیشتر راس.ها رسید.

شبکه بی.مقیاس: در این شبکه.ها، توزیع درجات راس.ها، توانی است. یعنی از رابطه.ی P(k)~k-γ پیروی می.کنند. به.همین دلیل در این شبکه.ها، بیشتر راس.ها دارای درجات کمی هستند و تعداد کمی راس وجود دارد که درجاتشان زیاد است.

این صفحه را در گوگل محبوب کنید

[ارسال شده از: فان پاتوق]

[مشاهده در: www.funpatogh.com]

[تعداد بازديد از اين مطلب: 383]