مدل باراباشی-آلبرت - ویکی‌پدیا، دانشنامهٔ آزاد

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

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

مفاهیم[ویرایش]

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

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

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

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

الگوریتم[ویرایش]

الگوریتم باراباشی-آلبرت یک فرایند رستوران چینی ست. در این الگوریتم، تنها یک متغیر داریم که با عدد صحیح $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}$ معین می‌کند.

ویژگی‌ها[ویرایش]

توزیع درجه[ویرایش]

شبکه مبتنی بر مدل باراباشی-آلبرت توزیع درجهٔ بی‌مقیاس دارد. در اصل می‌توان گفت از توزیع توانی‌ای به شمایل زیر بهره‌مند است:

P(k)\thicksim k^{-3}

[1] Holme, Petter (2019-03-04). "Rare and everywhere: Perspectives on scale-free networks". Nature Communications (به انگلیسی). 10 (1): 1016. doi:10.1038/s41467-019-09038-8. ISSN 2041-1723. PMC 6399274. PMID 30833568.{{cite journal}}: نگهداری یادکرد:فرمت پارامتر PMC (link)

[2] Barabási, Albert-László; Albert, Réka (1999-10-15). "Emergence of Scaling in Random Networks". Science (به انگلیسی). 286 (5439): 509–512. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342.

[3] Holme, Petter (2019-03-04). "Rare and everywhere: Perspectives on scale-free networks". Nature Communications (به انگلیسی). 10 (1): 1016. doi:10.1038/s41467-019-09038-8. ISSN 2041-1723.

[4] Holme, Petter; Kim, Beom Jun (2002-01-11). "Growing scale-free networks with tunable clustering". Physical Review E. 65 (2): 026107. doi:10.1103/PhysRevE.65.026107.

[5] Newman، Mark (۲۰۱۸). توضیحات بیشتر درباره اتصال ترجیحی. ج. ۲. Oxford. ص. ۴۷۹.

[6] Albert-László Barabási. "Non-linear Preferential Attachment". Network Science (به انگلیسی).

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

مدل باراباشی-آلبرت - ویکی‌پدیا، دانشنامهٔ آزاد

مفاهیم[ویرایش]

الگوریتم[ویرایش]

ویژگی‌ها[ویرایش]

توزیع درجه[ویرایش]

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

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

رژیم خطی ( $\alpha =1$ )[ویرایش]

رژیم فراخطی ( $\alpha >1$ )[ویرایش]

جستارهای وابسته[ویرایش]

منابع[ویرایش]

مدل باراباشی-آلبرت - ویکی‌پدیا، دانشنامهٔ آزاد

مفاهیم[ویرایش]

الگوریتم[ویرایش]

ویژگی‌ها[ویرایش]

توزیع درجه[ویرایش]

پیوست ترجیحی غیرخطی[ویرایش]

عدم وجود پیوست ترجیحی ( α = 0 {\displaystyle \alpha =0} )[ویرایش]

رژیم فروخطی ( 0 < α < 1 {\displaystyle 0<\alpha <1} )[ویرایش]

رژیم خطی ( α = 1 {\displaystyle \alpha =1} )[ویرایش]

رژیم فراخطی ( α > 1 {\displaystyle \alpha >1} )[ویرایش]

جستارهای وابسته[ویرایش]

منابع[ویرایش]

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

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

رژیم خطی ( $\alpha =1$ )[ویرایش]

رژیم فراخطی ( $\alpha >1$ )[ویرایش]