شبکه بی‌مقیاس

توزیع درجه برای یک شبکه با ۱۵۰۰۰۰ رأس و درجه میانگین ۶ که با مدل باراباشی-آلبرت ساخته شده (نقطه‌های آبی). توزیع از یک فرم تحلیلی تبعیت می‌کند که با نسبت دو تابع گاما درست می‌شود (خط سیاه) که یک توزیع توانی را تقریب می‌زند.

شبکه بی‌مقیاس یا شبکه مقیاس ناوردا یا شبکه مستقل از مقیاس (انگلیسی: Scale-free network) شبکه‌ای است که توزیع درجه آن، دست کم به شکل مجانبی، توانی باشد. یعنی نسبت $P(k)$ از گره‌ها در شبکه که تعداد $k$ اتصال با بقیه گره‌ها دارند، در مقادیر بزرگ $k$ به صورت

$P(k)\ \sim \ k^{\boldsymbol {-\gamma }}$‌

رشد می‌کند که $\gamma$ پارامتری است که مقدار آن به‌طور معمول در بازه ${\textstyle 2<\gamma <3}$ قرار دارد (حالتی که در آن ممان دوم (پارامتر مقیاس) برای $k^{\boldsymbol {-\gamma }}$ بی‌نهایت است اما ممان اول آن محدود است)، البته بعضی اوقات ممکن است در خارج این کران‌ها قرار بگیرد. نام «بی‌مقیاس» می‌تواند به این اشاره کند که برخی ممان‌های توزیع درجه تعریف‌نشده هستند، طوری که شبکه یک مقیاس یا «اندازه» مشخصه ندارد.

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

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

تاریخ

در مطالعات شبکه‌های ارجاعات بین مقاله‌های علمی، درک د سولا پرایس در سال ۱۹۶۵ نشان داد که تعداد پیوندهای به مقالات (همان تعداد ارجاعاتی که دریافت می‌کنند) توزیع دم‌سنگین دارند که از توزیع پارتو یا توزیع توانی پیروی می کنند، و بنابراین شبکه ارجاعات بی‌مقیاس است. البته او از عبارت «شبکه بی‌مقیاس» استفاده نکرده بود، که چند دهه بعد ابداع شد. در مقاله‌ای دیگر در سال ۱۹۷۶، پرایس سازوکاری برای پیدایش توزیع توانی در شبکه‌های ارجاعات ارائه داد که آن را «برتری فزاینده» نامید، اما امروزه بیشتر به عنوان اتصال ترجیحی شناخته می‌شود.

گرایش به شبکه‌های بی‌مقیاس با کار آلبرت-لازلو باراباشی و ریکا آلبرت در دانشگاه نوتردام در سال ۱۹۹۹ شروع شد، که توپولوژی بخشی از وب جهان‌گستر را نقشه‌کشی کردند. آن‌ها یافتند که بعضی گره‌ها از بقیه تعداد خیلی بیشتری اتصال دارند، که آن‌ها را «هاب» (در فارسی «شاه‌رأس») نام‌گذاری کردند، و به‌طور کلی شبکه یک توزیع توانی برای تعداد پیوندهای گره‌ها دارد. بعد از یافتن تعداد دیگری شبکه که توزیع درجه دم‌سنگین داشتند، از جمله بعضی شبکه‌های اجتماعی و زیستی، باراباشی و آلبرت عبارت «شبکه بی‌مقیاس» را ابداع کردند تا دسته‌ای از شبکه‌ها را توصیف کنند که توزیع درجه توانی دارند. با این وجود، با بررسی هفت مثال از شبکه‌ها در سامانه‌های اجتماعی، اقتصادی، تکنولوژیک، زیستی و فیزیکی، آمارال و همکاران او نتوانستند شبکه بی‌مقیاسی بین آن‌ها پیدا کنند. تنها یکی از این مثال‌ها، شبکه بازیگر فیلم، توزیع درجه توانی $P(k)$ برای $k$های غیربزرگ داشت، که حتی بخش توانی آن هم به یک ناحیه انقطاع تیز ختم می‌شود که رفتار افت نمایی برای $k$های بزرگ دارد.

باراباشی و آلبرت یک سازوکار برای تولید کردن توزیع‌های توانی در شبکه‌ها ارائه دادند که آن را «اتصال ترجیحی» نام‌گذاری کردند. این مدل اصولاً همان مدلی است که پرایس ارائه داده بود. حل تحلیلی برای این سازوکار (که مشابه حل پرایس بود) در ۲۰۰۰ توسط دوروگووْزتِو، مِندِز و ساموخین و به‌طور مستقل از گروه قبل توسط کراپیوْسکی، رِدنِر و لِیوْراز ارائه شد و بعدتر توسط بیلا بولوباس ریاضی‌دان به‌طور دقیق اثبات شد. البته که این سازوکار، فقط یک زیرمجموعه خاص از شبکه‌های بی‌مقیاس را می‌سازد و تعداد زیادی سازوکار دیگر از آن موقع کشف شده است.

تاریخ شبکه‌های بی‌مقیاس هم تا حدی مورد بحث است. در سطح تجربی، خود بی‌مقیاس بودن شبکه‌های متعددی زیر سؤال است. به عنوان مثال، سه برادران فالوتسوس، بر اساس داده‌های تریس روت، معتقد بودند که اینترنت توزیع درجه توانی دارد؛ اما پیشنهاد شده که این یک واهمه لایه ۳ است که توسط روترها ایجاد می‌شود، که به صورت گره‌های درجه‌بالا به نظر می‌آیند در حالی که لایه ۲ را پنهان می‌کند که همان ساختار سامانه‌های خودگردانی است که به هم وصلشان می‌کنند.

در سطح نظری، بهبود تعریف انتزاعی بی‌مقیاسی پیشنهاد شده است. به عنوان مثال، لی و همکاران او (۲۰۰۵) «متریک بی‌مقیاس» را ارائه دادند که می‌تواند دقیق‌تر باشد. به‌طور خلاصه، اگر $G$ یک گراف با مجموعه یال $E$ باشد، و درجه رأس $v$ (یعنی همان یال‌های وصل به $v$) با $\deg(v)$ نشان داده شود، تعریف می‌کنیم

$s(G)=\sum _{(u,v)\in E}\deg(u)\cdot \deg(v)$ .

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

$S(G)={\frac {s(G)}{s_{\max }}}$ ،

که $s_{\max }$ مقدار بیشینه $s(H)$ برای $H$ در مجموعه تمام گراف‌ها با توزیع درجه مشابه $G$ است. این یک متریک بین صفر و یک می‌دهد، که یک گراف $G$ با S(G) کوچک «بامقیاس» است، و یک گراف $G$ با $S(G)$ نزدیک یک «بی‌مقیاس» است. این تعریف مفهوم خودهمانندی که نام «بی‌مقیاس» به آن اشاره می‌کند را در خود دارد.

مرور کلی

وقتی مفهوم «بی‌مقیاسی» اولین بار در زمینه شبکه‌ها معرفی شد، به یک جنبه خاص اشاره می‌کرد: یک توزیع توانی برای متغیر $k$ که به شکل $f(k)\propto k^{-\gamma }$ توصیف می‌شود. این ویژگی با اعمال تبدیل پیوسته $k\to k+\epsilon k$ شکل خود را حفظ می‌کند. این یادآور موارد مشابهی در روش‌های گروه بازبهنجارش در نظریه میدان آماری است.

با این حال، یک تفاوت اساسی بین آن‌ها وجود دارد. در نظریه میدان آماری، عبارت «مقیاس» معمولاً به اندازه سامانه مربوط است. در زمینه شبکه‌ها، «مقیاس» $k$ یک معیار برای میزان اتصال است، و به‌طور کلی با درجه یک گره سنجیده می‌شود، یعنی همان تعداد پیوند‌های متصل به آن. شبکه‌هایی که گره‌های درجه‌بالای بیشتری دارند، اتصال بیشتری دارند.

توزیع درجه توانی به ما این قابلیت را می‌دهد که ادعاهای «بی‌مقیاس» در مورد شیوع گره‌های درجه‌بالا کنیم. به عنوان مثال، می‌تونیم بگوییم «گره‌های با اتصال سه برابر میانگین، با احتمال نصف گره‌هایی با اتصال میانگین پیدا می‌شوند.» مقدار عددی دقیق اینکه دقیقاً چه چیزی «اتصال میانگین» است مهم نیست، چه صد باشد چه یک میلیون.

ویژگی‌ها

شبکه تصادفی (آ) و شبکه بی‌مقیاس (ب)

توزیع درجه شبکه‌های تصادفی و بی‌مقیاس (خط قله‌دار مربوط به شبکه تصادفی است)

شاه‌رأس

قابل‌توجه‌ترین ویژگی یک شبکه بی‌مقیاس، متداول بودن رأس‌هایی است که درجه آن‌ها از میانگین درجه بسیار بزرگ‌تر است. درجه‌بالاترین گره‌ها «شاه‌رأس» (در انگلیسی hub) نامیده می‌شوند، و گمان می‌رود نقش خاصی در شبکه‌های خود دارند، البته که این به شدت وابسته به دامنه است.

خوشگی

یک ویژگی مهم دیگر شبکه‌های بی‌مقیاس، توزیع ضریب خوشگی آن‌ها است، که با افزایش درجه گره، کاهش پیدا می‌کند. این توزیع هم توانی است. این نشان می‌دهد گره‌های درجه‌پایین به زیرگراف‌های بسیار چگال تعلق دارند که توسط شاه‌رأس‌ها به هم وصل شده اند. یک شبکه اجتماعی را در نظر بگیرید که در آن گره‌ها مردم هستند و پیوندها روابط آشنایی بین آن‌ها هستند. به سادگی می‌توان دید که مردم به تشکیل «انجمن» گرایش دارند، یعنی گروه‌های کوچکی که در آن‌ها همه یکدیگر را می‌شناسند (می‌توان چنین انجمنی را به یک گراف کامل تشبیه کرد). علاوه بر این، اعضای یک انجمن روابطی هم با افرادی بیرون انجمن خود دارند. بعضی افراد هم به تعداد انجمن‌های زیادی متصل هستند (به عنوان مثال افراد مشهور یا سیاست‌مداران). این افراد را می‌توان به عنوان شاه‌رأس‌هایی در نظر گرفت که باعث ظهور پدیده‌ی دنیای کوچک می‌شوند.

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

مقاوم‌سازی

مسئله مقاوم‌سازی بهینه شبکه‌های بی‌مقیاس که نماینده شبکه‌های واقعی مثل اینترنت و شبکه‌های اجتماعی هستند، مورد مطالعه بسیار قرار گرفته است. یک استراتژی می‌تواند مقاوم‌سازی گره‌هایی باشد که بالاترین درجه را دارند. به عنوان مثال، حمله‌های هدفمند (بین‌المللی) تعداد گره‌های کمی را حذف می‌کنند، بنابراین گره‌های کمتری نیاز است مقاوم‌سازی شوند. با این حال، در خیلی شرایط واقعی، ساختار جهانی در دسترس نیست و گره‌های با بیشترین درجه شناخته‌شده نیستند.

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

مثال‌ها

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

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

تصویری از شبکه ورقه‌ای وزن‌دار تصادفی (WPSL)

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

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Scale-free network». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۱ مارس ۲۰۱۷.