بخش 4-1
مقدمه

در شبکه جهانی وب صفحه ها و یا اسناد، نقش گره و ارجاع بین صفحات، نقش پیوند بین آنها را بازی می کنند. در وب با یک کلیک از یک صفحه وب به صفحه دیگری انتقال می یابیم. تعداد اسناد موجود در وب بیش از یک تریلیون (N≈10¹²) تخمین زده شده است و تا کنون بزرگ‌ترین شبکه ساخته دست بشر است و اندازه آن از شبکه مغز انسان (N ≈ 10¹¹ نرون) نیز بزرگ‌تر است.

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

برای بدست آوردن نقشه اتصالات گره‌های وب از نرم‌افزاری به نام خزشگر استفاده می شود. یک خزشگر می‌تواند از هر سند وب شروع کرده و پیوندهای (URL) آن‌ را شناسایی کند. سپس صفحات مرتبط با هر پیوند را استخراج می کند و این کار به همین روال ادامه پیدا خواهد کرد تا زمانی که همه صفحات دریافت شوند. تکرار این فرآیند یک نقشه محلی از وب را برمی‌گرداند. موتورهای جستجو مانند گوگل یا بینگ برای پیدا کردن و نمایه سازی اسناد جدید و برای نگه‌داری جزئیات نقشه وب از خزشگر‌ها استفاده می‌کنند.

اولین بار Hawoong Jeong دردانشگاه نوتردام نسبت به تهیه نقشه وب به منظور مطالعه ساختار زیربنایی آن اقدام کرد. او نقشه دامنه nd.edu [1] را که شامل حدود 300،000 سند و 5/1 میلیون پیوند بود (منبع آنلاین 4.1)، استخراج کرد. هدف از ایجاد این نقشه، مقایسه مشخصات گراف وب با مدل شبکه تصادفی بود. در واقع تا سال 1998 تصور می شد شبکه های وب به خوبی با مدل شبکه های تصادفی سازگار هستند. محتوای هر صفحه وب علایق شخصی و حرفه ای سازنده آن( اشخاص یا سازمان ها) را نشان می‌دهد. با توجه به تنوع این سلایق به نظر می رسد که این پیوند ها بصورت تصادفی ایجاد شده اند.

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

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

بخش4-2
قوانین توان و شبکه‌های بی‌مقیاس

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

معادله (4.1) توزیع قانون توان نامیده می‌شود و γ توان درجه است (نکته 4.1). اگر ما از (4.1) لگاریتم بگیریم خواهیم داشت:

با درنظر گرفتن معادله (4.1) ، انتظار می‌رود کهlog p_k با log k رابطه خطی داشته باشد، شیب این خط توان درجه γ است (شکل4.2).

وب یک شبکه جهت دار است، از این رو هر سند با یک درجه خروجیk_out و یک درجه ورودی k_in مشخص می‌شود. k_out نشان دهنده تعداد پیوندهایی است که از این سند به اسناد دیگر اشاره می‌کنند و kin نشان دهنده تعداد اسنادی است که به این سند اشاره می‌کنند. بنابراین باید توزیع این دو درجه را از یکدیگر تمیز دهیم: احتمال اینکه یک سند دلخواه (که به صورت تصادفی انتخاب می شود) به k_out سند وب اشاره کند، p_kout، و احتمال اینکهk_in سند وب به یک گره دلخواه اشاره کنند، p_kin نامیده می-شود. در مورد وب می‌توان هر دو مقدار p_kout و p_kin را با قانون توان تقریب زد:

که γ_in و γ_out به ترتیب توان‌های درجه ورودی و خروجی هستند (شکل4.2). به طور کلی γ_in می‌تواند با γ_outمتفاوت باشد. برای مثال در شکل 4.1 داریم γ_in ≈ 2.1 و γ_out ≈ 2.45.

نتایج تجربی نمایش داده شده درشکل 4.2 سندی مبنی بر وجود شبکه‌ای است که توزیع درجه آن کاملا با توزیع پواسون که شبکه‌های تصادفی را مشخص می‌کند، متفاوت است. این نوع شبکه ها، شبکه مقیاس آزاد یا بدون مقیاس نامیده می شوند که در ادامه آنها را تعریف خواهیم کرد [2]:

یک شبکه مقیاس آزاد شبکه‌ای است که توزیع درجه آن از قانون توان پیروی می‌ کند..

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

برای فهم بهتر ویژگی مقیاس آزاد، باید تعریف دقیق‌تری از توزیع قانون توان ارائه دهیم. بنابراین در ادامه فرمول‌های گسسته و پیوسته استفاده شده در این کتاب را توضیح می دهیم.

فرمول‌ گسسته

از آنجایی که درجه‌ گره‌ها اعداد صحیح و مثبت می‌باشند، k = 0, 1, 2, ..., فرمول گسسته p_k احتمال این که گره‌ای دقیقا k پیوند داشته باشد را تعیین می‌کند.

ثابت C با توجه به شرط نرمال‌سازی مشخص می‌شود.

با استفاده از (4.5) به دست می‌آوریم،

از این رو

که ζ (γ) تابع ریمان-زتا است. بنابراین برای k > 0 توزیع قانون توان گسسته به این شکل است:

توجه کنید، که (4.8) در k=0 واگرا است. اگر نیاز باشد می‌توانیم p₀ را که کسری از گره‌هایی است که به دیگر گره‌ها پیوند ندارند را به طور مجزا تعریف کنیم. در این مورد نیاز است که محاسبه C در (4.7) با p₀ ترکیب شود.

فرمول پیوسته

در محاسبات تحلیلی اغلب فرض می‌شود که درجه می‌تواند هر مقدار حقیقی مثبتی داشته باشد. در این صورت توزیع درجه قانون توان را چنین می نویسیم:

با استفاده از شرط نرمالسازی

که در نتیجه فرمول زیر بدست می‌ آید:

بنابراین در فرمول پیوسته، توزیع درجه به این شکل است

در اینجا k_min کوچک‌ترین درجه‌ای است برای آن قانون توان (4.8) برقرار است

توجه کنید که p_k در فرمول گسسته معنای دقیق دارد: احتمال اینکه نودی که به شکل تصادفی انتخاب شده درجه k داشته باشد. در مقابل انتگرال p(k) که در فرمول پیوسته با آن روبرو می‌شوید تعبیر فیزیکی دارد:

احتمال اینکه یک گره دلخواه (تصادفی) درجه‌ای بین k₁ و k₂ داشته باشد.

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

بخش 4.3
هاب‌ها

تفاوت اصلی بین یک شبکه تصادفی و بی‌مقیاس در دنباله توزیع درجه وجود دارد، که نشان دهنده ناحیه k های بزرگ از p_kاست. برای نشان دادن این موضوع، در شکل 4.4 قانون توان با توزیع پواسون مقایسه شده است. نتایج نشان می دهد که:

• برای k کوچک قانون توان بالای تابع پواسون قرار دارد، نشان دهنده آن است که یک شبکه بی‌مقیاس شامل تعداد زیادی از گره‌ها با درجه کوچک است، که اکثر آن‌ها در یک شبکه تصادفی وجود ندارند.
• برای k در مجاورت 〈k〉 توزیع پواسون بالاتر از قانون توان است، نشان می‌دهد که در یک شبکه تصادفی تعداد مضاعفی گره با درجه k≈〈k〉 وجود دارد.
• برای k بزرگ قانون توان مجددا بالای منحنی پواسون است. این تفاوت در نمودار لگاریتمی بهتر قابل مشاهده است (شکل 4.4 ب). این شکل نشان می‌دهد که احتمال مشاهده یک گره با درجه بالا یا هاب، در شبکه بی مقیاس به مراتب بالاتر از شبکه تصادفی است.

برای اینکه نشان دهیم تفاوت بین شبکه تصادفی و بدون مقیاس تا چه اندازه فاحش است، از شبکه وب استفاده می¬کنیم. احتمال وجود گره با k=100 در یک توزیع پواسون تقریبا p₁₀₀≈10⁻⁹⁴ است در حالی که اگر p_k از قانون توان پیروی کند تقریبا p₁₀₀≈4x10^-4 است. درنتیجه اگر وب شبکه‌ای تصادفی با =4.6 و اندازه N≈10¹² باشد، انتظار داریم به تعداد

گره‌ها با حداقل 100 پیوند داشته باشیم که در واقع هیچ است. در مقابل با توجه به توزیع درجه قانون توان وب‌، با γ_in = 2.1 داریم N_k≥100 = 4x10⁹ ، یعنی بیش از چهار میلیارد نود با درجه k ≥100.

بزرگ‌ترین هاب

همه شبکه‌های واقعی محدود هستند. اندازه وب N ≈ 10¹² گره تخمین زده می‌شود. اندازه شبکه اجتماعی با جمعیت کره زمین، تقریبا N ≈ 7 × 10⁹ برابر است. این اعداد، بسیار بزرگ اما محدود هستند. دیگر شبکه‌ها در مقایسه کم‌رنگ هستند: شبکه ژنتیک در یک سلول انسان تقریبا 20000 ژن دارد در حالی که شبکه متابولیک باکتری‌های E. Coli به تنهایی حدود هزار متابولیت دارد. حال این پرسش مطرح می‌شود که اندازه شبکه چه تاثیری بر اندازه هاب‌های آن دارد؟ برای پاسخ به این سوال، بیشینه درجه k_max که برش طبیعی (ذاتی) توزیع درجه p_k نامیده می‌شود را محاسبه می‌کنیم، و اندازه مورد انتظار بزرگ‌ترین هاب در شبکه را به دست می آوریم.

ابتدا محاسبات را برای توزیع نمایی انجام می دهیم

$p(k) = Ce^{ - \lambda k}$

برای شبکه‌ای با حداقل درجه k_min با شرایط نرمالسازی

$\int\limits_{k_{\min } }^\infty {p(k)dk = 1} \hspace{20 mm} (4 . 15)$

خواهیم داشت C = λe^λk_min. برای محاسبه k_max فرض می‌کنیم که در شبکه‌ای با N گره حداکثر یک گره در بازه((k_max, ∞)) قرار داشته باشد (مباحث پیشرفته ب.3). به عبارت دیگر احتمال مشاهده گره ای که درجه آن بیش از k_max باشد، 1/N است، پس خواهیم داشت:

$\int\limits_{k_{\max } }^\infty {p(k)dk = \frac{1}{N}} \hspace{20 mm} (4 . 16)$

از رابطه (4.16) نتیجه می‌گیریم:

$k_{\max } = k_{\min } + \frac{{\ln N}}{\lambda } \hspace{20 mm} (4 . 17)$

از آنجا که رشد تابع lnN به نسبت اندازه سیستم (N) کند است، رابطه (4.17) نشان می دهد که تفاوت معنی داری بین حداکثر و حداقل درجه وجود نخواهد داشت. برای یک توزیع درجه پواسون، محاسبه کمی پیچیده تر است، اما وابستگی k_max نسبت به N حتی از رابطه (4.17) نیز کندتر است (مباحث پیشرفته ب.3).

برای شبکه بی‌مقیاس، با توجه به (4.12) و (4.16) برش ذاتی از رابطه زیر پیروی می‌کند:

$k_{\max } = k_{\min } N^{\frac{1}{{\gamma - 1}}} \hspace{20 mm} (4 . 18)$ از این رو هر چه شبکه بزرگ‌تر باشد، درجه بزرگ‌ترین هاب آن هم بزرگ‌تر خواهد بود. وابستگی چند جمله‌ای k_max به N دلالت بر این امر دارد که در یک شبکه‌ بی‌مقیاس،انتظار می رود تفاوت بزرگی بین کوچک‌ترین گره، k_min ، و بزرگ‌ترین هاب، k_max وجود داشته باشد(شکل 4.5).

برای نشان دادن تفاوت در حداکثر درجه یک شبکه نمایی و بی‌مقیاس اجازه دهید به مثال وب از شکل 4.1 ، متشکل از N ≈ 3 × 10⁵ گره برگردیم. چنان‌که k_min = 1، اگر توزیع درجه نمایی دنبال شود، (4.17) پیش‌بینی می‌شود که حداکثر درجه برای λ=1، k_max ≈ 14 باشد. در شبکه‌ای بی‌مقیاس با اندازه مشابه وγ = 2.1 ، (4.18) عدد کاملا متفاوت‌ k_max ≈ 95,000 پیش‌بینی می‌شود. توجه داشته باشید که بزرگ‌ترین درجه شبکه وب که در شکل 4.1 نشان داده شده است، 10.721 است، که به مقدار برآوردی برای شبکه بی مقیاس نزدیک است. این نتیجه تاییدی است بر برداشت ما که در شبکه تصادفی مجال ایجاد هاب‌ فراهم نیست، درحالی‌که هاب ها در شبکه‌های بی‌مقیاس به طور طبیعی حضور دارند.

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

• اگر n −γ + 1 ≤ 0 آنگاه اولین عبارت سمت راست (4.20)، k_max^n−γ+1، با افزایش k_max صفر می‌شود. بنابراین تمامی گشتاورها در حالتی که n ≤ γ−1 باشد، محدود هستند.
• اگر n−γ+1 > 0 آنگاه em>〈kⁿ〉 در حالت حدی k_max→∞، به سمت بی‌نهایت میل می‌کند. بنابراین تمامی گشتاورهای بزرگ‌تر از γ-1 واگرا هستند.

توان درجه γ در بسیاری از شبکه‌های بی‌مقیاس بین 2 و 3 است (جدول 4.1). ازاین‌رو گشتاور اول 〈k〉) در N → ∞ محدود است، اما گشتاورهای دوم و بالاتر ، 〈k²〉، 〈k³〉، به بی‌نهایت می‌روند. این واگرایی به ما کمک می‌کند تا منشأ "بی‌مقیاس" را درک کنیم. در واقع اگر درجه‌ها از توزیع نرمال پیروی کنند، آنگاه درجه گره انتخاب شده به شکل تصادفی معمولا در بازه زیر است

با این حال، درجه میانگین ‹k› و انحراف معیار استاندارد σ_k در شبکه‌های تصادفی و بی‌مقیاس تفاوت فاحشی با هم دارد:

• برای شبکه‌ای تصادفی با توزیع درجه پواسون σ_k = ‹k›^1/2 است، که همواره کمتر از 〈k〉 است. از این رو گره‌های شبکه درجاتی در بازه k = 〈k〉 ± 〈k〉^1/2 دارند. به عبارت دیگر درجات گره‌ها در یک شبکه تصادفی نزدیک به هم است و میانگین درجه 〈k〉 به عنوان "مقیاس" یک شبکه تصادفی به کار می‌رود.
• • شبکه‌های بی‌مقیاس فاقد مقیاس
  برای شبکه‌ای با توزیع درجه قانون توان با γ < 3 گشتاور اول محدود است اما گشتاور دوم نامحدود خواهد بود. واگرایی 〈k²〉 (و σ_k) برای N بزرگ نشان می‌دهد که پراکندگی و فاصله درجات از میانگین می‌تواند بسیار زیاد باشد. این به این معنی است که زمانی که ما گره‌ای را به شکل تصادفی انتخاب می‌کنیم، نمی دانیم چه چیزی در انتظار است: درجه گره انتخاب شده می‌تواند یک مقدار کوچک یا هر مقدار بزرگی باشد. از این رو شبکه‌هایی با γ < 3 مقیاس داخلی معنی‌داری ندارند و " بی‌مقیاس" نامیده می شوند (شکل 4.7 ).
  برای مثال میانگین درجه مثال شبکه وب که پیش از این مطرح شد 〈k〉 = 4.60 است (جدول 4.1). با توجه به γ≈ 2.1، گشتاور دوم واگرا است، به این معنی که انتظار ما از درجه داخلی یک صفحه دلخواه وب در حالت حدی N → ∞، k=4.60 ± ∞ است. یعنی یک صفحه دلخواه وب می‌تواند به احتمال زیاد به صفحه ای از درجه یک یا دو دسترسی داشته باشد، زیرا 74.02% از گره‌ها دارای درجه‌ای کمتر از ⟨k⟩ هستند. با این وجود، می‌تواند به گره ای با صدها میلیون پیوند مانند گوگل یا فیسبوک نیز دسترسی داشته باشد.

اگرچه واگرایی 〈k²〉 فقط در حالت حدی N → ∞ معنا دارد، اما واگرایی در شبکه‌های محدود نیز به چشم می آید. اطلاعات گشتاور دوم ده شبکه واقعی در جدول 4.1 و انحراف استاندارد آن در شکل 4.8 ارائه شده است. برای اکثر این شبکه‌ها σ به طور قابل توجه‌ای بزرگ‌تر از ⟨k⟩ است، که دامنه زیاد تغییرات در درجه گره ها را نمایان می سازد. برای مثال درجه یک گره دلخواه در شبکه وب k_in = 4.60 ± 1546 است. این موضوع بار دیگر نشان می‌دهد که میانگین حاوی اطلاعات مفید و قابل اتکا نیست.

به طور خلاصه، نام بی‌مقیاس بر عدم وجود مقیاس داخلی تاکید دارد که پیامد آن وجود گره‌هایی با درجات بسیار متفاوت در یک شبکه است. این ویژگی شبکه‌های بی‌مقیاس را از شبکه‌های توری ، که در آن همه گره‌ها درجه یکسان دارند (σ = 0)، یا شبکه‌های تصادفی، که درجات در یک بازه محدود (σ = 〈k〉^1/2) تغییر می کند، متمایز می‌کند. همانطور که در فصول آینده خواهیم دید، این واگرایی منشأ برخی از جذاب‌ترین ویژگی‌های بدون مقیاس از استحکام آن‌ها گرفته تا خرابی‌های تصادفی تا شیوع غیر عادی ویروس‌ها است.

بخش 4.5
جهانی بودن

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

این تفاوت عواقب مهمی دارد: هزینه برقراری پیوند بین دو صفحه وب یکی در بوستون و دیگری در بوداپست با دو صفحه روی یک کامپیوتر یکسان است. در حای که برای اتصال یک مسیریاب در بوستون و دیگری در بوداپست نیاز به کابل¬کشی بین آمریکای شمالی و اروپا داریم که بسیار پرهزینه است. علیرغم این تفاوتها، توزیع درجه هر دو شبکه به خوبی با قانون توان تطبیق دارد [1, 5 ,6]. نشانه های ماهیت بی‌مقیاس بودن اینترنت در شکل 4.9قابل مشاهده است، چند مسیریاب با درجه بالا، تعداد زیادی از مسیریاب ها با چند پیوند محدود را به یکدیگر متصل می‌کنند.

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

تنوع سیستم‌هایی که دارای خاصیت بی‌مقیاس هستند، شگفت انگیز است (نکته 4.2). وب یک شبکه ساخت انسان است که قدمت آن اندکی بیش از دو دهه است، در حالی که شبکه برهم¬کنش پروتئین محصول چهار میلیارد سال تکامل است. در برخی از این شبکه‌ها گره‌ها مولکول ها و در برخی دیگر کامپیوترها هستند. این تنوع است که ما را وادار می‌کند تا خصوصیات بی‌مقیاس را ویژگی شبکه‌ای فراگیر (جهانی) بدانیم.

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

رسم کردن درجه توزیع

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

اندازه‌گیری توان درجه

با برازش یک خط راست روی یک نمودار log-log می‌توان تقریبی از توان درجه به دست آورد. با این وجود، این روش می‌تواند دچار سوی سیستمی شده و γ نادرستی را نتیجه دهد. ابزارهای آماری برای تخمین γ وجود دارند، که در مباحث پیشرفته ج.4 مطرح شده اند.

شکل p_k برای شبکه‌های واقعی

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

به طور خلاصه، از زمان کشف ماهیت بی‌مقیاس وب در سال 1999 تعداد زیادی از شبکه‌های واقعی در حوزه علم و فناوری از شبکه‌های بیولوژیکی گرفته تا شبکه های اجتماعی و زبانی به عنوان شبکه های بی‌مقیاس شناخته شده‌اند (نکته 4.2). البته این بدان معنا نیست که همه شبکه‌ها مقیاس آزاد هستند. در واقع بسیاری از شبکه‌های مهم، از شبکه برق گرفته تا شبکه‌هایی که در علم مواد مشاهده می‌شوند، خاصیت بی‌مقیاس را بروز نمی‌دهند (نکته 4.3).

بخش 4.6
ویژگی فوق‌العاده کوچک

وجود هاب‌ها در شبکه‌های بی‌مقیاس فرضیه جالبی را مطرح می‌کند: آیا هاب‌ها بر ویژگی جهان کوچک تأثیر می‌گذارند؟ شکل 4.4 این فرضیه را تایید می کند زیرا شرکت های هواپیمایی از هاب ها برای کاهش فاصله (تعداد توقف ها) در پروازها استفاده می کنند. محاسبات ریاضی نیز این موضوع را تایید می کند که فاصله‌ها در شبکه‌های بی‌مقیاس کمتر از فاصله‌ها در شبکه‌ تصادفی معادل هستند.

وابستگی میانگین فاصله ⟨d⟩ به اندازه سیستم N و درجه توان γ توسط فرمول زیر نمایش داده می‌شود [29, 30]

در ادامه رفتار ⟨d⟩ را در چهار محدوده ای که در رابطه (4.22) بیان شده و در شکل 4.12 نیز نشان داده شده است بررسی می کنیم:

فرم غیرعادی (γ = 2)

با توجه به رابطه 4.18 برای γ = 2 درجه بزرگ‌ترین هاب به شکل خطی با اندازه شبکه رشد می‌کند، یعنی k_max ~ N، در این حالت، پیکربندی هاب و گره های اقماری ایجاد می شود، که در آن همه‌ گره‌ها به یکدیگر نزدیک هستند زیرا همه آن‌ها به یک هاب مرکزی یکسان متصل هستند. در این ناحیه میانگین طول مسیر به N وابسته نیست.

جهان فوق العاده کوچک (2 < γ < 3)

رابطه (4.22) پیش‌بینی می‌کند که در این ناحیه میانگین فاصله طبق lnlnN افزایش می‌یابد که به طور قابل توجه‌ای رشدی کندتر از lnN حاصل از شبکه‌های تصادفی دارد. شبکه‌هایی که در این ناحیه قرار می گیرند را فوق‌العاده کوچک می‌نامیم، زیرا هاب‌ها به شدت طول مسیر را کاهش می‌دهند [29]. هاب ها با اتصال به تعداد زیادی گره با درجه کوچک، فاصله بین آن ها را کوتاه می کنند.

برای مشاهده خاصیت فوق‌العاده کوچک جهانی، مجددا شبکه اجتماعی جهان با برای مشاهده خاصیت فوق‌العاده کوچک جهانی، مجددا شبکه اجتماعی جهان با N ≈ 7x109 را در نظر بگیرید. اگر جامعه با شبکه‌ای تصادفی مدل شود، ضریب وابستگی فاصله به N معادل lnN = 22.66 است. در مقابل به شکل شهودی برای شبکه‌ای بی مقیاس ضریب وابستگی فاصله به N معادل lnlnN = 3.12 است، نشان می‌دهد که هاب‌ها به طور چشمگیری فاصله بین گره‌ها را کاهش می‌دهند. را در نظر بگیرید. اگر جامعه با شبکه‌ای تصادفی مدل شود، ضریب وابستگی فاصله به N معادل lnN = 22.66 است. در مقابل به شکل شهودی برای شبکه‌ای بی مقیاس ضریب وابستگی فاصله به N معادل lnlnN = 3.12 است، نشان می‌دهد که هاب‌ها به طور چشمگیری فاصله بین گره‌ها را کاهش می‌دهند.

نقطه بحرانی (γ = 3)

این مقدار از لحاظ نظری اهمیت ویژه‌ای دارد، زیرا گشتاور دوم توزیع درجه دیگر واگرا نمی‌شود، بنابراین γ = 3 را نقطه بحرانی می‌نامیم. در این نقطه بحرانی، فاصله نسبت به اندازه شبکه مشابه شبکه‌های تصادفی با ضریب lnN وابسته است. با این حال محاسبات حاکی از وجود جمله مضاعف لگاریتمی lnlnN در مخرج کسر است [29، 31]، که باعث می شود فاصله‌ در مقایسه با یک شبکه تصادفی با اندازه مشابه، کاهش یابد.

جهان کوچک(γ > 3)

Iدر این ناحیه 〈k²〉 محدود است و میانگین فاصله تا حدی به مدل جهان کوچک شبکه‌های تصادفی نزدیک است. درحالی‌که هاب ها همچنان حضور دارند، اما به اندازه کافی بزرگ و فراوان نیستند که تأثیر معنی‌داری بر فاصله گره‌ها داشته باشند.

روی‌هم‌رفته رابطه 4.22 نشان می‌دهد که هاب‌ها هرچه برجسته‌تر باشند، به طور مؤثرتری فاصله بین گره‌ها را تقلیل می‌دهند. شکل 4.12الف نیز این نتیجه‌گیری را تایید می‌کند. این شکل اندازه میانگین فاصله را برای شبکه‌های بی‌مقیاس با γ های متفاوت نمایش می‌دهد. درحالی‌که برای N کوچک فاصله‌ها در چهار ناحیه نزدیک به هم هستند، اما برای N بزرگ تفاوت‌ قابل ملاحظه ای دارند.

شواهد بیشتری در این خصوص در شکل 4.12ب-د ارائه شده است و توزیع فاصله برای شبکه‌های بی‌مقیاس با γ و N متفاوت ترسیم شده است برای N = 10² توزیع فاصله ها برای مقادیر مختلف γ با هم همپوشانی دارند و تفاوت فاحشی وجود ندارد. ضمنا برای N = 10⁶، p_d های مشاهده شده برای γهای مختلف به خوبی قابل تفکیک هستند و تفاوت محسوس دارند.شکل 4.12د همچنین نشان می‌دهد که هر چه توان درجه بزرگ‌تر باشد، فاصله بین گره‌ها بیشتر است.

به طور خلاصه، خاصیت بی‌مقیاس چندین اثر روی فاصله‌های شبکه دارد:

• میانگین طول مسیرها را کاهش می‌دهد. بنابراین اکثر شبکه‌های بی‌مقیاس واقعی نه تنها "کوچک" بلکه "فوق العاده کوچک" هستند. این امر حاصل وجود هاب‌ها است که مانند پل‌ها بین بسیاری از گره‌ها با درجه کوچک عمل می‌کنند و فاصله را کاهش می دهند.
• • ⟨d⟩ به اندازه سیستم وابسته است (مطابق رابطه 4.22). هر چه γ کوچک‌تر باشد، فاصله‌های بین گره‌ها کوتاه‌تر هستند.
• • فقط برای γ > 3 ضریب وابستگی فاصله به اندازه شبکه ln N است که به خاصیت جهان کوچک شبکه‌های تصادفی نزدیک است (شکل 4.12).

بخش 4.7
نقش توان درجه

بسیاری از خواص شبکه بی‌مقیاس به مقدار توان درجه γ وابسته هستند. بررسی دقیق جدول 4.1 نشان می‌دهد که:

• γ از یک سیستم به سیستم دیگر متفاوت است و ما را وادار می‌کند تا چگونگی تغییرات یک شبکه را با γ کشف کنیم.
• در اکثر سیتم‌های واقعی توان درجه بزرگتر از 2 است و این سوال را پیش می آورد که چرا شبکه‌هایی با γ < 2 مشاهده نمی‌کنیم؟

برای پرداختن به این سوالات، در ادامه، چگونگی تغییرات خصوصیات شبکه بی‌مقیاس با γ (نکته 4.5) را بررسی می کنیم.

ناحیه غیرعادی (γ≤ 2)

برای γ< 2 نمای 1/(γ- 1) در رابطه 4.18 بزرگ‌تر از یک است، در حالی که تعداد پیوندهای متصل به بزرگ‌ترین هاب سریع‌تر از اندازه شبکه رشد می‌کند. این بدان معناست که برای N به اندازه کافی بزرگ، درجه بزرگ‌ترین هاب باید از تعداد کل گره‌های شبکه فراتر رود، از این رو گرهی برای اتصال باقی نخواهد ماند. به طور مشابه، برای γ < 2 میانگین درجه ⟨k⟩ در N → ∞ واگرا است. این نتایج عجیب تنها دو مورد از ویژگی‌های غیر عادی شبکه‌های بی‌مقیاس در این ناحیه را نشان می دهد. عملا چنانچه اجازه پیوند متعدد یا چندپیوندی وجود نداشته باشد، امکان به وجود آمدن شبکه بی مقیاس در ناحیه γ < 2 وجود نخواهد داشت. (نکته 4.6).

ناحیه بی‌مقیاس (2 ‹ γ ‹ 3)

در این ناحیه گشتاور اول توزیع درجه محدود است اما گشتاور‌های دوم و بالاتر در حالت حدی N →∞ واگرا هستند. در نتیجه شبکه‌های بی مقیاس در این ناحیه فوق‌العاده کوچک هستند (بخش 4.6). طبق رابطه 4.18 مقدار k_max با اندازه شبکه با نمای1/ (γ - 1) که کمتر از یک است، رشد می‌کند. از این رو سهم بزرگ‌ترین هاب که نشان دهنده کسری از گره‌ها است که به آن متصل می‌شوند به k_max/N ~ N^{-(γ-2)/(γ-1)}

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

ناحیه شبکه‌تصادفی (γ > 3)

با توجه به رابطه 4.20 برای γ > 3 گشتاور اول و دوم هر دو محدود هستند. شخیص خصوصیات یک شبکه‌ بی‌مقیاس از شبکه تصادفی با اندازه مشابه در این ناحیه دشوار است. برای مثال رابطه 4.22 نشان می‌دهد، که میانگین فاصله بین گره‌ها به رابطه جهان کوچک در شبکه‌های تصادفی نزدیک است. دلیل این امر این است که برای γ بزرگ توزیع درجه p_k آنقدر کاهش می یابد که تعداد و اندازه هاب ها به شدت کاهش می یابد.

توجه کنید که شبکه‌های بی‌مقیاس با γ بزرگ به سختی از شبکه‌های تصادفی تمیز داده می‌شوند. در واقع، برای اثبات بی مقیاس بودن یک شبکه و پیروی آن از توزیع قانون توان نیاز به بزرگنمایی از مرتبه 2-3 است، بدین معنا که k_max باید حداقل 10² - 10³بار بزرگ‌تر از k_min باشد. با معکوس کردن رابطه 4.18 می‌توانیم اندازه شبکه‌ مورد نیاز را برای تشخیص شبکه ای در این ناحیه محاسبه کنیم:

برای مثال، اگر بخواهیم ماهیت بی‌مقیاس را برای شبکه‌ای با γ = 5 و بزرگ‌نمایی حداقل دو برابر (k_min ~ 1 و k_max ≃ 10²) اثبات کنیم، با توجه به رابطه 4.23 اندازه شبکه باید بزرگ‌تر از N > 10⁸ باشد. نقشه تعداد بسیار بسیاد اندکی شبکه با این اندازه ترسیم شده است. بنابراین، ممکن است شبکه‌های زیادی با توان درجه بالا وجود داشته باشند که به دلیل اندازه محدود آن‌ها یافتن شواهدی برای اثبات بی‌مقیاس بودن آن‌ها مشکل باشد.

به طور خلاصه، درمی‌یابیم که رفتار شبکه‌های بی‌مقیاس حساس به مقدار توان درجه γ است. از لحاظ نظری، جالب‌ترین ناحیه 2 < γ < 3 است، که واگرایی〈k²〉 ، شبکه‌های بی‌مقیاس را فوق‌العاده کوچک می‌سازد. جالب است که، بسیاری از شبکه‌های جالب، از وب گرفته تا شبکه‌های برهم کنش های پروتئین ها، در این ناحیه قرار دارند.

بخش 4.8
ایجاد شبکه‌ها با توزیع درجه دلخواه

شبکه‌های ایجاد شده توسط مدل اردوش-رنی توزیع درجه پواسون‌ دارند. اما، نتایج تجربی مطرح شده در این فصل نشان می‌دهد که توزیع درجه شبکه‌های واقعی به طور قابل توجه‌ای با توزیع پواسون تفاوت دارد، سوال مهمی ‌را ایجاد می‌کند: چگونه شبکه‌هایی با p_k دلخواه ایجاد کنیم؟ در این قسمت سه الگوریتم که برای این هدف طراحی شده و غالبا استفاده می‌شوند را مطرح می‌کنیم.

مدل پیکربندی

مدل پیکر بندی، که در شکل 4.15 شرح داده شده، به ما کمک می‌کند شبکه‌ای با یک دنباله درجه از پیش تعریف شده بسازیم. در این شبکه هر گره یک درجه از پیش تعریف شده k_i دارد و بقیه کارها همانند شبکه تصادفی دنبال می شود. در واقع یک شبکه تصادفی با دنباله درجه از پیش تعریف شده تولید می‌شود. با چند بار اعمال این روش روی یک دنباله درجه مشخص، می‌توانیم شبکه‌هایی متفاوت با p_k یکسان ایجاد کنیم (شکل 4.15 ب-د). چند نکته وجود دارد که باید در نظر گرفت:

• احتمال وجود پیوند بین دو گره با درجه k_i و k_jبرابر است با: $p_{ij} = \frac{{k_i k_j }}{{2L - 1}} \hspace{20 mm} (4 . 24)$ • روی هر گره چند خار در نظر گرفته می شود (به تعداد درجه گره) که گره از طریق هر یک از آنها می تواند به گره های دیگر متصل شود (شکل 4.15 الف). گره i از طریق خارهایش می تواند به 2L - 1 خار از گره های دیگر وصل شود. از این میان k_j به گره j اختصاص دارد. بنابراین احتمال اینکه یک خار خاص از i به یک خار از گرهj وصل شود k_j /(2L - 1) است. از آنجا که گره i، k_i خار دارد، رابطه 4.24 به دست می آید.
• • شبکه به دست آمده می تواند شامل طوقه و چند-پیوند (چند یال) باشد، زیرا در الگوریتم منعی برای اتصال یک گره به خود، یا ایجاد چند پیوند بین دو گره وجود ندارد. می‌توان در حین ساخت شبکه از انتخاب جفت خار‌هایی که منجر به این مساله می‌شوند، خودداری کرد. اما این موضوع باعث می شود احتمال یکسان انتخاب اتصال بین همه خارها زیر سوال رود و در نتیجه رابطه 4.24 معتبر نخواهد بود و محاسبات تحلیلی دشوار خواهد شد. در عمل از آنجا که به دلیل وجود انتخاب های متعدد برای N های بزرگ، تعداد طوقه‌ها و چند-پیوندها ناچیز می شود، معمولا می توان از آن صرف نظر کرد [42].
• غالبا در محاسبات از مدل پیکربندی استفاده می‌شود، زیرا رابطه 4.24 و مشخصات تصادفی ذاتی آن به ما کمک می‌کند که بسیاری از معیارهای شبکه را به صورت تحلیلی محاسبه کنیم.

بازآرایی تصادفی شبکه با حفظ درجه

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

مدل پارامتر پنهان

در تولید شبکه با روش مدل پیکربندی، ممکن است طوقه و چند-پیوندی ایجاد شود، در حالی که این ویژگی‌ها در بسیاری از شبکه‌های واقعی به چشم نمی خورد. برای ایجاد شبکه‌ها با یک p_k از پیش تعریف شده بدون چند-پیوند و طوقه می‌توان از مدل پارامتر پنهان (شکل 4.18) استفاده کرد [44, 45, 46].

ابتدا از N گره مجزا شروع می‌کنیم و به هر گره i، یک پارامتر پنهان η_i که از توزیع ρ(η) انتخاب شده است، اختصاص می‌دهیم. ماهیت شبکه ایجاد شده به دنباله پارامتر پنهان {η_i} انتخاب شده بستگی دارد. دو روش برای ایجاد پارامترهای پنهان مناسب وجود دارد:

• η_i می‌تواند دنباله‌ای از N عدد تصادفی انتخاب شده از یک توزیع از پیش تعریف شده ρ(η) باشد. توزیع درجه شبکه به دست آمده به صورت زیر است: $p_k = \int {\frac{{e^{ - \eta } \eta ^k }}{{k!}}} \rho (\eta )d\eta \hspace{20 mm} (4 . 26)$
• η_i می‌تواند از یک دنباله قطعی {η₁, η₂, ..., η_N} حاصل شود. در اینصورت توزیع درجه شبکه به دست آمده به صورت زیر است: $p_k = \frac{1}{N}\sum\limits_j {\frac{{e^{ - \eta _j } \eta _j ^k }}{{k!}}} \hspace{20 mm} (4 . 27)$

مدل پارامتر پنهان روشی بسیار ساده برای ایجاد شبکه¬های بی‌مقیاس ارائه می‌دهد. در واقع، با استفاده از

به عنوان دنباله‌ای از پارامترهای پنهان، با توجه به رابطه (4.27) و برای K بزرگ، شبکه به دست آمده توزیع درجه زیر را خواهد داشت:

به عنوان دنباله‌ای از پارامترهای پنهان، با توجه به رابطه (4.27) و برای K بزرگ، شبکه به دست آمده توزیع درجه زیر را خواهد داشت:

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

• الگوریتم‌ها به ما نمی‌گویند چرا یک شبکه توزیع درجه مشخصی دارد. دانستن منشا pk مشاهده شده در یک شبکه خاص، موضوع فصل‌های 6 و 7 خواهد بود.
• و چندین خصوصیت مهم شبکه، از خوشه‌بندی (فصل 9) گرفته تا همبستگی درجه (فصل 7)، در طول تصادفی سازی از بین می‌روند.

شبکه‌های ایجاد شده به وسیله این الگوریتم‌ها شبیه به یک عکس از نقاشی هستند: در نگاه اول، به نظر می‌رسد این شبکه ها مشابه شبکه اصلی هستند، اما با بررسی دقیق‌تر، درمی‌یابیم که بسیاری از جزئیات، از بافت بوم نقاشی گرفته تا ضربات قلم‌ مو از بین رفته‌اند.

سه الگوریتمی که معرفی شد، این پرسش را مطرح می‌کند که چگونه می‌توانیم تصمیم بگیریم از کدام الگوریتم استفاده کنیم؟ انتخاب به این بستگی دارد که از یک دنباله درجه {ki} یا یک توزیع درجه pk شروع می‌کنیم. همچنین، اینکه وجود طوقه و چند پیوندی بین گره‌ها پذیرفتنی است؟ درخت تصمیم شامل این انتخاب در Image 4.20. ارائه شده است.

بخش 4.9
جمع بندی

خصوصیات بی‌مقیاس به دو دلیل اصلی نقش مهمی در توسعه علم شبکه دارد:

• بسیاری از شبکه‌های واقعی، از وب گرفته تا شبکه‌های درون سلولی، بی‌مقیاس هستند. این جامعیت باعث می‌شود که خاصیت بی‌مقیاس در بسیاری از رشته‌ها به چشم بخورد.
• هاب‌ها از زمانی که شناسایی شدند، رفتار سیستم را دستخوش تغییر کرده¬اند. خاصیت فوق العاده-کوچک اولین نمونه از تاثیر آن‌ها بر خصوصیات شبکه است. در فصل‌های آینده با نمونه‌های بیشتری مواجه خواهیم شد.

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

شبکه‌های محدود به نمایی

یک شبکه را نمایی-محدود می‌نامیم اگر توزیع درجه آن برایk های بزرگ به شکل نمایی یا سریع‌تر کاهش یابد. در نتیجه ‹k²› کوچک‌تر از ‹k› خواهد شد، به عبارتی درجه گره ها (p_k ) تفاوت زیادی نخواهد داشت. توزیع پواسون، گاوسی و نمایی ساده (جدول 4.2) نمونه‌هایی از این دسته هستند. شبکه‌های اردوش-رنی و واتس-استروگاتز معروف‌ترین مدل‌های شبکه در این گروه هستند. شبکه‌های محدود شده به نمایی، فاقد گره هایی با درجه خیلی پرت (متفاوت) هستند و درجه اکثر گره‌ها نزدیک به هم است. نمونه شبکه‌های واقعی در این دسته شامل شبکه‌های بزرگراهی و توزیع برق هستند.

شبکه‌های پهن-دنباله

یک شبکه پهن-دنباله است اگر توزیع درجه آن در ناحیه‌ k های بزرگ شبیه دنباله قانون توان باشد، در نتیجه ‹k²› بسیار بزرگ‌تر از ‹k› می شود، که منجر به تفاوت درجه قابل توجه‌ای بین گره ها می‌شود. شبکه‌های بی‌مقیاس با توزیع درجه قانون توان (رابطه 4.1) معروف‌ترین نمونه از این شبکه‌ها به شمار می آیند. وجود گره هایی با درجه پرت (درجه بیشتر از نمایی)، نه تنها در این شبکه ها مجاز است بلکه کاملا طبیعی نیز هست. شبکه‌ وب، اینترنت، شبکه‌ برهم کنش پروتئین و اکثر شبکه‌های اجتماعی و آنلاین در این گروه قرار می گیرند.

اگرچه برای تشخیص نوع یک شبکه باید توزیع درجه آن با تکنیک های آماری تعیین شود، اما در عمل، در بسیاری از مواقع کافی است مشخص شود که شبکه از نوع محدود به نمایی است یا پهن دنباله (مباحث پیشرفته 4.الف را ببینید). اگر توزیع درجه به تابع نمایی محدود باشد، مدل شبکه تصادفی حدس معقولی برای تشخیص توپولوژی آن خواهد بود و اگر توزیع درجه از نوع پهن-دنباله باشد، احتمالا با یک شبکه بی‌مقیاس مواجهیم. در فصل‌های آتی خواهیم دید که نشانه کلیدی رفتار پهن-دنباله بزرگ‌نمایی 〈k²〉 است: اگر 〈k²〉 نسبت به متوسط درجه شبکه خیلی بزرگ تر باشد (چند برابر)، رفتار سیستم‌ها شبیه شبکه‌های بی‌مقیاس است، و اگر 〈k²〉 کوچک باشد، یعنی به 〈k〉(〈t〉+1) نزدیک باشد، سیستم‌ شبیه شبکه تصادفی خواهد بود.

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

بخش 4.10
تمرین

1. هاب‌ها

   حداکثر درجه مورد انتظار k_max را برای شبکه‌های بدون جهت ذکر شده در جدول 4.1 بیابید. .

2. تناقض (پارادوکس) دوستی

   توزیع درجه p_k احتمال اینکه یک گره دلخواه (تصادفی) دارایk همسایه باشد را تعیین می‌کند. اگر پیوندی را به شکل تصادفی انتخاب کنیم، احتمال اینکه یک گره در یک سر آن درجه k داشته باشد q_k = Akp_k است که A ضریب نرمال سازی است.

   1. ضریب نرمال¬سازی A را پیدا کنید، فرض کنید که شبکه دارای یک توزیع درجه قانون توان با 2 < γ < 3 ، با کمترین درجه k_min و بیشترین درجه k_max است
   2. علاوه بر این در مدل پیکربندی q_k برابر است با احتمال اینکه یک گره دلخواه دارای همسایه‌ای با درجهk باشد. میانگین درجه همسایه‌های یک گره دلخواه (تصادفی) چیست؟
   3. میانگین درجه همسایه‌های یک گره دلخواه (تصادفی) را در شبکه‌ای با N = 10⁴ ، γ= 2.3، k_min= 1 و k_max= 1, 000 محاسبه کنید.
   4. چگونه می‌توانید تناقض (ج)، که دوستان یک گره دوستان بیشتری نسبت به خود گره دارند را توجیه کنید؟

3. تولید شبکه‌های بی‌مقیاس

   برنامه کامپیوتری بنویسید که شبکه‌هایی با اندازه N و یک توزیع درجه‌ قانون توان با توان درجه γ ایجاد ‌کند. برای این رویه به بخش 4.9 مراجعه کنید. سه شبکه با γ = 2.2 و به ترتیب با N = 10³ ، N = 10⁴ و N = 10⁵ گره ایجاد کنید. درصد چند-پیوند و طوقه در هر شبکه چقدر است؟ شبکه‌های بیشتری تولید کنید و نموداری از این نسبت ها (درصدها) به عنوان تابعی از N رسم کنید. همین کار را برای شبکه‌هایی با γ = 3 نیز تکرار کنید.

4. تسلط بر توزیع

   با استفاده از یک نرم‌افزار مناسب برای کارهای آماری، مانند متلب، Mathematica یا Numpy در پایتون، سه مجموعه داده مصنوعی، هر یک شامل 10000 عدد صحیح تولید کنید که از توزیع قانون توان با توان های γ = 2.2 ، γ = 2.5 و γ = 3 پیروی ‌کنند. مقدار k_min = 1 در نظر بگیرید. از تکنیک‌های شرح داده شده در مباحث پیشرفته 4.ج برای برازش این سه توزیع استفاده نمایید

بخش 4.11
مباحث پیشرفته 4.الف
قوانین توان

قانون توان تاریخچه زیادی در طبیعت و علوم اجتماعی دارد و با اسامی مختلفی که گاهی چندان دقیق نبوده است مانند توزیع پهن-دنباله ، دنباله سنگین ، دنباله-بلند (دم بلند)، پرتو یا بردفید نامیده شده است. موارد دیگری نظیر توزیع نرمال لگاریتمی ، Weibull یا Lévy نیز به آن مشابه است. در این بخش برخی از توزیع‌های متداول در علم شبکه و رابطه آن با قانون توان را بررسی می‌کنیم.

توزیع‌های نمایی-محدود

وقایع زیادی در طبیعت، از قد انسان‌ها گرفته تا احتمال وقوع تصادف رانندگی، از توزیع‌های محدود شده به نمایی پیروی می‌کنند. خاصیت مشترک این‌ موارد این است کهp_x یا به صورت نمایی (e^-x) یا سریع‌تر از صورت نمایی(e^-x2/σ2) برای x های بزرگ کاهش می‌یابد. در نتیجه بزرگ‌ترین x مورد انتظار به یک مقدارx_max که اختلاف زیادی با ⟨x⟩ ندارند محدود خواهد بود. در واقع، چنانچه N عدد از یکp_x محدود شده به نمایی برداریم، بزرگ‌ترین x مورد انتظار حداکثر به اندازهx_max ~ logN خواهد بود. به این معنی که احتمال ایجاد داده‌ پرت (گره ای با درجه خیلی زیاد) ناچیز است و در عمل هاب ها مجال بروز پیدا نمی کنند و اکثر رخ‌ داد‌های حاصل ازچنین توزیعی در نزدیکی و مجاورت ⟨x⟩ قرار می گیرند.

اصطلاحا به ناحیه x های بزرگ، دنباله یک توزیع گفته می شود. با توجه به عدم امکان رخ دادهای فراوان در دنباله این توزیع، به آن توزیع دنباله ضعیف (دم کوتاه) نیز گفته ممی شود.

از نظر تحلیلی، ساده‌ترین توزیع محدود شده، توزیع نمایی e^-λx است. توزیع محدود-نمایی که در علم شبکه متداول تر است، توزیع پواسون (یا پدر آن، توزیع دوجمله‌ای ) است که توزیع درجه یک شبکه تصادفی را توصیف می‌کند. توزیعی که در خارج از علم شبکه متداول تر است، توزیع نرمال (گاوسی) است (جدول 4.2).

توزیع پهن-دنباله

اصطلاحات پهن-دنباله، دنباله سنگین یا دنباله کشیده به p_x اشاره دارد که روند کاهشی آن در x های بزرگ کندتر از حالت نمایی است. در این توزیع‌ها ما اغلب با رویدادهایی مواجه هستم که دارای مقادیر x بسیار بزرگ یا همان رخدادهای نادر و داده های پرت هستند. توزیع قانون توان (رابطه 4.1) بهترین نمونه شناخته شده از یک توزیع پهن-دنباله است. یکی از ویژگی¬های بارز این توزیع این است که بزرگی مقادیر x حاصل از آن می‌تواند چندین مرتبه با هم تفاوت داشته باشد. در واقع در این خانواده از توزیع‌ها، اندازه بزرگ‌ترین رخداد پس از N بار آزمایش با x_max ~ N^ζ متناسب است، که ζ با توان γ که دنباله توزیع p_x را توصیف می‌کند، مشخص می‌شود. با رشد سریع N^ζ ، رخدادهای نادر یا داده‌های پرت با تواتر قابل توجه‌ای رخ می‌دهند و بر اکثر ویژگی های سیستم تاثیر می گذارند.

رابطه توزیع‌های پهن-دنباله با شبکه‌ها توسط چندین عامل تعیین می‌شود:

• کمیت‌های زیادی مانند درجه، وزن‌های پیوند و مرکزیت میانی در علم شبکه وجود دارند، که هم در شبکه‌های واقعی و هم شبکه های مصنوعی (مدل) از توزیع قانون توان پیروی می‌کنند.
• قالب قانون توان توسط مدل‌های مناسب شبکه، به شکل تحلیلی پیش‌بینی می‌شود (فصل 5).

توزیع متقاطع ( لگاریتمی-نرمال ، نمایی کشیده شده)

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

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

که x > 0 و γ > 0 و Γ(s,y) تابع گاما ناکامل بالا را نشان می‌دهد. رابطه تحلیلی 4.30 بلافاصه ماهیت این توزیع را نشان می دهد: جمله قانون توان، عمل اصلی به وجود آمدن دنباله پهن است و جمله نمایی عامل اصلی محدود شدن دنباله توزیع به تابع نمایی است. برای برجسته کردن خصوصیت برش نمایی آن از رابطه 4.30 لگاریتم می گیریم:

برای x ≪ 1/λ دومین جمله سمت راست غالب است، نشان می‌دهد که توزیع از قانون توان با توان γ پیروی می‌کند. زمانی که x ≫ 1/λ ، عبارت λx بر عبارت ln x غالب می شود که باعث شکل گیری یک برش نمایی برای x های بزرگ می‌شود.

نمایی کشیده ( توزیع Weibull) رسما شبیه به رابطه4.30 است با این تفاوت که توان جمله قانون توان، کسری (کوچک) است. نامگذاری آن به این دلیل بوده که تابع توزیع تجمعی آن برابر با یک منهای تابع توان کشیده شده P(x) = e^-(λx)β (4.32) است که منجر به (ایجاد) تابع چگالی زیر می‌شود:

در بسیاری از کاربردها x بین 0 و +∞ متغیر است. در رابطه4.32، β توان کشیدگی است، که مشخصات p(x) را تعیین می‌کند:

• برای β=1 به تابع نمایی ساده تبدیل می شود.
• اگر β بین 0 و 1 باشد نمودار حاصل از log p(x) براساس x ،کش می آید ، به این معنی که چندین مرتبه از بزرگ نمایی x را در برمی‌گیرد. در این حالت، تمیز دادن توزیع نمایی کشیده از قانون توان خالص دشوار است. هر چه β به صفر نزدیک‌تر باشد، p(x) به قانون توان x-1 شبیه‌تر خواهد بود.
• اگر β > 1 باشد، یک تابع نمایی "فشرده شده " داریم، به این معنی که دامنه تغییرات x بسیار محدود و باریک خواهد بود.
• برایβ = 2 ، رابطه 4.33 به توزیع رایلی تبدیل می شود.

همانطور که در فصل 5 و 6 خواهیم دید، چندین مدل از شبکه ها، توزیع درجه نمایی کشیده را نشان می دهند.

یک توزیع لگاریتمی-نرمال (توزیع Galton یا Gibrat) وقتی پدید می آید که ln x از توزیع نرمال پیروی کند. معمولا متغیری از یک توزیع لگاریتمی-نرمال پیروی می‌کند که حاصل ضرب تعداد زیادی عدد تصادفی مثبت مستقل باشد. در مباحث مالی برای نشان دادن بازده مرکب دنباله‌ای از معاملات از این توزیع استفاده می شود.

تابع چگالی احتمال توزیع لگاریتمی- نرمال برابر است با:

از این رو تابع لگاریتمی- نرمال شبیه توزیع نرمال است با این تفاوت که جمله x در صورت کسر با ln x جایگزین می شود.

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

دامنه تغییرات در مرتبه x را نشان می‌دهد. بنابراین اکنون که ln x توزیع نرمال دارد، به این معنی است که x می‌تواند بسیار گسترده باشد. بسته به مقدار σ توزیع لگاریتمی-نرمال ممکن است شبیه به توزیع قانون توان با چند مرتبه بزرگ‌نمایی باشد. این موضوع در جدول 4.2 نیز نشان داده شده است، 〈x²〉 به شکل نمایی با σ رشد می‌کند، از این رو می‌تواند بسیار بزرگ شود.

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

بخش 4.12
مباحث پیشرفته 4.ب
رسم نمودار قانون توان

رسم نمودار توزیع درجه، بخش جدایی ناپذیر تجزیه و تحلیل یک شبکه است. فرآیند با بدست آوردن N_k یعنی تعداد گره ها با درجه k شروع می‌شود. این کار می‌تواند از طریق شمارش مستقیم یا به وسیله یک مدل انجام شود. برای هر N_k ، p_k = N_k /N را محاسبه می‌کنیم. پرسش این است که چگونه p_k رسم شود که ویژگی های آن به بهترین شکل نمایان گردد.

استفاده از یک نمودار لگاریتم-لگاریتم

در شبکه¬های بی‌مقیاس تعداد زیادی گره‌ با یک یا دو پیوند در کنار تعداد کمی هاب با هزاران یا حتی میلیون‌ها پیوند وجود دارند. استفاده از محور افقی خطی برای K باعث می شود گره‌های زیادی با درجه کم در یک ناحیه کوچک (مقادیر کم K ) تجمیع و فشرده شوند و در نتیجه به خوبی در نمودار دیده نشوند. همچنین از آنجا که مقدار p_k تفاوت زیادی برای k = 1 و k های بزرگ خواهد داشت، اگر آن را روی محور عمودی خطی رسم کنیم، مقدار آن‌ برای k بزرگ صفر به نظر می‌رسد (شکل 4.22 الف) و دیده نمی شود. استفاده از نمودار لگاریتم-لگاریتم از بروز این مشکل جلوگیری می‌کند. می‌توانیم یا از محور لگاریتمی، با توان 10 استفاده کنیم (در کل این کتاب مورد استفاده قرار گرفته است شکل 4.22ب)، یا log pk را به عنوان تابعی از log k رسم کنیم (اگرچه این روش هم درست است، اما تفسیر نمودار دشوارتر است). توجه داشته باشید که در نمودار لگاریتم-لگاریتم نقاط با p_k =0 یا k=0 به دلیل اینکه log 0=-∞ نشان داده نمی‌شوند.

عدم استفاده از تظریف خطی

یکی از روش های رایج و در عین حال ناکارآمد، ترسیم ساده p_k = N_k/N روی یک نمودار لگاریتمی-لگاریتمی است. این روش تظریف خطی نامیده می‌شود، زیرا همه ظرف ها (سطل) اندازه برابر و مساوی Δk = 1 دارد. برای شبکه‌ای بی‌مقیاس روش تظریف خطی باعث ایجاد خط تراز در مقادیر بزگر k می شود. منظور از خط تراز، قرارگرفتن نقاط داده متعدد در یک خط افقی است (شکل 4.22 ب). دلیل به وجود آمدن این خط ساده است، از آنجا که در درجه های بالا معمولا حداکثر فقط یک گره از هر درجه داریم، از این رو در ناحیه K-بزرگ یا خواهیم داشت N_k=0 (گره با درجه k وجود ندارد) یا N_k=1 (فقط یک گره با درجه k وجود دارد). در نتیجه در تظریف خطی یا pk=0 می شود که در نمودار لگاریتمی-لگاریتمی اصلا نشان داده نمی‌شود، یا p_k = 1/N، می شود که برای همه هاب‌ها یکسان است و باعث ایجاد یک خط تراز می شود.

ظهور خط تراز، اجازه نمی دهد که توان درجه γ به درستی تعیین شود. برای مثال، اگر سعی کنیم قانون توان را برای داد‌ه‌های نشان داده شده در شکل 4.22ب با استفاده از تظریف خطی برازش کنیم، γ به دست آمده کاملا متفاوت از مقدار واقعی γ=2.5 می شود. دلیل این امر این است که در تظریف خطی تعداد زیادی گره در سطل هایی با اندازه کوچک k و تعداد کمی نقطه در سطل هایی با اندازه بزرگ k قرار می گیرند. بنابراین p_k در قسمت هایی با اندازه کوچک k به خوبی برازش می شود ولی از آنجا که تعداد کمی نقطه در نواحی با k بزرگ داریم که آن هم تحت تاثیر خط تراز قرار می گیرد، عملا برازش در آن ناحیه به درستی انجام نمی شود و تحت تاثیر خط تراز قرار می گیرد. در صورتی که همین ناحیه(مقادیر بزرگ k) نقش کلیدی در تعیین γ دارد. افزایش اندازه سطل ها (بخش‌) نیز این مسئله را حل نخواهد کرد. بنابراین توصیه می‌شود از تظریف خطی برای توزیع‌های پهن-دنباله استفاده نشود.

استفاده از تظریف لگاریتمی

تظریف لگاریتمی نمونه‌گیری غیر یکنواخت تظریف خطی را اصلاح می‌کند. برای تظریف لگاریتمی اجازه می‌دهیم اندازه سطلها با درجه افزایش یابد، به این ترتیب تعداد نقاط سطل های مختلف تقریبا نزدیک به هم خواهد بود. برای مثال، می‌توانیم اندازه سطل را حاصل ضرب های 2 انتخاب کنیم، به اولین سطل اندازه b₀=1 اختصاص می دهیم که شامل همه گره‌ها با k=1 می شود. دومین سطل، اندازه b₁=2 خواهد داشت و شامل گره‌های با درجه k=2, 3 می شود. سومین سطل اندازه b₂=4 داشته و شامل گره‌هایی با درجات k=4, 5, 6, 7 می شود. به همین ترتیب به شیوه استقرایی، n-امین سطل اندازه 2^n-1 خواهد داشت و شامل همه گره‌ها با درجه k=2^n-1, 2^n-1+1, ..., 2^n-1-1 است. توجه داشته باشید که اندازه سطل می‌تواند به اندازه دلخواه b_n = cⁿ که c > 1 باشد، افزایش یابد. توزیع درجه با p(k_n)=N_n/b_n مشخص می‌شود، که N_n تعداد گره‌های سطل n با اندازه b_n است و (k_n) میانگین درجه گره‌ها در سطل b_n است.

نمودار تظریف زده شده به شکل لگاریتمی در شکل 4.22 ج نمایش داده شده است. توجه داشته باشید که اکنون نمودار به بخش خط تراز با k بزرگ گسترش یافته است، که در تظریف خطی پیدا بود. بنابراین تظریف لگاریتمی اطلاعات مفیدی را برای گره‌های کمیاب با درجه بالا نیز استخراج می‌کند (نکته 4.10).

استفاده از توزیع تجمعی

روش چهارم برای استخراج اطلاعات از دنباله p_k رسم نمودار توزیع تجمعی مکمل به صورت زیر است:

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

توزیع تجمعی هم بخش خط تراز که در روش تظریف خطی پدیدار می شد را حذف می‌کند و نمودار را تا مقادیر بزرگ درجه پیش می برد (شکل 4.22 د) و امکان یک تخمین دقیق‌ از توان درجه را فراهم می‌کند.

بخش 4.13
مباحث پیشرفته 4.ج
برآورد توان (نمای) درجه

از آنجایی که خصوصیات شبکه‌های بی‌مقیاس وابسته به توان درجه (بخش 4.7) است، باید مقدار γ را تعیین کنیم. اما، زمانی که سعی می‌کنیم قانون توان را به داده‌های حقیقی برازش کنیم، با چندین مشکل روبرو هستیم. مهم‌ترین مساله این است که اعداد در کل دامنه با توزیع درجه تطبیق ندارند و همانگونه که در (نکته 4.10) اشاره شد، با برش هایی در درجات خیلی کوچک و خیلی بزرگ مواجه هستیم که آنها را در این بخش با K_min و K_max مشخص می کنیم. در فاصله بین این دو نقطه، نمودار به خوبی با توزیع درجه تطبیق پیدا میکند. دقت کنید که K_min و K_max با K_min و K_max (کوچک‌ترین و بزرگ‌ترین درجه در یک شبکه) متفاوت هستند و در واقع متناظر با k_sat و k_cut که در نکته 4.10 مطرح شد هستند. در این‌جا روی تخمین زدن نقطه برش درجات کوچک یا همان K_min تمرکز می‌کنیم. پیدا کردن برش درجات بالا نیز به شیوه مشابه قابل انجام خواهد بود. پیش از استفاده از این روش، مباحث مربوط به مشکلات سیستماتیک آن را که در انتهای این بخش ارائه شده است، مطالعه فرمایید.

فرآیند برازش

از آنجا که معمولا توزیع درجه به صورت فهرستی از اعداد صحیح مثبت k_min , ..., k_max ارئه می‌شود، بر تخمین γاز مجموعه‌ گسسته‌ای از نقاط داده تمرکز می کنیم [47]. برای نشان دادن شیوه کار از شبکه ارجاعات (استنادات) علمی استفاده می‌کنیم. این شبکه شامل N=384,362 گره است و هر گره یک مقاله پژوهشی را نشان می‌دهد که بین سال‌های 1890 و 2009 در مجلات منتشر شده توسط انجمن فیزیک آمریکا منتشر شده اند. این شبکه L = 2,353,984 پیوند دارد، که هر کدام یک استناد از مقاله پژوهشی منتشر شده به برخی از نشریات دیگر در همان پایگاه داده را نشان می‌دهد (استنادهای خارج از آن نادیده گرفته شده‌اند). این مجموعه داده با آنچه در Table 4.1 ذکر شده است، متفاوت است. برای توصیف کامل این داده‌ها به [48] مراجعه کنید. مراحل فرآیند برازش عبارتند از [47]:

1. یک مقدار K_minبین K_minو k_maxانتخاب کنید. مقدار توان درجه متناظر با این K_min را با استفاده از عبارت زیر تخمین بزنید: $\gamma = 1 + N\left[ {\sum\limits_{i = 1}^N {\ln \frac{{k_i }}{{K_{\min } - \frac{1}{2}}}} } \right]^{ - 1} \hspace{20 mm} (4 . 41)$
2. با جفت پارامتر (γ, K_min) بدست آمده، فرض می کنیم که توزیع درجه به صورت زیر باشد: $p_k = \frac{1}{{\zeta (\gamma ,K_{\min } )}}k^{ - \gamma } \hspace{20 mm} (4 . 42)$ از این رو تابع توزیع تجمعی CDF به صورت زیر خواهد بود: $P_k = 1 - \frac{{\zeta (\gamma ,k)}}{{\zeta (\gamma ,K_{\min } )}} \hspace{20 mm} (4 . 43)$
3. 3. برای تعیین حداکثر فاصله D بین تابع توزیع تجمعی داده¬های واقعی S(k) و مدل برازش شده (با جفت پارامتر‌های (γ, K_min) با رابطه 4.43) از آزمون Kormogorov-Smirnov استفاده کنید: $D = \max _{k \ge K_{\min } } \left| {S(k) - P_k } \right| \hspace{20 mm} (4 . 44)$
4. مراحل 1 تا 3 را به ازای تمام مقادیر K_minاز بازه K_minتا k_maxتکرار کنید تا مشخص شود به ازای چه مقداری از K_minاندازه فاصله D که با رابطه 4.44 به دست می آید، کمینه می شود. برای نشان دادن این روال، K_minرا به صورت تابعی از D برای شبکه ارجاعات علمی رسم می‌کنیم (شکل 4.24 ب). این نمودار نشان می‌دهد که D به ازای K_min= 49 کمینه است و γ متناظر با آن به کمک رابطه 4.41، γ=2.79 است که بهترین برازش را نتیجه می دهد. خطای استاندارد برای توان درجه بدست آمده برابر است با: $\sigma _\gamma = \frac{1}{{\sqrt {N\left[ {\frac{{\zeta ''(\gamma ,K_{\min )} }}{{\zeta (\gamma ,K_{\min )} }} - \left( {\frac{{\zeta ''(\gamma ,K_{\min )} }}{{\zeta (\gamma ,K_{\min )} }}} \right)^2 } \right]} }} \hspace{20 mm} (4 . 45)$ بهترین برازش به ازای مقادیر توان γ ±σ_γ به دست می آید. برای شبکه ارجاعات علمی مقدار σ_γ=0.003 محاسبه می شود، در نتیجه γ=2.79±0.003 خواهد بود.

توجه داشته باشید که برای تخمینγ در مجموعه داده هایی با اندازه کوچک‌تر از N=50 ، باید با احتیاط عمل شود.

نکویی برازش

تنها یافتن جفت (γ, K_min) که بتواند برازش بهینه‌ای برای مجموعه داده ما نشان ‌دهد، کفایت نمی کند، بلکه باید بررسی شود که خود توزیع قانون توان، یک مدل مناسب برای توزیع مورد مطالعه باشد. بنابراین باید از آزمون نکویی برازش استفاده کنیم، که به کمک یک مقدار کمی p، قابل قبول بودن فرضیه قانون توان را نشان می دهد. مراحل روش متداول برای این منظور عبارتند از:

1. رای تخمین فاصله بین داده‌های واقعی و بهترین برازش، از توزیع تجمعی رابطه 4.43 استفاده می کنیم. این همان مرحله سوم الگریتم بالا است، مقدار D را برای K_min که بهترین برازش را برای داده‌ها ارائه می دهد محاسبه می کنیم و آن را D^real می نامیم. برای داده‌های ارجاعات علمی به ازای K_min=49 مقدار D^real = 0.01158 بدست می آید (شکل 4.24 ج).
2. از رابطه (4.42) برای ایجاد دنباله ای از N درجه استفاده می کنیم. به این ترتیب یک دنباله مصنوعی از درجات ایجاد می کنیم که تعداد آن دقیقا با همان دنباله اصلی برابر است. فاصله بین دنباله درجه‌ مصنوعی که دقیقا با همان مشخصات توزیع اصلی ایجاد شده، و داده‌های واقعی را D^synthetic می نامیم.
3. هدف این است که ببینیم آیا D^syntheticبدست آمده به D^realنزدیک است. برای این منظور، مرحله (2) را M بار (M ≫ 1) تکرار می‌کنیم و هر دفعه دنباله درجه جدیدی را ایجاد می‌کنیم و D^synthetic مطابق با آن را محاسبه می‌کنیم، در نهایت توزیع p(D^synthetic) را بدست می‌آوریم و نمودار آن را رسم می کنیم. D^realرا به شکل نوار عمودی نشان می‌دهیم (شکل 4.24 ج). اگر D^real در محدوده توزیع p(D^synthetic) باشد، بدین معنی است که فاصله بین مدل برگرفته از بهترین برازش و داده‌های تجربی با فاصله مورد انتظار از نمونه‌های تصادفی ساخته شده از مدل بهترین برازش قابل مقایسه است. از این رو قانون توان یک مدل معقول برای داده‌ها است. اما، اگر D^realخارج از توزیع p(D^synthetic) قرار بگیرد، آنگاه قانون توان مدل خوبی نیست و انتظار می رود توابع دیگری برای توصیف کردن p_k مناسب تر باشند.

هرچند نمایش تصویری توزیع مشابه شکل 4.24 ج در برخی اوقات می تواند برای نشان دادن صحت آماری برازش مفید باشد، اما در حالت کلی بهتر است نکویی برازش به صورت کمی و در قالب یک عدد p سنجش شود:

چنانچهp به 1 نزدیک‌ باشد، می توان استنباط نمود که تفاوت بین داده‌های واقعی و مدل تنها به دلیل نوسانات آماری باشد. اگر p بسیار کوچک باشد، مدل برازش برای داده‌ها مورد قبول نیست.

معمولا اگر p > 1% باشد، مدل مورد قبول خواهد بود. برای شبکه ارجاعات علمی، مقدار p < 10-4 به دست می آید که نشان می‌دهد قانون توان خالص مدل مناسبی برای آن نیست. این نتیجه از این جهت جالب است که در مقالات متعددی از دهه 1960 تصور می شد که این شبکه از توزیع قانون توان پیروی می کند [7,8]. این مثال نشان می دهد که نمی توان به صورت کورورانه و بدون درک تحلیلی از توزیع یک شبکه، آن را به توزیع قانون توان برازش کرد.

برازش توزیع‌های واقعی

مدل برازش (4.44) تمام نقاط داده با k < K_min را نادید می‌گیرد. با توجه به اینکه شبکه ارجاعات علمی پهن-دنباله است، انتخاب K_min= 49 باعث می شود که ما بیش از 96% از داده ها را از دست بدهیم، در حالی که اطلاعات آماری مفیدی در فاصله k < K_min وجود دارد که در برازش قبلی (قانون توان) نادیده گرفته شده‌اند. بنابراین برای رفع این مشکل باید از یک مدل جایگزین استفاده نماییم.

همان‌گونه که در نکته 4.10 مطرح شد، توزیع درجه بسیاری از شبکه‌های واقعی، مانند شبکه ارجاعات علمی، از قانون توان خالص پیروی نمی‌کند. معمولا اشباع درجات پایین و برش درجات بالا به چشم می خورد که با رابطه زیر بیان می شود:

و تابع توزیع تجمعی متناظر برابر است (با)

که k_satو k_cut به ترتیب نقاط اشباع درجات پایین و برش درجات بزرگ هستند. تفاوت بین این فرآیند جدید و رابطه 4.47 این است که اکنون نقاطی که از قانون توان خالص فاصله دارند را نادیده نمی‌گیریم، در عوض از تابعی استفاده می‌کنیم که برازش بهتری را برای کل توزیع درجه از k_min تا k_max پیشنهاد ‌دهد.

هدف ما یافتن پارامترهای مناسب k_sat، k_cut و γ مدل (4.47) است، که از طریق مراحل زیر به آن دست پیدا می کنیم(شکل 4.25):

1. برای k_satو k_cutمقداری را بین K_minو K_max انتخاب کنید. مقدار توان درجه γ را با استفاده از روش کاهشی سریع که تابع لگاریتمی-درست‌نمایی را حداکثر می‌سازد، تقریب می زنیم $\log L(\gamma |k_{sat} ,k_{cut} ) = \sum\limits_{i = 1}^N {\log p(k_i |\gamma ,k_{sat} ,k_{cut} )}$ به این معنا که، به ازای (k_sat, k_cut) ثابت γ را آن قدر تغییر می‌دهیم تا به مقدار بیشینه رابطه 4.49 دست پیدا کنیم.
2. پس از به دست آوردن γ(k_sat, k_cut)، فرض می کنیم که توزیع درجه به صورت رابطه 4.47 باشد. به کمک آزمون Kormogorov Smirnov پارامتر D را بین تابع توزیع تجمعی درجه داده‌های اصلی و مدل برازش شده با رابطه 4.47 محاسبه می کنیم.
3. k_satو k_cutرا ازk_min=0 تاk_max وk_cut از k_min= k0 ببینیم به ازای چه مقداری از k_satوk_cut مقدار D کمینه می شود. نمودار D به صورت تابعی ازk_sat برای مقادیر مختلف k_cutدر شکل 4.25 الف برای شبکه ارجاعات علمی رسم شده است. برای (k_sat, k_cut) که D برای آن‌ها D کمینه است، مقدارγ متناظر با رابطه 4.41 تعیین می‌شود. به این ترتیب پارامترهای بهینه برازش به دست خواهند آمد. برای مجموعه داده ارجاعات علمی، برازش بهینه به ازای k_sat= 12، k_cut= 5,691، و توان درجه γ= 3.028 به دست می آید. حالا D برای داده‌های واقعی داخل توزیعp(D) قرار می گیرد (شکل 4-25 ج) و مقدار p مربوط به آن 69% است.

مشکلات سیستماتیک برازش

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

1. قانون توان خالص یک توزیع ایده‌آل است که فقط در مدل‌های ساده به صورت رابطه 4.1 نمایان می‌شود (فصل 5). در واقعیت، طیف گسترده‌ای از فرآیندها در توپولوژی شبکه‌های واقعی نقش بازی می کنند و بر شکل دقیق توزیع درجه تاثیر می‌گذارند. این فرآیندها در فصل 6 مطرح خواهند شد. اگر p_k از قانون توان خالص پیروی نکند، روش‌هایی که در این فصل برای برازش قانون توان ارائه شد، نمی تواند به طور قطعی در تشخیص اینکه یک توزیع به لحاظ آماری معنی دار است مورد استفاده قرار گیرد. اگرچه یافته ها ممکن است نشان دهند که یک شبکه بی‌مقیاس نیست، اما معمولا شناخت دقیقی از توزیع دقیق درجه وجود ندارد. در نتیجه ممکن است تابع نادرستی برای p_k متناسب با مجموعه داده براورد شود.
2. ابزار‌های آماری که برای بررسی نکویی برازش معرفی شد، عمدتا مبتنی بر روش Kolmogorov-Smirnov هستند که حداکثر فاصله بین مدل برازش شده و مجموعه داده واقعی را اندازه‌ می¬گیرد. اگر همه نقاط داده کاملا با قانون توان خالص تطبیق پیدا کنند و تنها یک نقطه به هر دلیلی از منحنی انحراف داشته باشد، برازش به لحاظ آماری معنی داری خود را از دست خواهد داد. در سیستم‌های واقعی به دلایل بی‌شمار، چنین انحراف‌های محلی رخ می دهد که تاثیر کمی روی رفتار کلی سیستم دارند. از طرفی حذف این "داده‌های پرت" می‌تواند دست‌کاری داده‌ها تلقی شود و مجاز نیست و از طرف دیگر در صورت حفظ این داده ها، ممکن است معنی داری آماری برازش زیر سوال رود.
3. شبکه بازیگران مثال خوبی از این موضوع است که توزیع درجه آن در اکثر درجات از قانون توان پیروی می‌کند. با این حال، به لطف فیلم دور دنیا در هشتاد روز که در سال 1956 ساخته شد، یک داده پرت برجسته درk = 1,287 شکل گرفت. این تنها فیلمی است که طبق imdb.com که منبع اطلاعات شبکه بازیگران است، تعداد بسیار زیادی (1288) بازیگر دارد. دومین فیلم بزرگ در این پایگاه داده تنها 340 بازیگر دارد. این فیلم یک داده پرت محلی درpk در k=1,287 به شمار می آید و باعث می شود توزیع درجه برازش شده برای قانون توان، نتواند آزمون های معنی داری آماری را پشت سر بگذارد. در واقع، همانطور که در جدول 4.3 آمده است، نه قانون توان خالص و نه قانون توانی با برش درجات بالا، نمی توانند برازش آماری معنی داری برای ان به شمار آیند. در حالی که در واقعیت، تنها یک نقطه ماهیت قانون توان توزیع درجه را تغییر نمی‌دهد.
4. 4. در نتیجه طبق مباحثی که در بالا مطرح شد، متدولوژی شرح داده شده برای برازش توزیع قانون توان اغلب با ناحیه کوچکی از توزیع درجه تطبیق پیدا می کند و معمولا مجبور می‌شویم بخش بزرگی از گره‌ها را برای دست‌یافتن یک برازش آماری معنی دار حذف کنیم (گاهی تا 99% داده ها، جدول 4.4 را ببینید). هنگامی که نمودار در کنار مجموعه داده اصلی رسم شود، حتی در صورتی که به لحاظ آماری معنی دار باشد، گاهی اوقات نتیجه به وضوح فاصله دارد و غیر قابل قبول و مضحک است.

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

بخش 4.14
فهرست مراجع

[1] H. Jeong, R.Albert, and A.-L. Barabási. Internet: Diameter of the world-wide web. Nature, 401:130-131, 1999.

[2] A.-L. Barabási and R.Albert. Emergence of scaling in random networks. Science, 286:509-512, 1999.

[3] V. Pareto. Cours d’Économie Politique: Nouvelle édition par G.- H. Bousquet et G. Busino, Librairie Droz, Geneva, 299–345, 1964.

[4] A.-L. Barabási. Linked: The New Science of Networks. Plume, New York, 2002.

[5] M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. Proceedings of SIGCOMM. Comput. Commun. Rev. 29: 251-262, 1999.

[6] R. Pastor-Satorras and A.Vespignani. Evolution and Structure of the Internet: A Statistical Physics Approach. Cambridge University Press, Cambridge, 2004.

[7] D. J. De Solla Price. Networks of Scientific Papers. Science 149: 510- 515, 1965.

[8] S. Redner. How Popular is Your Paper? An Empirical Study of the Citation Distribution. Eur. Phys. J. B 4: 131, 1998.

[9] R. Kumar, P. Raghavan, S. Rajalopagan, and A.Tomkins. Extracting Large-Scale Knowledge Bases from the Web. Proceedings of the 25thVLDBConference, Edinburgh,Scotland,pp.639-650,1999.

[10] A.-L. Barabási, R.Albert, and H. Jeong. Mean-field theory of scalefree random networks. Physica A 272:173-187, 1999.

[11] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási. The large-scale organization of metabolic networks. Nature 407: 651-654, 2000.

[12] A. Wagner, A. and D.A. Fell. The small world inside large metabolic networks. Proc. R. Soc. Lond. B 268: 1803–1810, 2001.

[13] W. Aiello, F. Chung, and L.A. Lu. Random graph model for massive graphs, Proc. 32nd ACM Symp. Theor. Comp, 2000.

[14] H. Jeong, B. Tombor, S. P. Mason, A.-L. Barabási, and Z.N. Oltvai. Lethality and centrality in protein networks. Nature 411: 41-42, 2001.

[15] A. Wagner. How the global structure of protein interaction networks evolves. Proc. R. Soc. Lond. B 270: 457–466, 2003.

[16] M. E. J. Newman. The structure of scientific collaboration networks. Proc. Natl.Acad. Sci. 98: 404-409, 2001.

[17] A.-L. Barabási, H. Jeong, E. Ravasz, Z. Néda, A. Schubert, and T. Vicsek. Evolution of the social network of scientific collaborations. Physica A 311: 590-614, 2002.

[18] F. Liljeros, C.R. Edling, L.A.N. Amaral, H.E. Stanley, and Y. Aberg. The Web of Human Sexual Contacts. Nature 411: 907-908, 2001.

[19] R. Ferrer i Cancho and R.V. Solé. The small world of human language. Proc. R. Soc. Lond. B 268: 2261-2265, 2001.

[20] R. Ferrer i Cancho, C. Janssen, and R.V. Solé. Topology of technology graphs: Small world patterns in electronic circuits. Phys. Rev. E 64: 046119, 2001.

[21] S. Valverde and R.V. Solé. Hierarchical Small Worlds in Software Architecture. arXiv:cond-mat/0307278, 2003.

[22] H. Ebel, L.-I. Mielsch, and S. Bornholdt. Scale-free topology of email networks. Phys. Rev. E 66: 035103(R), 2002.

[23] J.P.K. Doye. Network Topology of a Potential Energy Landscape: A Static Scale-Free Network. Phys. Rev. Lett. 88: 238701, 2002.

[24] J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabó, D. Lazer, K. Kaski, J. Kertesz, and A.-L. Barabási. Structure and tie strengths in mobile communication networks. Proceedings of the National Academy of Sciences 104: 7332-7336 (2007).

[25] H. Kwak, C. Lee, H. Park, S. Moon. What is Twitter, a social network or a news media? Proceedings of the 19th international conference on World Wide Web, 591-600, 2010.

[26] M. Cha, H. Haddadi, F. Benevenuto and K. P. Gummadi. Measuring user influence in Twitter: The million follower fallacy. Proceedings of international AAAI Conference on Weblogs and Social, 2010.

[27] J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The Anatomy of the Facebook Social Graph. ArXiv:1111.4503, 2011.

[28] L.A.N. Amaral, A. Scala, M. Barthelemy and H.E. Stanley. Classes of small-world networks. Proceeding National Academy of Sciences U. S. A. 97:11149-11152, 2000.

[29] R. Cohen and S. Havlin. Scale free networks are ultrasmall. Phys. Rev. Lett. 90, 058701, 2003.

[30] B. Bollobás and O. Riordan. The Diameter of a Scale-Free Random Graph. Combinatorica, 24: 5-34, 2004.

[31] R. Cohen and S. Havlin. Complex Networks - Structure, Robustness and Function. Cambridge University Press, Cambridge, 2010.

[32] K.-I. Goh, B. Kahng, and D. Kim. Universal behavior of load distribution in scale-free networks. Phys. Rev. Lett. 87: 278701, 2001.

[33] F. Karinthy. Láncszemek, in Minden másképpen van. Budapest, Atheneum Irodai es Nyomdai R.-T. Kiadása, 85–90, 1929. English translation in: M.E.J. Newman, A.-L. Barabási, and D. J. Watts. The Structure and Dynamics of Networks. Princeton University Press, Princeton, 2006.

[34] P.S. Dodds, R. Muhamad and D.J. Watts. An experimental study to search in global social networks. Science 301: 827-829, 2003.

[35] P. Erdős and T. Gallai. Graphs with given degrees of vertices. Matematikai Lapok, 11:264-274, 1960.

[36] C.I. Del Genio, H. Kim, Z. Toroczkai, and K.E. Bassler. Efficient and exact sampling of simple graphs with given arbitrary degree sequence. PLoS ONE, 5: e10012, 04 2010.

[37] V. Havel. A remark on the existence of finite graphs. Casopis Pest. Mat., 80:477-480, 1955.

[38] S. Hakimi. On the realizability of a set of integers as degrees of the vertices of a graph. SIAM J.Appl. Math., 10:496-506, 1962.

[39] I. Charo Del Genio, G. Thilo, and K.E. Bassler. All scale-free networks are sparse. Phys. Rev. Lett. 107:178701, 10 2011.

[40] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1: 311– 316, 1980.

[41] M. Molloy and B. A. Reed. Critical Point for Random Graphs with a Given Degree Sequence. Random Structures and Algorithms, 6: 161-180, 1995.

[42] M. Newman. Networks: An Introduction. Oxford University, Oxford, 2010.

[43] S. Maslov and K. Sneppen. Specificity and stability in topology of protein networks. Science, 296:910-913, 2002.

[44] G. Caldarelli, I. A. Capocci, P. De Los Rios, and M.A. Muñoz. Scale- Free Networks from Varying Vertex Intrinsic Fitness. Phys. Rev. Lett. 89: 258702, 2002.

[45] B. Söderberg. General formalism for inhomogeneous random graphs. Phys. Rev. E 66: 066121, 2002.

[46] M. Boguñá and R. Pastor-Satorras. Class of correlated random networks with hidden variables. Phys. Rev. E 68: 036112, 2003.

[47] A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review S1: 661-703, 2009.

[48] S. Redner. Citation statistics from 110 years of physical review. Physics Today, 58:49, 2005.