ژانویه 22, 2021

شناسایی تشکل‌های همپوشان در شبکه‌های پویا- قسمت ۲

 
تصویر ۴: شبکه پیش بینی نحوه شیوع ویروس H1N1 در سال ۲۰۰۹
کاربردها در پژوهش بر روی مغز
مغز انسان از هزاران میلیارد سلول عصبی تشکیل شده است و یکی از پیچیده ترین شبکه هایی است که در حوزه شبکه ها مورد بررسی قرار گرفته است. دلیل اصلی این موضوع پیچیدگی ارتباط این سلول ها است که کار تشخیص شبکه را دشوار می‌سازد. تنها نمونه ای که کاملا تشخیص داده شده است، متعلق به ساختار عصبی نوعی کرم است که تنها شامل ۳۰۰ سلول عصبی است. کاربردهای فراوانی برای نتایج حاصل از این پژوهش ها وجود دارند که از جمله آن می‌توان به فناوری های نوین برای تعامل میان انسان و ماشین[۲۲]، درمان بیماری های عصبی و استخراج اطلاعات حافظه انسان اشاره کرد.
کاربردهای مدیریتی
علاوه بر ساختارهای رسمی و سلسله مراتبی تعیین شده در سازمان ها و شرکت ها، ساختارهای پنهان دیگری نیز خارج از این محدوده وجود دارند. به عنوان مثال ممکن است برای تولید یک محصول، همکاری هایی خارج از ساختار رسمی صورت پذیرد. همچنین برای افزایش بازدهی عملکرد، استفاده از روش های سنتی چندان جوابگو نیستند. برای نمونه، اعضای یک گروه کاری در روش های نوین بر اساس معیارهای مختلفی از جمله میزان ارتباط آنها با یکدیگر انتخاب می‌شوند که این اطلاعات از روی ساختارهای شبکه ای تهیه شده از کارکنان به دست می‌آید. همچنین ارزیابی میزان کارایی هر کدام از بخش ها و اعضای یک سازمان از این طریق با دقت و سرعت بهتری قابل انجام خواهد بود (۵).
 
تصویر ۵: نمونه ای از شبکه روابط بین کارکنان یک سازمان. بخش های پررنگ نمایانگر کارکنان تاثیرگذار در سازمان هستند.
کاربردهای پژوهشی
با رشد سریع پژوهش ها و دستاوردهای علمی در حوزه های مختلف، دسترسی، طبقه بندی و مطالعه این تحقیقات با توجه به حجم عظیم اطلاعات موجود کاری بسیار دشوار و پیچیده خواهد بود، اما امروزه به کمک ابزارهای طراحی شده، پژوهش های انجام شده در مجامع علمی مختلف، مانند یک شبکه بزرگ به یکدیگر متصل شده اند. مقالات، مجلات، کتاب ها و منابع تحقیقاتی به آسانی و با هزینه کم، در اسرع وقت در اختیار پژوهشگران قرار می‌گیرند. همچنین امکان مقایسه، استناد و دریافت آخرین روش ها و فعالیت های انجام شده توسط سایر محققین در سراسر دنیا فراهم شده است.
کاربردهای دیگر
مواردی که در اینجا به آنها اشاره شد تنها گوشه ای از کاربردهای فراوان مطالعه شبکه ها می‌باشد. همچنین با پیشرفت های بیشتر انسان در زمینه های مختلف، همواره بر تعداد این کاربردها افزوده می‌شود و مسائل جدیدی برای مطالعه و بررسی مطرح می‌شوند.
تصویر ۶: شبکه مواد غذایی مکمل
( منبع: http://www.ladamic.com/img/IngredientComplements.jpg )
تاریخچه
تعداد علومی که بتوان به وضوح زمانی را برای شروع آنها تعیین کرد زیاد نیست. نظریه گراف که یکی از بنیان های ریاضی دانش شبکه ها است در سال ۱۷۳۶ میلادی توسط اویلر[۲۳]، ریاضی دان سوئیسی در پی حل معمای پل های کونیگزبرگ[۲۴] مطرح کرد. این پل های هفت گانه (همانطور که در شکل زیر مشاهده می‌شود،) یک جزیره و سه ساحل مجاور آن را به یکدیگر مرتبط می‌ساختند. معما از این قرار بود که آیا کسی می‌تواند بدون عبور مجدد از یک پل، از تمام پل ها عبور کند؟ این معما که تا دو سال بدون پاسخ باقی مانده بود، سرانجام توسط اویلر با مدل سازی مسئله به صورت یک گراف، حل شد (۶).
 
تصویر ۷: معمای پل های کونیگزبرگ و گراف نشان دهنده آن
در سال ۱۸۴۷، گوستاو کیرشهف نوع خاصی از گراف‌ها به نام درخت را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم قوانین اهم برای جریان الکتریکی در کاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد، آرتور کیلی همین نوع گراف را برای شمارش ایزومرهای متمایز هیدروکربنهای اشباع شده ی مولکول CnH2n+2 به‌کار برد.
در همین دوران شاهد ظهور دو ایده ی مهم دیگر در صحنه هستیم. ایده ی اول حدس چهار رنگ بود که نخستین بار توسط فرانسیس گوثری در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط کنث ایپل و ولفگانگ هیکن و با استفاده از یک تحلیل رایانه‌ای پیچیده حل شد. ایده ی مهم دوم، دور همیلتونی بود. این دور به افتخار سر ویلیام روآن همیلتون نامگذاری شده است. او این ایده را در سال ۱۸۵۹ برای حل معمای جالبی حاوی یال‌های یک دوازده وجهی منتظم به‌کار گرفت. یافتن جوابی برای این معما چندان دشوار نیست ، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که گراف‌های بدون جهت حاوی مسیر یا دورهای همیلتونی را مشخص کنند.
پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئله ی مشخص کردن گراف‌های مسطح را کازیمیر کوراتوفسکی، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین کتاب درباره ی نظریه ی گراف در سال ۱۹۳۶ منتشر شد. این کتاب را ریاضیدان مجارستانی، دنش کونیگ، که خود محقق برجسته‌ای در این زمینه بود، نوشت. از آن پس فعالیت‌های بسیاری در این زمینه صورت گرفته و کامپیوتر نیز در چهار دهه ی اخیر به یاری این فعالیت‌ها آمده است (۷).
مفاهیم اولیه
سیستم های پیچیده نگاهی نو به پدیده هایی است که به علت ارتباط بین اجزای آن و همچنین ارتباط با دیگر پدیده ها، از پیچیدگی بالایی برخوردارند و رفتار جمعی متفاوتی بروز می‌دهند. بدین معنی که با مطالعه تک تک اجزای یک سیستم پیچیده نمی‌توان به رفتار جمعی آن دست یافت.
اگر بخواهیم یک سیستم پیچیده را بهتر درک و توصیف کنیم، نیاز داریم که آن را به صورت یک شبکه نمایش دهیم. به بیان ساده، یک شبکه یا گراف شامل اجزایی به نام گره[۲۵] یا رأس[۲۶] است که ارتباط مستقیم میان آنها توسط پیوندها[۲۷] و یا یال ها[۲۸] مشخص می‌شود. این نوع نمایش زبان مشترکی را برای توصیف پدیده های مختلف ارائه می‌دهد (۸).
 
تصویر ۸: (a) شبکه کامپیوتری، (a) شبکه اجتماعی بازیگران، (c) شبکه مولکولی و (d) توصیف یکسان هر سه شبکه از دیدگاه تحلیل شبکه
در ادامه به چند تعریف و مفهوم پایه در زمینه شبکه ها و گراف ها می‌پردازیم (۸):
تعداد گره ها (یا رأس ها): به مجموع تعداد اجزای یک گراف گفته می‌شود و معمولا با حرف N یا V نمایش داده شده و آن را اندازه شبکه یا گراف نیز می‌نامند.
تعداد پیوند ها (یا یال ها): به مجموع ارتباطات بین اجزای یک گراف (گره ها) گفته شده و معمولا با حرف L یا E نمایش داده می‌شود.
گراف جهت دار[۲۹]: به گرافی که یال های آن جهت داشته باشند جهت دار و در غیر این صورت بدون جهت[۳۰] می‌گویند. به عنوان مثال، گراف جاده های شهری جهت دار است، زیرا در آن جهت تردد وسایل نقلیه نیز در نظر گرفته می‌شود.
گراف وزن دار[۳۱]: به گرافی که یال های آن دارای وزن باشند وزن دار و در غیر این صورت بدون وزن[۳۲] می‌گویند. به عنوان مثال، گراف نشان دهنده ارتباط بین کلمات وزن دار است و در آن کلماتی که از نظر مفهومی شباهت بیشتری به یکدیگر دارند با وزن بیشتری به یکدیگر متصل شده اند.
درجه گره[۳۳]: به تعداد پیوندهایی که یک گره با سایر گره ها دارد درجه آن گره گفته شده و معمولا با حرف K نمایش داده می‌شود.
میانگین درجه[۳۴]: به میانگین تمام درجات گره های یک گراف، میانگین درجه آن گفته می‌شود.
توزیع درجه[۳۵]: به توزیع احتمالی که بتوان به وسیله آن پراکندگی درجه گره های یک گراف را توصیف کرد، توزیع درجه آن می‌گویند. به بیان دیگر، اگر گره ای به صورت تصادفی از گراف انتخاب شود، این نمودار بتواند نشان دهد که این گره با چه احتمالی درجه خاصی (مثلا درجه ۲) را خواهد داشت.
 
تصویر ۹: دو نمونه گراف و نمودار توزیع درجه آنها
گراف کامل[۳۶]: به گرافی که در آن هر گره به تمام گره های دیگر متصل باشد گراف کامل می‌گویند.
 
تصویر ۱۰: یک گراف کامل

برای دانلود متن کامل پایان نامه به سایت  fotka.ir  مراجعه نمایید.