مدل باراباشی-آلبرت کیست؟ توضیح بده.
مدل باراباشی-آلبرت () یک الگوریتم تولید شبکه پیچیده بی‌مقیاس با ساز و کار پیوست ترجیحی است.گمان می‌شود شبکه‌های طبیعی‌ای مانند شبکه تنظیم ژن و برخی شبکه‌های مصنوعی، از قبیل، اینترنت، وب جهان‌گستر، تحلیل استنادی و بعضی از شبکه‌های اجتماعی تقریبا بی‌مقیاس باشند و شامل رئوس کمی‌ با درجهٔ بالای غیر عادی در مقایسه با سایر رئوس شبکه باشند. این راس‌ها را «شاه‌راس» یا «hub» گویند.هدف مدل باراباشی-آلبرت، ایجاد یک شبکه‌ بی‌مقیاس است. این مدل منجر به یک شبکه جهان‌کوچک با توزیع درجه توانی می‌شود. با وجود این‌که شبکه‌های دنیای واقعی دارای توزیع درجه‌ای شبیه به توزیع توانی هستند، اما مدل باراباشی-آلبرت به دلیل پایین بودن ضریب خوشگی در شبکه‌ای که ایجاد می‌کند، مدل کاملی برای شبیه‌سازی یک شبکه واقعی نیست. مدل دیگری که بر اساس پیوست ترجیحی منجر به یک شبکه جهان‌کوچک با توزیع درجه توانی می‌شود، مدل هُلم-کیم است. در مدل هلم-کیم شبکه‌ها با ضریب‌خوشگی بالاتری ایجاد می‌شوند.مفاهیم.بسیاری از شبکه‌های مشاهده‌شده (حداقل تقریباً) در کلاس شبکه‌های بی‌مقیاس قرار می‌گیرند، به این معنی توزیع درجه‌شان توانی (یا بی‌مقیاس) است، در حالی که مدل‌های تصادفی‌ای همچون مدل اردوش-رنیی و مدل واتس-اشتروگاتز از توزیع توانی تبعیت نمی‌کنند. مدل باراباشی-آلبرت یکی از مدل‌هایی ست که شبکه‌های بی‌مقیاس تولید می‌کند. این مدل دو مفهوم کلی مهم دارد: رشد و پیوست ترجیحی؛ که هردو به طور گسترده در شبکه‌های واقعی وجود دارند.مفهوم اول، رشد، یعنی تعداد راس‌ها در طول زمان افزایش می‌یابد.مفهوم دوم یعنی پیوست ترجیحی به این معناست که هرچه یک راس بیشتر پیوندیده‌باشد، احتمال بیشتری برای دریافت پیوندهای جدید دارد. راس‌های با درجهٔ بیشتر، میل بیشتری برای پیوند خوردن به راس‌های نوورود دارند. برای شهود بهتر به دو مثال توجه کنید. اولی شبکه‌ای از افراد است. در اینجا پیوند دو راس به معنی آشنایی یکی با دیگریست. حال وقتی تازه‌واردی وارد اجتماع می‌شود، احتمال بیشتری دارد که با افراد مشهورتر آن آشنا شود تا دیگر افراد. برای مثال دوم شبکه جهانی وب را درنظر بگیرید. در اینجا نیز مدل باراباشی-آلبرت فرض می‌کند که صفحات جدید ترجیحاً به شاه‌راس‌ها (سایت‌های مشهوری همچون گوگل و نه صفحات ناشناخته) پیوند می‌خورند. پیوست ترجیحی نمونه‌ای از چرخه بازخورد مثبت است که در آن تغییرات تصادفی اولیه (درشت‌تر بودن یک راس یا زودتر وارد شدن) خود به خود در گذر زمان تقویت می‌شوند، بنابراین تفاوت‌های اندک اولیه بیشتر می‌شوند؛ اثری که گاهی به آن اثر متیو نیز گفته می‌شود. بعدها، مدل بیانکونی-باراباشی با معرفی متغیری با عنوان «برازش» یا «fitness» در صدد رفع این ایراد برمی‌آید. الگوریتم.الگوریتم باراباشی-آلبرت یک فرایند رستوران چینی ست. در این الگوریتم، تنها یک متغیر داریم که با عدد صحیح formula_1 نمایش داده می‌شود و درجه راس اولیهٔ هر راس را مشخص می‌سازد. شبکه با formula_2 راس آماده‌سازی می‌گردد. پس از آماده‌سازی گرافی با formula_3 راس، در هر مرحله راس جدیدی به شبکه افزوده می‌شود. پس از آن formula_1 راس از راس‌های پیشین به طور تصادفی برگزیده می‌شوند و از هرکدام یالی به راس جدید پیوند می‌خورد. (ممکن است در گزینش یک مرحله راس‌های تکراری نیز برگزیده شوند و یال‌های تکراری داشته باشیم. در طی مراحل و با افزایش تعداد راس‌ها، احتمال رخداد این اتفاق کم می‌شود. احتمالا به همین دلیل، منابع اصلی چندان اشاره‌ای به این خطا نکرده‌اند و راهکاری برای جلوگیری از آن پیشنهاد نداده‌اند). برگزیده‌شدن هر راس با احتمال formula_5 ای تعیین می‌شود که احتمال پیوند خوردن راس جدید به راس formula_6 ام است:formula_7که formula_8 درجه راس formula_6ام است و مخرج، مجموع درجات راس‌هایی ست که تا پیش از این مرحله وجود داشته‌اند. (به زبانی دیگر، مخرج، دوبرابر تعداد یال‌های موجود در شبکه است.)با گذر زمان، «شاه‌راس»‌هایی پدید می‌آیند که به طور سهمگینی در شبکه پیوندیده‌اند. این راس‌ها بزرگ و بزرگ‌تر می‌شوند درحالی‌که راس‌های جوان‌تر، کوچک باقی می‌مانند و فرصت رشد از ایشان سلب می‌شود. ریشه چنین رخدادی «پیوست ترجیحی» راس‌های نوورود است. این رئوس در بدو ورود «ترجیح» بیشتری به پیوند خوردن با شاه‌راس‌ها دارند تا رئوس معمولی. در واقع «پیوست ترجیحی» میل راس‌ها به برگزیدن جفت(های) پیوندی خود از شبکهٔ موجود است و ماهیت این میل را تابع احتمال formula_5 معین می‌کند.ویژگی‌ها.توزیع درجه.شبکه مبتنی بر مدل باراباشی-آلبرت توزیع درجهٔ بی‌مقیاس دارد. در اصل می‌توان گفت از توزیع توانی‌ای به شمایل زیر بهره‌مند است:formula_11پیوست ترجیحی غیرخطی.پیوست ترجیحی می‌تواند خطی نباشد. در واقع برخی شواهد تجربی گویای وجود چنین روابط غیرخطی‌ای هستند. درواقع مدل باراباشی-آلبرت تنها موردی خاص از پیوست ترجیحی‌ست. در پیوست ترجیحی غیرخطی، احتمال گزینش هر راس با رابطهٔ زیر داده می‌شود:formula_12که ثابت formula_13 عددی مثبت است. با تعیین مقدار این ثابت می‌توانیم توپولوژی‌های مختلفی از شبکه را داشته باشیم. عموما ۴ رژیم برای شبکه‌ها ناظر به ثابت formula_13 در نظر می‌گیرند که به ترتیب از قرار زیرند:عدم وجود پیوست ترجیحی ( formula_15 ).در این حالت شبکه بیشتر شبیه به شبکه تصادفی ست. شاه‌راسی وجود ندارد. توزیع درجات رئوس تابع نمایی ساده است. رژیم فروخطی (formula_16).در این رژیم توزیع درجه رئوس تابع نمایی کشیده خواهد بود. شاه‌راس‌ها از نظر اندازه و تعداد نسبت به شبکه بی‌مقیاس کوچک‌تر و کمترند.رژیم خطی (formula_17).مدل بدل به مدل باراباشی-آلبرت می‌گردد و شبکه در رژیم «خطی» خواهد بود. از این رو توزیع درجه رئوس از توزیع توانی تبعیت می‌کند.رژیم فراخطی (formula_18).راس‌های درشت، به شدت برای راس‌های نوورود جذاب‌اند به طوری که دینامیک «انحصار پیروزمندان» (winner-takes-all) بر شبکه حاکم می‌شود و راس‌های پیشگام (آنها که از ابتدای شکل‌گیری شبکه بوده‌اند) در طی زمان به ابرشاه‌راس‌ها تبدیل می‌شوند.