مشخصات شبکه های مورد استفاده در آزمایش ها ۶۰
فهرست الگوریتم ها
الگوریتم SLPA 43
الگوریتم پیشنهادی برای تشخیص تشکل های همپوشان در شبکه های ایستا ۴۷

الگوریتم پیشنهادی برای تشخیص تشکل های همپوشان در شبکه های پویا ۴۹
فصل اول

فصل اول: مقدمه

مقدمه

در دنیای امروز، ما با سیستم های پیچیده ای^[۳] در پیرامون خود احاطه شده ایم، از جامعه که در آن میلیون ها عضو با یکدیگر در حال تعامل هستند تا شبکه های تلفن همراه و کامپیوتر که میلیون ها کاربر را به یکدیگر متصل می‌کنند. همچنین توانایی ما برای استنتاج و درک محیط اطراف، وابسته به شبکه ای از میلیاردها سلول عصبی^[۴] در مغز ماست. این سیستم های پیچیده نقش های بسیار مهمی در جنبه های مختلف زندگی ما ایفا می‌کنند. درک، توصیف، پیش بینی و کنترل این سیستم ها از جمله بزرگترین چالش های ما در جهان مدرن است.
معمولا در پشت هر کدام از این سیستم های پیچیده، شبکه ای عظیم قرار دارد که تعاملات بین اجزای این سیستم ها را مشخص می‌کند. به عنوان مثال: فعل و انفعالات شیمیایی درون بدن موجودات زنده، تعاملات میان سلول های عصبی مغز، روابط دوستی، خویشاوندی و اجتماعی، شبکه جهانی اینترنت، تراکنش های مالی، خطوط انتقال و توزیع نیرو، راه های ارتباطی زمینی، هوایی و دریایی، همگی بخشی از مواردی هستند که می‌توان آنها را به صورت یک شبکه توصیف کرد. همچنین می‌توان گفت که شبکه ها قلب بسیاری از فناوری های انقلابی عصر حاضر هستند. موتورهای جستجو^[۵]، شبکه های اجتماعی مجازی^[۶]، شبکه های کامپیوتری جهانی، شبکه جهانی مخابرات و تلفن همراه تنها تعدادی از این نمونه ها هستند.
با وجود تفاوت و تنوع بسیار زیادی که در ماهیت، اندازه، کاربرد، رفتار و ویژگی های مختلف این سیستم ها و شبکه ها، چه از نوع طبیعی و چه ساخته دست بشر وجود دارد، می‌توان اصول و قوانین مشخص و مشابهی را در میان آنها مشاهده کرد. برای مثال: شبکه واکنش های شیمیایی که اجزای آن را مولکول های بسیار کوچک تشکیل می‌دهند، شبکه جهانی وب^[۷] که در آن صفحات وب به وسیله پیوندهای وب^[۸] به یکدیگر متصل شده اند، شبکه های اجتماعی که از روابط میان افراد تشکیل شده اند و بسیاری موارد دیگر، همگی قابل توصیف با ساختارها و قوانین مشابهی هستند و این امر به عنوان یک مزیت بزرگ تلقی می‌شود. زیرا می‌توان تمام این سیستم های متفاوت طبیعی و مصنوعی را توسط ابزارهای ریاضی و مدل سازی مشابهی توصیف کرد.
با توجه به اینکه از سال ها پیش بسیاری از این سیستم ها، مانند: ساختارها و واکنش های زیستی، راه های ارتباطی، روابط اجتماعی و نظایر آن و همچنین دانش مطالعه بر روی سیستم ها و شبکه ها شناخته شده اند، پرسشی که ممکن است مطرح شود این است که چرا اهمیت این موضوع تنها در چند دهه اخیر آشکار شده است؟ پاسخی که می‌توان داد این است که در گذشته ابزارهای مناسبی برای جمع آوری، نگهداری و پردازش این اطلاعات وجود نداشت اما امروزه با توسعه چشمگیر فناوری هایی نظیر کامپیوتر و شبکه های ارتباطی دیجیتال، این امکان فراهم آمده است که گردآوری، ترکیب، اشتراک و تحلیل این اطلاعات با سهولت، سرعت و دقت بالا و هزینه کم قابل اجرا باشد.

دانش شبکه^[۹]

دانش شبکه شاخه ای از علوم بشری است که به مطالعه بر روی شبکه ها می‌پردازد و تلاش می‌کند با بهره گرفتن از نتایج بررسی های خود، از آنها برای درک بهتر سیستم های پیچیده بهره بگیرد. به طور کلی می‌توان چهار ویژگی را برای این دانش برشمرد که در ادامه به اختصار به آنها اشاره می‌شود (۱):
ماهیت میان رشته ای: با توجه به نحوه برخورد با مسئله در حوزه مطالعه شبکه ها، این دانش تنها به یک شاخه خاص از علم محدود نبوده و می‌تواند در علوم گوناگون از قبیل: علوم اجتماعی، زیستی، کامپیوتر، فیزیک، شیمی، اطلاعات، اقتصاد، امنیت و بسیاری از موارد دیگر کاربرد داشته باشد. به عنوان مثال، روشی که در حوزه علوم اجتماعی برای تشخیص افراد و گرو های موثر بر جامعه مورد استفاده قرار می‌گیرد، ممکن است در شبکه های کامپیوتری برای مدیریت ترافیک شبکه به کار برده شود.
عملگرایی و تمرکز بر داده ها: بر خلاف نظریه گراف ها که بیشتر به جنبه های انتزاعی و ریاضی مسائل توجه دارد، این دانش بیشتر بر حوزه کاربرد عملی و داده های مسئله تمرکز می‌کند. به همین جهت ابزارها و روش هایی که در این زمینه ارائه می‌شوند، بر روی داده ها و مسائل واقعی آزمایش می‌شوند تا قابلیت و کارایی آنها مشخص شود.
بیان کمی و ریاضی: مطالعه شبکه ها برای توصیف و مطالعه بهتر و دقیق تر، از ابزارها و روش های ریاضی بهره می‌برد. به عنوان مثال: نظریه گراف ها، آمار و احتمالات، داده کاوی^[۱۰]، تئوری اطلاعات^[۱۱]، کنترل و فیزیک آماری از جمله علومی هستند که در این حوزه کاربرد دارند.
پردازش و محاسبات: از آنجا که اغلب مسائل مطرح شده در این حوزه، حجم عظیمی از اطلاعات را در بر می‌گیرند، بخش مهمی از کار به طراحی و بکارگیری روش هایی معطوف می‌شود که بتوانند از عهده محاسبات سنگین مورد نیاز برآیند. به همین منظور طراحی الگوریتم ها، پایگاه داده ها و داده کاوی بخشی از ابزارهای نرم افزاری هستند که بسیار به کار برده می‌شوند.

کاربردهای دانش شبکه

کارایی و تاثیر هر شاخه از علم، علاوه بر دستاوردهای نظری، در حوزه کاربردهای عملی نیز مورد بررسی قرار می‌گیرد. در این بخش به اختصار به چند مورد از کاربردهای دانش شبکه ها اشاره می‌کنیم.

تصویر ۱: نمونه ای از شبکه راه های ارتباطی
( منبع: http://upload.wikimedia.org/wikipedia/commons/e/e1/Late Medieval Trade Routes.jpg )

کاربردهای اقتصادی

موارد زیادی از شرکت های بسیار موفق عصر حاضر، به ارائه خدمات و فناوری هایی می‌پردازنده که بر پایه شبکه ها استوار هستند. برای نمونه می‌توان به شرکت های Google^[12]، ^[۱۳]Facebook، Cisco^[14] و ^[۱۵]Apple اشاره کرد. شرکت Google فعالیت های عظیمی در حوزه استخراج نقشه شبکه جهانی وب انجام می‌دهد و بسیاری از خدمات و محصولات آن بر پایه این شبکه هستند. همچنین Facebook به عنوان بزرگترین شبکه اجتماعی مجازی جهان در کنار شرکت های دیگری نظیر Twitter^[16] سالانه درآمدهای فراوانی از فعالیت های تبلیغاتی به دست می‌آورند.

تصویر ۲: شبکه کاربران شبکه اجتماعی فیسبوک
( منبع: http://www.social-dynamics.org/gephi-facebook/4/ )

کاربردهای بهداشتی

پروژه مطالعه ژنوم انسان^[۱۷] در سال ۲۰۰۱ تکمیل شد و توانست فهرستی از تمام ژن های انسان را ارائه دهد (۱). اما همچنان کار بر روی نقشه دقیقی که بتواند تعامل میان ژن ها و سایر ساختارهای سلولی را نشان دهد ادامه دارد. از تجزیه غذا در سلول ها تا احساس تغییرات محیطی بر اساس این شبکه مولکولی انجام می‌شود. هر گونه اختلال در این شبکه می‌تواند موجب بیماری های انسان شود. به همین منظور، پژوهش های شاخه ای از زیست شناسی، تحت عنوان زیست شبکه ای^[۱۸] به این موضوع اختصاص دارد. همچنین در همین راستا، پژوهش های دیگری نیز در علم داروسازی تحت عنوان داروسازی شبکه ای^[۱۹] در حال انجام است. هدف اصلی که در این حوزه دنبال می‌شود، تولید داروهایی است که علاوه بر درمان بیماری ها، اثرات جانبی کمی داشته باشند. امروزه، در پیشرفت های داروسازی جدید، شبکه ها نقش مهمی را ایفا می‌کنند و سرمایه گذاری های بزرگی در این حوزه انجام می‌شود.

کاربردهای امنیتی

تروریستم^[۲۰] یکی از مسائل مهم امنیتی قرن حاضر است که جامعه جهانی را درگیر خود کرده است. تفکر شبکه ای و مطالعه آن برای اخلال در فعالیت های مالی سازمان های تروریستی و شناسایی افراد و امکانات آنها به طور روز افزون از سوی نهادهای امنیتی مورد استفاده قرار می‌گیرد. با وجود اینکه اغلب مطالعات و فعالیت ها در این حوزه، طبقه بندی شده هستند اما گاهی مواردی از موفقیت های این روش ها منتشر می‌شوند. به عنوان مثال دستگیری صدام حسین و عوامل بمب گذاری قطار مادرید در سال ۲۰۰۴ در نتیجه همین مطالعات حاصل گردید. همچنین در میدان های نبرد نوین نیز، دانش شبکه کاربردهای وسیعی پیدا کرده است و هزینه های فراوانی صرف این موضوع می‌شود (۲).

تصویر ۳: بخشی از شبکه روابط صدام حسین و اطرافیانش که توسط نیروهای امنیتی تهیه شده است.

کاربردها در حوادث همگانی^[۲۱]

استفاده از ابزار شبکه در پیش بینی دقیق نحوه شیوع ویروس H1N1 در سال ۲۰۰۹ نمونه ای از موفقیت های این علم در پیشگیری و کنترل بیماری های واگیردار است (۳). علاوه بر این، در دنیای مجازی نیز از همین ابزار برای کنترل انتشار ویروس ها از جمله در شبکه های تلفن همراه و کامپیوتر استفاده می‌شود (۴).

تصویر ۴: شبکه پیش بینی نحوه شیوع ویروس H1N1 در سال ۲۰۰۹

کاربردها در پژوهش بر روی مغز

مغز انسان از هزاران میلیارد سلول عصبی تشکیل شده است و یکی از پیچیده ترین شبکه هایی است که در حوزه شبکه ها مورد بررسی قرار گرفته است. دلیل اصلی این موضوع پیچیدگی ارتباط این سلول ها است که کار تشخیص شبکه را دشوار می‌سازد. تنها نمونه ای که کاملا تشخیص داده شده است، متعلق به ساختار عصبی نوعی کرم است که تنها شامل ۳۰۰ سلول عصبی است. کاربردهای فراوانی برای نتایج حاصل از این پژوهش ها وجود دارند که از جمله آن می‌توان به فناوری های نوین برای تعامل میان انسان و ماشین^[۲۲]، درمان بیماری های عصبی و استخراج اطلاعات حافظه انسان اشاره کرد.

کاربردهای مدیریتی

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

تصویر ۵: نمونه ای از شبکه روابط بین کارکنان یک سازمان. بخش های پررنگ نمایانگر کارکنان تاثیرگذار در سازمان هستند.

کاربردهای پژوهشی

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

کاربردهای دیگر

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

تصویر ۶: شبکه مواد غذایی مکمل
( منبع: http://www.ladamic.com/img/IngredientComplements.jpg )

تاریخچه

تعداد علومی که بتوان به وضوح زمانی را برای شروع آنها تعیین کرد زیاد نیست. نظریه گراف که یکی از بنیان های ریاضی دانش شبکه ها است در سال ۱۷۳۶ میلادی توسط اویلر^[۲۳]، ریاضی دان سوئیسی در پی حل معمای پل های کونیگزبرگ^[۲۴] مطرح کرد. این پل های هفت گانه (همانطور که در شکل زیر مشاهده می‌شود،) یک جزیره و سه ساحل مجاور آن را به یکدیگر مرتبط می‌ساختند. معما از این قرار بود که آیا کسی می‌تواند بدون عبور مجدد از یک پل، از تمام پل ها عبور کند؟ این معما که تا دو سال بدون پاسخ باقی مانده بود، سرانجام توسط اویلر با مدل سازی مسئله به صورت یک گراف، حل شد (۶).

تصویر ۷: معمای پل های کونیگزبرگ و گراف نشان دهنده آن
در سال ۱۸۴۷، گوستاو کیرشهف نوع خاصی از گراف‌ها به نام درخت را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم قوانین اهم برای جریان الکتریکی در کاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد، آرتور کیلی همین نوع گراف را برای شمارش ایزومرهای متمایز هیدروکربنهای اشباع شده ی مولکول C_nH_2n+2 به‌کار برد.