مدل باراباشی-آلبرت

مدل باراباشی-آلبرت (انگلیسی: Barabási–Albert model) یک الگوریتم تولید شبکه پیچیده بی‌مقیاس با ساز و کار پیوست ترجیحی است.گمان می‌شود شبکه‌های طبیعی‌ای مانند شبکه تنظیم ژن و برخی شبکه‌های مصنوعی، از قبیل، اینترنت، وب جهان‌گستر، تحلیل استنادی و بعضی از شبکه‌های اجتماعی تقریبا بی‌مقیاس باشند و شامل رئوس کمی‌ با درجهٔ بالای غیر عادی در مقایسه با سایر رئوس شبکه باشند. این راس‌ها را «شاه‌راس» یا «hub» گویند.

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

مفاهیم

بسیاری از شبکه‌های مشاهده‌شده (حداقل تقریباً) در کلاس شبکه‌های بی‌مقیاس قرار می‌گیرند، به این معنی توزیع درجه‌شان توانی (یا بی‌مقیاس) است، در حالی که مدل‌های تصادفی‌ای همچون مدل اردوش-رنیی و مدل واتس-اشتروگاتز از توزیع توانی تبعیت نمی‌کنند. مدل باراباشی-آلبرت یکی از مدل‌هایی ست که شبکه‌های بی‌مقیاس تولید می‌کند. این مدل دو مفهوم کلی مهم دارد: رشد و پیوست ترجیحی؛ که هردو به طور گسترده در شبکه‌های واقعی وجود دارند.

مفهوم اول، رشد، یعنی تعداد راس‌ها در طول زمان افزایش می‌یابد.

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

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

الگوریتم

مراحل رشد شبکه‌ای مبتنی بر مدل باراباشی-آلبرت. ($m_{0}=m=2$)

الگوریتم باراباشی-آلبرت یک فرایند رستوران چینی ست. در این الگوریتم، تنها یک متغیر داریم که با عدد صحیح $m$ نمایش داده می‌شود و درجه راس اولیهٔ هر راس را مشخص می‌سازد. شبکه با $m_{0}\geq m$ راس آماده‌سازی می‌گردد.

پس از آماده سازی گرافی با $m_{0}$ راس، در هر مرحله راس جدیدی به شبکه افزوده می‌شود. پس از آن $m$ راس از راس‌های پیشین به طور تصادفی برگزیده می‌شوند و از هرکدام یالی به راس جدید پیوند می‌خورد.(ممکن است در گزینش یک مرحله راس‌های تکراری نیز برگزیده شوند و یال‌های تکراری داشته باشیم. در طی مراحل و با افزایش تعداد راس‌ها، احتمال رخداد این اتفاق کم می‌شود. احتمالا به همین دلیل، منابع اصلی چندان اشاره‌ای به این خطا نکرده اند و راهکاری برای جلوگیری از آن پیشنهاد نداده اند). برگزیده شدن هر راس با احتمال $\pi _{i}$ ای تعیین می‌شود که احتمال پیوند خوردن راس جدید به راس $i$ ام است:$$\pi _{i}={\frac {k_{i}}{\Sigma _{j}k_{j}}},$$که $k_{i}$ درجه راس $i$ام است و مخرج، مجموع درجات راس‌هایی ست که تا پیش از این مرحله وجود داشته‌اند.(به زبانی دیگر، مخرج، دوبرابر تعداد یال‌های موجود در شبکه است.)

با گذر زمان، «شاه‌راس»‌هایی پدید می‌آیند که به طور سهمگینی در شبکه پیوندیده‌اند. این راس‌ها بزرگ و بزرگ‌تر می‌شوند درحالی‌که راس‌های جوان‌تر، کوچک باقی می‌مانند و فرصت رشد از ایشان سلب می‌شود. ریشه چنین رخدادی «پیوست ترجیحی» راس‌های نوورود است. این رئوس در بدو ورود «ترجیح» بیشتری به پیوند خوردن با شاه‌راس‌ها دارند تا رئوس معمولی. در واقع «پیوست ترجیحی» میل راس‌ها به برگزیدن جفت(های) پیوندی خود از شبکهٔ موجود است و ماهیت این میل را تابع احتمال $\pi _{i}$ معین می‌کند.

شبکهٔ درختی‌ای که بر اساس مدل باراباشی-آلبرت تولید شده. این شبکه متشکل از ۵۰ راس با درجه راس ابتدایی $m_{0}=1$ است.

ویژگی‌ها

توزیع درجه

توزیع درجه راس‌های یک گراف باراباشی-آلبرت با ۲۰۰٫۰۰۰ راس و ۲ یال در هر گام. رسم شده در نمودار دولگاریتمی. این نمودار از قاعده توانی با نمای ۲/۷۸- تبعیت می‌کند.

شبکه مبتنی بر مدل باراباشی-آلبرت توزیع درجهٔ بی‌مقیاس دارد. در اصل می‌توان گفت از توزیع توانی‌ای به شمایل زیر بهره‌مند است: $$P(k)\thicksim k^{-3}$$

پیوست ترجیحی غیرخطی

پیوست ترجیحی می‌تواند خطی نباشد. در واقع برخی شواهد تجربی گویای وجود چنین روابط غیرخطی‌ای هستند. درواقع مدل باراباشی-آلبرت تنها موردی خاص از پیوست ترجیحی ست. در پیوست ترجیحی غیرخطی، احتمال گزینش هر راس با رابطهٔ زیر داده می‌شود:$$\pi _{i}={\frac {k_{i}^{\alpha }}{\Sigma _{j}k_{i}^{\alpha }}},$$که ثابت $\alpha$ عددی مثبت است. با تعیین مقدار این ثابت می‌توانیم توپولوژی‌های مختلفی از شبکه را داشته باشیم. عموما ۴ رژیم برای شبکه‌ها ناظر به ثابت $\alpha$ در نظر می‌گیرند که به ترتیب از قرار زیرند:

عدم وجود پیوست ترجیحی ( $\alpha =0$ )

در این حالت شبکه بیشتر شبیه به شبکه تصادفی ست. شاه‌راسی وجود ندارد. توزیع درجات رئوس تابع نمایی ساده است.

رژیم فروخطی ($0<\alpha <1$)

در این رژیم توزیع درجه رئوس تابع نمایی کشیده خواهد بود. شاه‌راس‌ها از نظر اندازه و تعداد نسبت به شبکه بی‌مقیاس کوچک‌تر و کمترند.

رژیم خطی ($\alpha =1$)

مدل بدل به مدل باراباشی-آلبرت می‌گردد و شبکه در رژیم «خطی» خواهد بود. از این رو توزیع درجه رئوس از توزیع توانی تبعیت می‌کند.

رژیم فراخطی ($\alpha >1$)

راس‌های درشت، به شدت برای راس‌های نوورود جذاب‌اند به طوری که دینامیک «انحصار پیروزمندان» (winner-takes-all) بر شبکه حاکم می‌شود و راس‌های پیشگام در طی زمان به ابرشاه‌راس‌ها تبدیل می‌شوند.

جستارهای وابسته

• فرایند رستوران چینی
• شبکه پیچیده
• مدل اردوش-رنیی
• نظریه تراوش
• شبکه بی‌مقیاس
• شبکه جهان‌کوچک
• مدل واتس و استروگاتز

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Barabási–Albert model». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۱ مارس ۲۰۱۷.