دسامبر 12 2004

Paparophobia

دسته: شخصیadmin @ 3:19 ق.ظ

چند وقتي است كاغذ نو كه مي بينم، به شدت مي ترسم که تيزي لبه اش چشمانم را ببرد.


دسامبر 10 2004

مدل سازی شبکه های پیچیده

دسته: تألیفadmin @ 12:15 ب.ظ

• عنوان: مدل سازی شبکه های پیچیده
• زبان:
فارسي
• نویسنده:
نيما دارابي
• تاریخ نگارش: پاییز 83

چکيده: گراف ها در مطالعات كلاسيك معمولا كوچك و منظم هستند. در مطالعات جديد تكيه بر پردازش رايانه ها راه براي مطالعه ي گراف هاي بزرگ و نامنظم – كه مدل هاي بهتري براي شبكه هاي واقعي هستند – باز نموده است. بسياري از مباحث نظريه ي گراف، امروزه آماري تر و الگوريتميك تر از گذشته شده است. اين نوشتار چكيده اي است از منابع مختلف در زمينه ي مدل ها و‌ روش هاي الگوريتم هاي مطالعه و تحليل شبكه هاي پيچيده از طريق پياده سازي آنها بر روي گراف هاي بزرگ. به اين ترتيب نخست سه مدل مهم از گراف ها كه براي مدل سازي شبكه هاي پيچيده پيشنهاد شده اند را معرفي مي كنيم و سپس به بررسي ميزان انطباق آنها با مدل هاي واقعي مي پردازيم. مهم ترين منبع اين مقاله است، به موارد ديگر نيز در طول نوشتار استناد شده است.

شبکه های پیچیده (Complex Networks) چیستند؟
هر جا كه در جهان واقعي اشياء زيادي با ارتباطاتي به يكديگر پيوند خورده اند، يك شبكه ي پيچيده وجود دارد. شبكه ها را مي توانيم با گراف هاي بزرگ مدل كنيم. شبكه ها همه جا هستند:
– يك سلول،‌ شبكه ي پيچيده اي از مواد شيميايي متصل شده با واكنش هاي شيميايي است.
– اينترنت، شبكه ي پيچيده اي از كامپيوترها و روترها متصل شده با كابل ها يا ارتباطات بي سيم است.
– شبكه هاي اجتماعي، شبكه هاي پيچيده اي هستند كه در آن ها گره ها انسان و يال ها روابط اجتماعي بين آن ها است.
– وب، شبكه اي پيچيده از صفحات است كه توسط پيوندها به يكديگر متصل شده اند.

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

نمودار توزیع درجه: نموداری است که تعداد رؤوسی را که درجه ی خاصی دارند نشان می دهد. بنابراین محور افقی آن درجه ی رؤوس و محور عمودی آن هم بیانگر تعداد رؤوسی از آن درجه می باشد.

ضریب کلاسترینگ: ضريب كلاسترينگ يك رأس از گراف نسبت يالفعل به بالقوه ي يال هاي بين همسايه گان اش يا احتمال متصل بودن دو رأس همسايه ي آن رأس است.  ضریب کلاسترینگ کل یک گراف میانگین حسابی ضرایب کلاسترینگ تک تک رؤوس آن است.

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

چه مدل هایی برای تحلیل شبکه های پیچیده به کار می روند؟
برای تحلیل شبکه های پیچیده سه مدل اساسی معرفی شده اند که به اختصار ذکر می شود:

1. مدل گراف تصادفی (Random Graph): تعدادی نقطه روی صفحه قراردهید و تعدادی راس بین آنها به طور دلخواه ترسیم کنید. بدین ترتیب گرافی تصادفی خواهید داشت. اگر این تعداد یال توزیع شده را به کل n(n-1)/2 یالی که می تواند روی n رأس بنا شود بخش کنیم، احتمال اتصال دو رأس دلخواه در یک گراف تصادفی به دست می آید. گراف تصادفی با دو پارامتر تعداد رأس و احتمال اتصال معرفی می شود.  اگر گره اي از يك گراف تصادفي و دو تا از همسايه هاي آن را در نظر بگيريم، احتمال متصل بودن آن دو همسايه، برابر با احتمال متصل بودن هر دو رأس دلخواه از گراف است، پس ضریب کلاسترینگ یک گراف تصادفی همان احتمال اتصال آن است.
در مقايسه ي گراف تصادفي با شبكه هاي واقعي می توان به این نقطه ی قوت اشاره کرد که ميانگين فواصل در گراف تصادفي مانند این مقدار در شبكه هاي واقعي کم است، در حالی که ضريب كلاسترينگ در گراف تصادفي خيلي كمتر از اين ضريب براي شبكه هاي واقعي است. همچنین نمودار توزيع درجه در گراف تصادفي به صورت نرمال است، ‌در حالي كه در مدل هاي واقعي چنين نيست.
سرچشمه ي اين نظريه به سال هاي 1959 تا 1961 و كارهاي رياضيدان مشهور Erdös و  همكار او Renyi باز مي گردد. يكي از يافته هاي مهم اين دو دانشمند کشف تابع احتمال بحراني بود. این دو دریافتند كه بسياري از ويژگي هاي مهم در گراف تصادفي با افزايش احتمال اتصال p به طور ناگهاني ظاهر مي شوند. برای یک گراف بزرگ (با تعداد رؤوس زیاد) و یک توزیع احتمال مشخص، اگر بار ها و بارها یال ها را به صورت تصادفی توزیع کنیم، یا همه ی گراف هاي حاصل یک ويژگي مشخص (مثلا همبند بودن یا داشتن مثلث)را دارند و يا هيچ يك ندارند. چنین وِیژگی هایی با افزایش احتمال اتصال و رسیدن آن به یک آستانه ی مشخص (تابع احتمال بحرانی که تابعی از تعداد رؤوس است) ناگهان پدید می آید. مشابه این پدیده را می توان در بارش باران روی زمین مشاهده کرد. زمین بزرگی را در نظر بگیرید که روی آن باران پراکنده ای (با نرخ یکنواخت) می بارد. سطح این زمین مملو از لکه های خیس جدا از هم خواهد بود. با افزایش باران این لکه ها ممکن است به صورت موضعی به هم بپیوندند اما در کل به یکدیگر متصل نمی شوند. اگر شدت بارش به حدی مشخص برسد، به طور ناگهانی همه ی لکه ها به هم می پیوندند و یک دریاچه ی سراسری پدید می آورند.

2. مدل جهان کوچک (Small World): چنانكه گفتيم ضريب كلاسترينگ و ميانگين طول مسير در يك گراف تصادفي نسبتا كم است. با توجه به اینکه در شبكه هاي واقعي ضريب كلاسترينگ خيلي بيشتر از مدل گراف تصادفي است و حتا اين ضريب بسياري از اوقات از سايز شبكه مستقل است، در سال 1998 دو دانشمند به نام های Watts و Strogatz مدلی ارائه کردند که علاوه بر آنکه مانند گراف تصادفی میانگین طول مسیر كمي دارد، ضریب کلاسترینگ بزرگی داشته باشد. ضریب کلاسترینگ بزرگ به این معنا است که اگر درجه ي متوسط رؤوس ثابت باشد، این ضريب مانند گراف تصادفي با رشد شبكه (افزايش n) كاهش پيدا نكند.
مدل جهان کوچک مدلی تك پارامتري است که از در هم ریختن تصادفی یک گراف منظم پدید می آید. یک شبکه ی منظم را در نظر بگیرید. مثلا شبکه ی یک توری که در آن هر رأس به رأس های مجاور متصل است. این شبکه میانگین طول مسیر زیاد و ضریب کلاسترینگ زیاد دارد. اگر یال های این شبکه را یک به یک برداریم و دوباره به صورت تصادفی بین دو رأس دلخواه قرار دهیم، پس از برداشتن و دوباره گذاشتن همه ی یال ها، گرافی تصادفی خواهیم داشت که میانگین طول مسیر کم و ضریب کلاسترینگ کم دارد. یعنی با بازآرایی تصادفی یک گراف منظم هر دوی این کمیت ها کم می شوند. چیزی که این دو دانشمند دریافتند این بود که نرخ این دو کاهش یکسان نیست. دوباره چینی درصد کمی از یال ها در همان ابتدای کار پل هایی را بین رأس ها برقرار می کند که موجب می شود میانگین طول مسیر به شدت کاهش یابد، در حالی که برای کاهش  ضریب کلاسترینگ باید کل شبکه را مختل کرد و تقریبا همه ی یال ها را دستکاری کرد. چنین گراف بینابینی که هنوز ضریب کلاسترینگ زیاد دارد ولی میانگین طول مسیر آن کم شده است،شبکه ی جهان کوچک نام دارد و از این هر دو حیث به شبکه های واقعی بیشتر می ماند. اما هنوز یک مشکل وجود دارد. روشی که ما اختیار کرده ایم، هنوز توزیع نرمالی دارد در حالی که توزیع درجه ی رؤوس در شبکه های واقعی چنین نیست. مدلی که در ادامه ارائه خواهد شد برای پوشش دادن این جنبه از شبکه های واقعی معرفی شده است:

3. مدل گراف هاي مستقل از مقياس (Scale-Free Graphs): براي فهم بهتر شبكه هاي مستقل از مقياس، بايد نخست دريابيم كه در اينجا به جاي مدل كردن توپولوژي شبكه ها، رشد آنها را مدل مي كنيم. همزمان با دو دانشمند پیشین در سال 1998 دو دانشمند به نام های Barabasi و Albert مدلی به نام شبكه هاي مستقل از مقياس ارائه کردند. بر اساس نظریه ی آنان شبکه هایی را مستقل از مقیاس می دانیم که اين دو ساز و كار در مورد آنها برقرار باشد:
– رشد (Growth): شبكه هاي مستقل از مقياس هميشه در حال افزودن رأس ها و يال هاي جديداند.
– پيوست ترجيحي (Preferential Attachment): رأس هاي جديد معمولا به رأس هاي قديمي اي متصل مي شوند كه درجه ي بيشتري دارند. به عبارت ديگر در شبكه هاي مستقل از مقياس قوي ها قوي تر مي شوند.
نشان داده شده كه شبكه هايي كه دو ويژگي فوق را دارند (مانند شبكه هاي واقعي) از توزيع درجه ي تواني پيروي مي كنند،‌ يعني احتمال آنكه رأسي داراي درجه ي k باشد، متناسب است با توان منفي ثابتي از k:

نمودار توزيع درجه در شبكه هاي مستقل از مقياس (Scale-Free) تواني است.

نمودار فوق نشان مي دهد كه درشبكه هاي مستقل از مقياس، تعداد گره هايي كه درجه ي كمي دارند،‌ فراوان و تعداد آنها كه درجه ي بسياري دارند، اندك است. اين گروه اخير را Hub مي ناميم. Hub ها در شبكه هاي واقعي وجود دارند، اما دو مدل پيشين قادر به توضيح آنها نيستند. Hub هاي زير را به عنوان نمونه در نظر بگيريد. مي توان ردپاي دو ساز و كار Barabasi را در شكل گيري آنها جست و جو كرد:
– در گراف وب (كه در آن گره ها صفحات وب و يال ها ابرلينك ها هستند)، سايت هاي كم شمار و بسيار پرطرفدار مانند Yahoo و Google نمونه هايي از Hub ها هستند.
– گراف همكاري رياضي دانان را در نظر بگيريد. در اين گراف رياضي دانان گره هايي هستند كه اگر با هم مقاله ي مشتركي منتشر كرده باشند، با يك يال به هم پيوند مي خورند. در اينجا Paul Erdös (همان مبتكر نظريه ي گراف تصادفي) يك Hub است. وي تنها رياضي داني بود كه تعداد مقالات چاپ شده اش از 1400 عنوان تجاوز كرد. هنوز كسي به اين رقم افسانه اي نزديك نشده است. (به افتخار او براي عددي موسوم به Erdös Number تعريف شده كه معرف طول كوتاه ترين مسير در گراف يادشده از هر رياضي دان تا Erdös است). براي بررسي ويژگي هاي اين عدد و گراف همكاري رياضي دانان، پروژه اي نيز راه اندازي شده است.

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

آسيب پذيري در گراف مستقل از مقياس به چه صورت است؟
يكي از تفاوت هاي بنیادین گراف مستقل از مقياس با گراف هاي تصادفي در آسيب پذيري آنها است. مسأله اين است كه در دو گراف مشابه (از نظر تعداد رأس و يال) و متفاوت (از نظر اينكه يكي از آنها مستقل از مقياس است و ديگري تصادفي)، با حذف تعداد ثابتي از گره ها به همراه يال هاي متصل به آنها ارتباط چند درصد از رأس ها با يكديگر قطع مي شود؟ نتايج تحقيقات نشان مي دهد كه گراف هاي مستقل از مقياس در برابر حذف تصادفي و بي قاعده ي رأس ها ايمن تر از گراف هاي تصادفي عمل مي كنند،‌ ولي در هنگام حذف قاعده مند رؤوس (حذف Hub ها) بسيار آسيب پذير تر هستند. اين نتيجه كاربردهاي مهمي داشته است. يك نمونه از اين كاربردها در مورد شيوع بيماري ها در يك شبكه ي اجتماعي است. نگرش سنتي، يك شبكه ي اجتماعي را گرافي تصادفي مي داند. همين نگرش هنوز در مديريت اجراي پروژه هاي واكسيناسيون كه به طور تصادفي شهروندان را با احتمال يكنواخت تحت پوشش قرار مي دهد، وجود دارد. براي ريشه كن كردن بيماري ها از طريق پيشگيري از شيوع آنها، مي توان به جاي واكسينه كردن درصد زيادي از مردم به صورت تصادفي، كار را از آن هايي كه روابط عمومي ييشتري دارند (Hub ها در شبكه ي ارتباط اجتماعي) آغاز كرد. اين كار به منزله ي انتخاب هدفمند رؤوس در شبكه ي مستقل از مقياس است. براي يافتن اين افراد راه هوشمندانه اي پيشنهاد شده و آن اينكه پس از هر كسي كه واكسينه شد به سراغ دوستان وي برويم. به اين ترتيب Hub ها زودتر شكار مي شوند.