بخش 5-1
مقدمه

هاب­ها تمایز اصلی شبکه‌های تصادفی و شبکه‌های بدون مقیاس در وجود هاب­ نهفته است. ، سایت‌هایی مثل گوگل یا فیس بوک در شبکه جهانی وب دارای تعداد بسیار زیاد و استثنایی پیوند هستند. در شبکه متابولیک، برخی مولکول‌ها مانند ATP و ADP وجود دارند که در تعداد بسیار زیادی واکنش‌های شیمیایی نقش حامل انرژی را دارند. مشاهده موارد متعدد از این نوع هاب­ها و ویژگی­های توپولوژیکی دیگر شبکه‌های بدون مقیاس دو سؤال اساسی را در ذهن ایجاد می‌کنند:

     • چرا شبکه‌هایی مثل وب و سلول‌ها که با هم بسیار متفاوت هستند، معماری بدون مقیاس مشابه دارند؟

• چرا مدل تصادفی شبکه که توسط اردوش و رنی ارائه شده است توانایی تشخیص هاب¬ها و قانون توان در شبکه‌های واقعی را ندارد؟

اهمیت سؤال اول در این است که شبکه‌های بدون مقیاس (مقیاس آزاد) مانند وب و شبکه متابولیک، کاملاً به لحاظ ماهیت، منشأ و حوزه سیستم‌ها با هم متفاوت هستند:

• متابولیت¬ها و پروتئین‌ها، گره‌های شبکه‌های سلولی هستند. درحالی‌که در وب، صفحات وبی که صرفا مفهوم اطلاعاتی بوده و مابه¬ازای فیزیکی ندارند، گره‌ها را تشکیل می¬دهند.
• پیوندها در شبکه سلولی واکنش‌های شیمیایی و برهم‌کنش‌های پیوندی هستند درحالی‌که در وب، پیوندها همان URL ها یا پیوند صفحات وب به هم هستند.
• تاریخچه این دو سیستم خیلی متفاوت است: شبکه‌های سلولی در طی تکامل 4 میلیارد ساله، تشکیل‌شده‌اند درحالی‌که از پیدایش وب کمتر از 3 دهه می¬گذرد.
• هدف شبکه متابولیک، تولید مؤلفه‌های شیمیایی مورد نیاز برای ادامه حیات سلول‌ها است، درحالی¬که هدف از وب دسترسی و تبادل اطلاعات است.

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

بخش 5-2
رشد و الحاق ترجیحی

مطالعه خود را با این سؤال آغاز می‌کنیم: چرا هاب¬ها و قوانین توان در شبکه‌های تصادفی مشاهده نمی¬شوند؟ در سال 1999 دو فرضیه پنهان در مدل اردوش-رینی یافت شد که در شبکه‌های واقعی نقض می‌شوند. این دو فرضیه به یافتن پاسخ کمک کرد [1]. دراینجا درباره این دو فرضیه به تفکیک بحث خواهیم کرد.

شبکه‌ها با اضافه کردن گره‌های جدید گسترش می‌یابند

در مدل شبکه تصادفی، فرض بر این است که تعداد ثابتی گره (N) داریم. در حالی که در شبکه‌های واقعی با اضافه شدن گره‌های جدید دائماً تعداد گره‌های شبکه افزایش می‌یابد.

چند مثال را در نظر بگیرید:

•  در سال1991 اولین صفحه وب توسط تیم برنرز لی مؤسس وب ایجاد شد، در آن زمان وب تنها یک گره داشت. در حال حاضر بیش از10¹² سند در وب وجود دارد. این حجم گسترده از صفحات وب به مرور زمان با اضافه شدن پیوسته مستندات توسط میلیون‌ها نفر و موسسه ایجاد شده¬ است. (شکلa 5-1 ).
• شبکه مشارکت و ارجاعات علمی، دائماً با انتشار مقاله‌های جدید توسعه می‌یابد(.(شکل 5-1 b).
•  شبکه بازیگران با ساخت و انتشار فیلم‌های جدید توسعه می‌یابد (شکل 5-1c).
• • شبکه برهم‌کنش پروتئینی شاید به نظر ثابت باشد زیرا ژن‌ها (و درنتیجه پروتئین‌ها) را از والدینمان به ارث می‌بریم، اما این همه ماجرا نیست. در طول چهار میلیارد سال، تعداد ژن‌ها در سلول‌های انسان از تعداد محدودی به بیش از 20000 ژن رسیده است.

بنابراین با مدل‌های ایستا نمی‌توانیم این شبکه‌ها را مدل کنیم. ما باید در رویکرد مدل‌سازی در نظر داشته باشیم که شبکه‌ها محصول فرآیند رشد پیوسته هستند.

گره‌ها ترجیح می‌دهند به گره‌هایی با ارتباطات بیشتر متصل شوند.

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

مثال‌های زیر را در نظر بگیرید:

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

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

1. رشد
   شبکه‌های واقعی ماحصل رشد دائمی تعداد گره¬ها (N) هستند. در مقابل، مدل شبکه تصادفی فرض می‌کند که تعداد گره‌ها ثابت است.
2. الحاق ترجیحی
   در شبکه‌های واقعی، گره‌های جدید بیشتر تمایل دارند به گره‌های با پیوند¬های بیشتر متصل شوند. درمقابل در مدل شبکه تصادفی، پیوند¬های آنها به صورت تصادفی انتخاب می‌شود.

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

بخش 5-3
مدل باراباشی-آلبرت

پی بردن به این نکته که رشد و الحاق ترجیحی هر دو در شبکه‌های واقعی وجود دارند الهام‌بخش ارائه مدل مبنایی به نام باراباشی-البرت شد که می‌تواند شبکه‌های بدون مقیاس را ایجاد کند[1]. به این مدل، مدل BA یا مدل بدون مقیاس (مقیاس آزاد) هم گفته می‌شود و به صورت زیر تعریف می‌شود:

با m₀ گره شروع می‌کنیم، گره‌هایی که به صورت دلخواه انتخاب شده‌اند به هم متصل می‌شوند تا جایی که هر گره حداقل یک پیوند داشته باشد. شبکه، دو گام زیر را اجرا می‌کند (شکل 5-3 ):

1. رشد
   هر بار گره جدیدی با m (≤ m₀) پیوند ایجاد می‌شود و به m گره‌ای که در حال حاضر در شبکه وجود دارند متصل می‌شود.
2. الحاق ترجیحی
   احتمال ، احتمال اینکه بین گره جدید و گرهi یک پیوند وجود داشته باشد به درجه آن گره یا همانk_i بستگی دارد و با Π(k) نشان داده می¬شود:$\Pi (k_i ) = \frac{{k_i }}{{\sum\limits_j {k_j } }} \hspace{20 mm}$(5 . 1)

اتصال ترجیحی یک سازوکار احتمالی است: هر گره برای اتصال به هر گره دیگر آزاد است. گره دیگر می‌تواند هاب یا گره‌ای با تنها یک پیوند باشد. رابطه (5-1) نشان می¬دهد اگر گره جدیدی بخواهد بین گره‌ای با درجه دو و گره‌ای با درجه چهار انتخاب کند، احتمال اینکه به گره با درجه چهار متصل شود دو برابر است.

After t timesteps the Barabási-Albert model generates a network with N = t + m₀ nodes and m₀ + mt links. As Image 5.4 shows, the obtained network has a power-law degree distribution with degree exponent γ=3. A mathematically self-consistent definition of the model is provided in BOX 5.1.

As Image 5.3 and Video 5.2 indicate, while most nodes in the network have only a few links, a few gradually turn into hubs. These hubs are the result of a rich-gets-richer phenomenon: Due to preferential attachment new nodes are more likely to connect to the more connected nodes than to the smaller nodes. Hence, the larger nodes will acquire links at the expense of the smaller nodes, eventually becoming hubs.

In summary, the Barabási-Albert model indicates that two simple mechanisms, growth and preferential attachment, are responsible for the emergence of scale-free networks. The origin of the power law and the associated hubs is a rich-gets-richer phenomenon induced by the coexistence of these two ingredients. To understand the model’s behavior and to quantify the emergence of the scale-free property, we need to become familiar with the model’s mathematical properties, which is the subject of the next section.

بخش 5-4
دینامیک درجه‌ها

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

در این مدل درجه گره‌ای که از قبل وجود دارد با ورود گره جدید به شبکه می‌تواند افزایش یابد. این گره جدید به m گره از N(t) گره‌ای که در حال حاضر در سیستم وجود دارند متصل می‌شود. احتمال اینکه یکی از این پیوندها به گره i وصل شود در رابطه (5-1) نشان داده شده است.

اجازه دهید درجه k_i را با مقادیر حقیقی پیوسته تخمین بزنیم که این تخمین مقدار مورد انتظار را در طول فرایند رشد نشان می¬دهد. نرخ به دست آوردن پیوند از طریق اتصال به گره جدید توسط گره موجود i به‌صورت زیر است:

ضریب m نشان می¬دهد که هر گره جدید با m اتصال اضافه می‌شود. بنابراین گره iدارای m شانس انتخاب شدن است. جمعی که در مخرج رابطه (5-3) قرار دارد همه گره‌های شبکه به‌جز گرهی که تازه اضافه شده را شامل می‌شود. بنابراین:

بنابراین رابطه (5-3) به‌صورت زیر نوشته می‌شود:

برای t های بزرگ می‌توان از (1-) در مخرج چشم‌پوشی کرد که رابطه (5-6) به دست می‌آید:

با انتگرال‌گیری از رابطه 5-6 و با توجه به این که گره i در زمان t_i با m اتصال به شبکه ملحق می‌شودk_i(t_i)=m عبارت زیر به دست می‌آید:

β نمای دینامیکی با مقدار زیر است:

چند پیش‌بینی از رابطه (5-7) حاصل می¬شود:

• درجه هر گره با توجه به قانون-توان و با توان دینامیک β=1/2 افزایش می‌یابد(شکل 5-6a) بنابراین تمام گره‌ها از قانون دینامیک مشابهی پیروی می‌کنند.
• رشد درجه زیرخطی است(به عبارتی β < 1). این ویژگی از پیامدهای ماهیت رشد در مدل باراباشی-البرت است: هر گره جدید نسبت به گره‌های قدیمی به تعداد بیشتری گره می‌تواند متصل شود. بنابراین با گذر زمان گره‌های موجود برای به دست آوردن پیوندهای جدید با حجم زیادی از گره‌های دیگر که دائماً هم در حال افزایش هستند، رقابت می‌کنند.
• • هر قدر گره i زودتر اضافه شود، درجه k_i(t) آن بالاتر خواهد بود. بنابراین هاب¬ها از آنجایی که زودتر وارد شبکه شده‌اند، بزرگ‌تر هستند. به این پدیده در بازاریابی و تجارت مزیت پیشرو بودن می‌گویند.
• • نرخی که گره i پیوند جدیدی به دست می‌آورد با مشتق گیری از رابطه (5-7) به دست می‌آید. $\frac{{dk_i (t)}}{{dt}} = \frac{m}{2}\frac{1}{{\sqrt {t_i t} }} \hspace{20 mm} (5 . 8)$ این رابطه نشان می¬دهد که در هر گام زمانی، گره‌های قدیمی‌تر پیوندهای بیشتری به دست می‌آورند (زیرا t_i کوچک‌تری دارند). به‌علاوه به دلیل ضریب t^−1/2 نرخ به دست آوردن پیوندهای جدید توسط هر گره با گذر زمان کاهش می‌یابد. بنابراین تعداد پیوندهایی که به هر گره می‌رسد کمتر و کمتر می‌شود.

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

بخش 5-5
توزیع درجه

ویژگی متمایز شبکه‌های ایجاد شده با مدل باراباشی-آلبرت توزیع درجه قانون-توان آن‌ها است(شکل 5-4). در این بخش فرم تابعی p_k را حساب می‌کنیم تا به ما در درک مبانی آن کمک کند.

تعدادی ابزار تحلیلی برای محاسبه توزیع درجه شبکه باراباشی-آلبرت وجود دارد. ساده‌ترین آنها تئوری پیوستگی است که از بخش قبلی توسعه آن را آغاز کردیم [1, 11]و توزیع درجه را پیش‌بینی می‌کند(نکته 5-3)،

همراه با

بنابراین توزیع درجه از قانون-توان با درجه توان ϒ=3 پیروی می‌کند و با نتایج عددی هم مطابقت دارد (شکل 5.4 و 5.7). به‌علاوه (5-10) توان درجه ϒ که معیاری برای تعیین توپولوژی شبکه است را به توان دینامیک ᵝ که تکامل زمانی گره‌ها را تعیین می‌کند مرتبط می‌کند و ارتباط قوی بین توپولوژی شبکه و پویایی آن را نمایش می¬دهد.

از آنجایی که تئوری پیوستگی، توان درجه صحیح را پیش‌بینی می‌کند، در پیش‌بینی دقیق پیش عوامل رابطه (5-9) ناتوان است. پیش فاکتورهای دقیق می‌توانند با کمک مستر [12] یا معادله درجه [13] به دست آید یا به طور دقیق با استفاده از مدل LCD محاسبه شود]10[ (نکته 5-3). درنتیجه توزیع درجه دقیق مدل باراباشی-آلبرت به صورت رابطه 5-11 است(مطالب پیشرفته 5-A).

رابطه(5-11) چندین پیامد دارد:

• برای مقادیر بزرگ k، رابطه 5-11 به‌صورت خطی نسبت به روابط 5-9 و 5-10 به p_k~ k^-3 یا ϒ=3 کاهش می‌یابد.
•  توزیع درجه ϒمستقل از m است، پیش‌بینی‌ای که با نتایج عددی هم مطابقت دارد(شکل 5-7a).
•  توزیع درجه قانون-توان که در شبکه‌های واقعی مشاهده می‌شود سیستم‌هایی با اندازه و قدمت نسبتاً متفاوت را توصیف می‌کند. بنابراین یک مدل مناسب باید توزیع درجه‌ای مستقل از زمان ارائه دهد. در واقع طبق رابطه 5-11 توزیع درجه مدل باراباشی-آلبرت مستقل از t و N است. بنابراین، این مدل می‌تواند ظهور وضعیت ایستای مقیاس آزاد را پیش‌بینی کند. شبیه¬سازی‌های عددی با نشان دادن اینکه p_k به ازای t یا N های مختلف به‌طور کامل بر هم منطبق می‌شود، این پیش‌بینی را تأیید می‌کنند (شکل 5-7b)
• تساوی (5-11) پیش‌بینی می‌کند که ضریب توزیع قانون-توان متناسب با m(m+1) (یا m²برای m های بزرگ) است که این موضوع هم توسط شبیه‌سازی‌های عددی تأیید می‌شود.(شکل 5-7a الحاق ).

به طور خلاصه، محاسبات تحلیلی پیش‌بینی می‌کند که مدل باراباشی-آلبرت شبکه مقیاس آزاد با توان درجه ϒ=3 ایجاد می‌کند. توان درجه از پارامترهای m و m0 مستقل است. به‌علاوه توزیع درجه ایستا است (به زمان وابسته نیست) که بیان می‌کند چرا شبکه‌هایی با تاریخچه، قدمت و اندازه مختلف توزیع درجه یکسان دارند.

بخش 5-6:
حذف رشد یا حذف الحاق ترجیحی

حضور هم‌زمان رشد و الحاق ترجیحی در مدل باراباشی-آلبرت سؤال مهمی را به وجود می‌آورد: آیا هر دوی آنها برای ایجاد شبکه‌های بدون مقیاس ضروری هستند؟ به عبارت دیگر آیا می‌توانیم تنها با یکی از آن‌ها ویژگی‌های شبکه‌های بدون مقیاس را ایجاد کنیم؟ برای پاسخگویی به این پرسش در ادامه دو حالت را بررسی می‌کنیم که هر حالت تنها به یکی از دو مفهوم رشد شبکه و الحاق ترجیحی محدود می‌شود[1, 11].

مدل A:

برای بررسی نقش الحاق ترجیحی، مشخصه رشد (مؤلفه A) را نگه می‌داریم و الحاق ترجیحی(مؤلفه B) را حذف می‌کنیم. بنابراین مدل A با m₀ گره ‌ایجاد می‌شود و طبق گام‌های زیر تکامل می‌یابد:

1. رشد
   در هر گام زمانی گره جدیدی با m(≤m₀) اتصال اضافه می‌کنیم به‌طوری‌که به m گره‌ای که قبلاً اضافه شده بودند متصل شود.
2.  الحاق ترجیحی
   احتمال اینکه گره جدید به گره‌ای با درجه k_i متصل شود برابر: $\Pi (k_i ) = \frac{1}{{(m_0 + t - 1)}} \hspace{20 mm} (5 . 16)$ است.

به عبارتی Π(k_i) مستقل از k_i بوده و نشان می دهد گره جدید به صورت تصادفی گره‌هایی که به آنها متصل می‌شود را انتخاب می‌کند.

قضیه پیوستگی پیش‌بینی می‌کند که مدل A، k_i(t) را به‌صورت لگاریتمی با زمان افزایش می دهد.

که خیلی کندتر از سرعت افزایش قانون-توان است(5-7). درنتیجه توزیع درجه به‌صورت نمایی پیش می‌رود(شکل 5-8a)

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

مدل B

در ادامه برای ارزیابی نقش رشد، الحاق ترجیحی(مؤلفه B) را نگه می‌داریم و رشد(مؤلفه A) را حذف می‌کنیم. بنابراین مدل B با N گره شروع می‌شود و طبق گام‌های زیر تکامل می‌یابد:

2. الحاق ترجیحی
   

   در هر گام زمانی گره‌ای به‌صورت تصادفی انتخاب می‌شود و به گره i با درجه k_i که در حال حاضر در شبکه وجود دارد متصل می‌شود. این درحالیست که i با احتمالΠ(k) انتخاب شده است. ازآنجاکه Π(0)=0 است، فرض شده گره با k=0 دارای k=1 باشد، زیرا در غیر این صورت نمی‌تواند هیچ پیوندی به دست آورد. .

   در مدل B تعداد گره‌ها در طول تکامل شبکه ثابت می‌ماند درحالیکه تعداد پیوندها به صورت خطی با زمان افزایش می‌یابد. درنتیجه برای t بزرگ درجه هر گره به‌صورت خطی با زمان افزایش می‌یابد (شکل 5-7b, inset)

   $k_i (t) \approx \frac{2}{N}t \hspace{20 mm} (5 . 19)$

   در واقع در هر گام زمانی پیوند جدیدی اضافه می‌کنیم بدون اینکه تعداد گره‌ها تغییر کند.

   در ابتدا که هنوز پیوندهای کمی در شبکه وجود دارد(برای مثال L ≪ N)، هر پیوند جدید دو گره که هنوز متصل نیستند را به هم وصل می‌کند. در این مرحله روند تکامل مدل کاملاً شبیه مدل باراباشی-آلبرت با m=1 است. شبیه‌سازی‌های عددی نشان می دهد این سازمان توزیع درجه با دنباله قانون-توان ایجاد می‌کند (شکل 5-8b).

   اما همچنان p_k ایستا نیست. درواقع بعد از یک دوره گذار درجه گره‌ها به سمت میانگین درجه (5-19) همگرا می‌شوند و یک قله شکل می‌گیرد(شکل 5-8b). به ازای t→N(N-1)/2 شبکه به یک گراف کامل تبدیل می‌شود که در آن درجه همه گره‌ها k_max=N-1 است، زیرا p_k= δ(N-1).

به طور خلاصه، حذف الحاق ترجیحی باعث ایجاد شبکه در حال رشدی می‌شود که دارای توزیع درجه ایستا و نمایی است. در مقابل حذف رشد باعث از بین رفتن ایستایی می‌شود که درنتیجه شبکه به گراف کامل میل می‌کند. شکست دو مدل A و B برای تولید توزیع بدون مقیاس مشاهده‌شده اولیه نشان می¬دهد که رشد و الحاق ترجیحی به طور هم‌زمان برای ایجاد مشخصه بدون مقیاس بودن ضروری هستند.

بخش 5-7
اندازه‌گیری الحاق ترجیحی

در بخش قبل نشان دادیم رشد و الحاق ترجیحی هر دو در به وجود آمدن ویژگی مقیاس آزاد نقش دارند. وجود رشد در شبکه‌های واقعی به‌وضوح مشهود است: همه شبکه‌های بزرگ از طریق اضافه شدن گره‌های جدید به اندازه فعلی خود رسیده‌اند. برای درک بهتر وجود الحاق ترجیحی در شبکه‌های واقعی آزمایشی را ترتیب می¬دهیم. در این بخش نشان می‌دهیم که چطور از طریق اندازه‌گیری تابع Π(k) می‌توان وجود الحاق ترجیحی را در شبکه‌های واقعی نشان داد.

الحاق ترجیحی مبتنی بر دو فرضیه متمایز است:

فرضیه 1
احتمال اتصال به یک گره، به درجه k آن گره بستگی دارد. این فرضیه با مدل شبکه‌های تصادفی که در آنها Π(k) مستقل از k است در تضاد است.

فرضیه 2
فرم تابعی Π(k) نسبت به k به‌صورت خطی است.

هر دو فرضیه را می‌توان با اندازه‌گیری Π(k) آزمایش کرد. می‌توانیم برای سیستم‌هایی که زمان اضافه شدن هر گره به شبکه را می‌دانیم یا سیستم‌هایی که حداقل دو نقشه از شبکه که در زمان‌های نزدیک به هم تهیه شده‌اند در دسترس باشد، Π(k) را تعیین کنیم [14, 15].

شبکه‌ای را در نظر بگیرید که برای آن دو نقشه متفاوت داریم. اولین نقشه در زمان t و دومی در زمان t+∆t (شکل 5-9a) تهیه شده است. برای گره‌هایی که درجه آنها در بازه زمانی t∆ تغییر کرده است مقدار Δk_i = k_i(t+Δt )−k_i(t) است. طبق رابطه 5-1 تغییرات نسبی Δk_i/Δt باید مطابق رابطه زیر باشد:

که فرم تابعی الحاق ترجیحی را فراهم می‌کند. برای اینکه رابطه 5-20 معتبر باشد باید t∆ را کوچک نگه داریم، بنابراین تغییرات k∆ نسبتاً کم می‌شود. اما t∆ نباید خیلی کوچک باشد تا همچنان تغییرات ملموسی بین دو شبکه وجود داشته باشد.

در عمل ممکن است منحنیΔk_i/Δt دارای نویز باشد. برای کاهش این نویز مقدار تجمعی تابع الحاق ترجیحی را اندازه‌گیری می‌کنیم:

در غیاب الحاق ترجیحی Π(k_i) مقدار ثابتی خواهد داشت، بنابراین طبق رابطه 5-21، π(k)~k خواهد بود. اگر الحاق ترجیحی خطی وجود داشته باشد برای مثال اگر Π(k_i)=k_i انتظار داریم π(k) ~ k² باشد.

شکل 5-10 مقدار π(k) را که برای چهار شبکه واقعی اندازه‌گیری شده است، نشان می¬دهد. برای هر یک از شبکه‌ها، مشاهده می‌کنیم π(k) سریع‌تر از حالت خطی افزایش می‌یابد که بیانگر وجود الحاق ترجیحی است. شکل 5-10همچنین پیشنهاد می¬دهد که Π(k) را می‌توان به صورت زیر تخمین زد:

برای شبکه اینترنت و شبکه ارجاعات علمی داریم α ≈ 1که طبق (5-1) بیانگر آن است که Π(k) به صورت خطی به k وابسته است. این نکته با فرضیه‌های 1 و 2 تطابق دارد. برای شبکه‌های همکاری علمی و بازیگران، بهترین حالت ∝=0.9±0.1 است که به معنای الحاق ترجیحی زیرخطی است. .

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

بخش 5-8
الحاق ترجیحی غیرخطی

با مشاهده الحاق ترجیحی زیرخطی در شکل 5-10 سؤال مهمی به وجود می‌آید: تأثیر این غیرخطی بودن روی توپولوژی شبکه‌ها چیست؟ برای پاسخ به این پرسش الحاق ترجیحی خطی در (5-1) را با (5-22) جایگزین می‌کنیم و توزیع درجه در مدل باراباشی-آلبرت غیرخطی را محاسبه می‌کنیم.

رفتار شبکه برای ∝=0 واضح است: در غیاب الحاق ترجیحی به مدل A که در بخش 5-4 بحث کردیم، برمی‌گردیم. در نتیجه توزیع درجه از حالت نمایی پیروی می‌کند(5-17).

مدل باراباشی-آلبرت را به ازای α=1 بازیابی می‌کنیم تا به شبکه‌ای با توزیع درجه بدون مقیاس برسیم(5-14).

در ادامه روی حالتی که α≠1 یا α≠0 باشد تمرکز می‌کنیم. محاسبه p_k برای α دلخواه چندین نظام مقیاس¬بندی را نشان می دهد [13](موضوعات پیشرفته 5-B):

الحاق ترجیحی زیرخطی(0<α<1)

برای α > 0 گره‌های جدید بیشتر تمایل دارند به گره‌هایی با پیوندهای بیشتر متصل شوند تا گره‌هایی با پیوندهای کمتر. اما برای α<1 این سوگیری نسبتاً کم‌رنگ است و برای ایجاد توزیع درجه بدون مقیاس کافی نیست. در عوض، در این نظام درجه‌ها از توزیع نمایی کشیده پیروی می‌کنند(بخش 4.10).

در حالیکه μ(α) وابستگی ضعیفی به α دارد. کاهش نمایی در (5-23) نشان می¬دهد که الحاق ترجیحی زیرخطی اندازه و تعداد هاب ها را محدود می‌کند.

همچنین الحاق ترجیحی زیرخطی اندازه بزرگ‌ترین درجه ، k_max را هم طبق رابطه (4-18)تغییر می¬دهد. k_max. برای یک شبکه بدون مقیاس به‌صورت چندجمله‌ای نسبت به زمان تغییر می‌کند. برای الحاق ترجیحی زیرخطی داریم:

که یک وابستگی لگاریتمی است که رشد درجه بیشینه را کمتر از چندجمله‌ای پیش‌بینی می‌کند. همین رشد کندتر دلیل کوچک‌تر بودن هاب¬ها برای α < 1 را توضیح می¬دهد.(شکل 5-11).

الحاق ترجیحی فراخطی(α > 1)

برای α > 1 تمایل به اتصال به گره‌های با درجه بالاتر بیشتر می‌شود و درنتیجه فرایند ثروتمندان ثروتمندتر می‌شوند را سرعت می‌بخشد. نتایج این رویداد برای α > 2 بیشتر نمایان است. هنگامی‌که مدل، پدیده "برنده همه را می‌برد" را پیش‌بینی می‌کند: تقریباً همه گره‌ها به تعداد کمی ابَر-هاب متصل می‌شوند. درنتیجه شاهد به وجود آمدن شبکه‌هایی با الگوی قطب و اقمار خواهیم بود که در آنها بیشتر گره‌ها به تعداد کمی گره مرکزی متصل می‌شوند. وضعیت برای 1<α<2 هم به همین صورت است ولی شدت آن کمتر می‌شود.

فرآیند برنده همه را می‌برد اندازه بزرگ‌ترین هاب را تغییر می دهد:(شکل 5-11).

بنابراین برای α > 1، بزرگ‌ترین هاب به کسر محدودی از گره‌های سیستم متصل می‌شود. به‌طور خلاصه الحاق ترجیحی غیرخطی، توزیع درجه را تغییر می¬دهد که یا باعث محدود شدن سایز هاب¬ها می‌شود(α<1) یا باعث به وجود آمدن ابرهاب ها می‌شود(α > 1 شکل 5-12). در نتیجه Π(k) باید به‌صورت خطی محض به درجه‌های شبکه حاصل وابسته باشد تا بتواند شامل قانون-توان p_k خالص باشد. هرچند در سیستم‌های زیادی شاهد این وابستگی‌ها هستیم، در شبکه‌های دیگر مثل شبکه همکاران یا بازیگران، الحاق ترجیحی به‌صورت زیرخطی خواهد بود. یکی از دلایلی که در شبکه‌های واقعی باعث انحراف توزیع درجه از قانون-توان خالص می‌شود، غیرخطی بودن Π(k) است. بنابراین برای سیستم‌هایی با Π(k) زیرخطی، نمای کشیده شده (5-23) باید توزیع درجه بهتری ارائه دهد.

بخش 5-9
پیدایش الحاق ترجیحی

با توجه به نقش کلیدی‌ای که الحاق ترجیحی در تکامل شبکه‌های واقعی بازی می‌کند باید بپرسیم که این ویژگی از کجا سرچشمه می‌گیرد؟ این پرسش می‌تواند به دو موضوع جزئی‌تر شکسته شود:

چرا Π(k) به k وابسته است؟

چرا Π(k) به k وابستگی خطی دارد؟

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

سازوکار¬های محلی

مدل باراباشی-آلبرت فرض می¬کند الحاق ترجیحی وجود دارد. همان‌طور که در ادامه می‌بینیم بدون داشتن الحاق ترجیحی به صورت صریح هم می‌توان شبکه‌های بدون مقیاس ایجاد کرد. این مدل‌ها با ایجاد کردن الحاق ترجیحی کار می‌کنند. در ادامه درباره این مدل‌ها بحث می‌کنیم و Π(k) را برای آنها حساب می‌کنیم. از این طریق می‌توانیم ریشه‌های الحاق ترجیحی را درک کنیم.

مدل انتخاب پیوند
مدل انتخاب اتصال احتمالاً ساده‌ترین مثال از سازوکار محلی است که بدون الحاق ترجیحی، شبکه‌های بدون مقیاس ایجاد می‌کند [16]. این مدل به‌صورت زیر تعریف می‌شود(شکل 5-13):

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

ابتدا احتمال اینکه گره انتهای اتصالی که تصادفی انتخاب شده، دارای درجه k باشد را حساب می‌کنیم(q_k):

رابطه 5-26 دو حقیقت را بیان می‌کند:

• هرچه درجه یک گره بیشتر باشد، احتمال اینکه در انتهای اتصال انتخاب شده قرار داشته باشد، بیشتر خواهد بود.
• • هرچه تعداد گره‌ها با درجه k در شبکه بیشتر باشد(برای مثال p_k) احتمال اینکه گره انتهایی اتصال انتخاب شده درجه k داشته باشد بیشتر می‌شود.

در رابطه 5-26، C را می‌توان با استفاده از شرط نرمال‌سازی Σq_k = 1 محاسبه کرد که در نتیجه خواهیم داشتC=1/〈k〉. بنابراین احتمال اینکه گره‌ای با درجه k در انتهای اتصال انتخاب شده باشد برابر است با:

رابطه 5-27 احتمال اینکه گره جدید به گره‌ای با درجه k متصل شود را نشان می¬دهد. از آنجا که رابطه 5-27 نسبت به k خطی است، مدل انتخاب اتصال با استفاده از تولید الحاق ترجیحی خطی، شبکه بدون مقیاس می‌سازد.

مدل تقلید
هرچند مدل انتخاب اتصال ساده‌ترین سازوکار را برای الحاق ترجیحی ارائه می¬دهد، اما نه اولین مدل و نه رایج‌ترین سازوکار در بین مدل‌های مبتنی بر سازوکار محلی است. مدل تقلید رایج‌ترین و اولین مدل در بین مدل‌های مبتنی بر سازوکار محلی است(شکل 5-14). این مدل از پدیده ساده‌ای پیروی می‌کند: تولیدکنندگان صفحات وب سعی می‌کنند از پیوند‌های دیگر صفحات وب مرتبط استفاده کنند[17, 18]. این مدل را در ادامه شرح می‌دهیم:

در هر گام زمانی گره جدیدی به شبکه اضافه می‌شود. برای اینکه تصمیم بگیریم به کدام گره متصل شود به‌طور تصادفی گره u را انتخاب می‌کنیم. به عنوان مثال این گره یک صفحه وب را نشان می¬دهد که محتوای آن با محتوای گره جدید مرتبط است. سپس روال دو مرحله‌ای زیر را انجام می‌دهیم:(شکل 5-14):

1. اتصال تصادفی: با احتمال p گره جدید به u متصل می‌شود، یعنی به طور تصادفی به یک صفحه وب متصل می‌شود.
2.  تقلید: با احتمال 1-p یکی از پیوندهای خروجی u را انتخاب می‌کنیم و گره جدید را به انتهای دیگر این اتصال وصل می‌کنیم. به عبارت دیگر صفحه وب جدید اتصالی از گره u را تقلید می‌کند و به جای اینکه به گره u وصل شود، به انتهای دیگر آن متصل می‌شود.

احتمال انتخاب گره‌ای مشخص در گام(i)، 1/N است. گام دوم معادل انتخاب گره متصل به یک پیوند تصادفی است. در گره‌های بدون جهت احتمال انتخاب گره‌ای با درجه k در گام تقلید(ii) برابر است با k/2L. با ترکیب (i) و (ii) احتمال اینکه گره جدید به گره‌ای با درجه k متصل شود برابر است با:

که نسبت به k خطی است و الحاق ترجیحی خطی را پیش‌بینی می‌کند.

رواج مدل تقلید به ارتباط آن با سیستم‌های واقعی برمی‌گردد:

•  شبکه‌های اجتماعی: هرچه آشنایان یک نفر بیشتر باشند، بیشتر احتمال دارد آن فرد توسط آشنایانش به افراد دیگر معرفی شود. به عبارت دیگر ارتباطات دوستانمان را "تقلید" می‌کنیم. بنابراین بدون داشتن هیچ دوستی سخت است دوست جدیدی پیدا کنیم.
•  شبکه ارجاعات: هیچ دانشمندی نمی‌تواند از همه مقالات منتشر شده در زمینه‌ای خاص اطلاع داشته باشد. نویسندگان از طریق "تقلید" کردن مراجع مقالاتی که خوانده‌اند تصمیم می‌گیرند کدام مقاله را بخوانند و به آنها ارجاع دهند. بنابراین احتمال خوانده شدن و ارجاع دهی به مقالاتی که ارجاع بیشتری دارند، بیشتر است.
• • برهم¬کنش پروتئینی: ژن‌های جدید در سلول‌ها از طریق تکثیر ژنی ایجاد می‌شوند. می‌توان تکثیر ژن‌ها را به مدل تقلید نگاشت کرد. این ویژگی ذات بدون مقیاس بودن شبکه برهم¬کنش پروتئین‌ها را نشان می¬دهد[19,20].

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

بهینه‌سازی

یکی از قدیمی‌ترین فرضیه‌های اقتصاد این است که افراد تصمیمات منطقی می‌گیرند و بین منافع و هزینه¬ها تعادل برقرار می‌کنند. به عبارت دیگر هر شخصی سعی می‌کند سود شخصی خود را افزایش دهد. این نقطه آغازین نظریه تصمیم‌گیری منطقی در اقتصاد [21] و نظریه اصلی در علم سیاست، جامعه‌شناسی و فلسفه مدرن است. همان‌طور که در ادامه توضیح خواهیم داد، تصمیم¬گیری منطقی منجر به الحاق ترجیحی می‌شود [22, 23,24].

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

برای سادگی فرض کنید تمام گره‌ها در محفظه‌ای به اندازه یک متر مکعب قرار گرفته باشند. در هر گام زمانی یک گره جدید اضافه می کنیم و به‌طور تصادفی بر اساس موقعیت فیزیکی نقطه‌ای داخل مربع انتخاب می¬کنیم. برای تعیین جایی که گره جدید i باید به آن متصل شود تابع هزینه را محاسبه می¬کنیم[22]

این فرمول، هزینه اتصال به هر گره j ای که در حال حاضر در شبکه وجود دارد را حساب می‌کند. d_ij فاصله اقلیدسی بین گره جدیدi و انتهای احتمالیj را حساب می‌کند و h_j فاصله مبتنی بر شبکه بین گرهj و اولین گره شبکه است که به عنوان "مرکز" شبکه تعریف کردیم. این مرکز طوری انتخاب می‌شود که بهترین بازدهی را برای شبکه داشته باشد (شکل 5-15).

محاسبات نشان می دهد که بر اساس مقادیر مختلف δ در رابطه (5-28) و N سه توپولوژی مختلف شبکه به دست می‌آید:(شکل 5-15):

شبکه ستاره‌ای δ < (1/2)^1/2
برای δ=0 فاصله‌های اقلیدسی غیر مرتبط هستند، بنابراین گره‌ها به گره مرکزی وصل می‌شوند و شبکه ستاره‌ای ایجاد می‌کنند. هر بار که عبارت h_j به δd_ij در رابطه (5-28) غالب شود ساختار ستاره‌ای خواهیم داشت.

شبکه تصادفی δ ≥ N^1/2
در رابطه (5-28) برای هر δ بزرگی عملکرد عبارت δd_ij که مربوط به فاصله است بر h_j غلبه می‌کند. در این مورد هر گره جدیدی به گره‌ای که به آن نزدیک¬تر است وصل می‌شود. شبکه حاصل مانند شبکه‌های تصادفی، توزیع درجه محدودی خواهد داشت(شکل 15-6b ).

شبکه‌های بدون مقیاس  4 ≤ δ ≤ N^1/2
شبیه‌سازی‌های عددی و محاسبات تحلیلی نشان می‌دهند که مقادیر متوسط δ، توپولوژی شبکه بدون مقیاس ایجاد می¬کند[22]. ظهور توزیع قانون-توان در این نظام از دو سازوکار نشأت می‌گیرد که این دو باهم در رقابت هستند:

1. بهینه‌سازی: هر گره دارای حوضچه‌ای است که دارای خاصیت جذب است، بنابراین هر گره دیگری که در این حوضچه قرار گیرد به آن متصل می‌شود. اندازه هر حوضچه به h_j گرهj که در مرکز آن قرار دارد وابسته است که آن‌هم به نوبه خود به درجه گره k_j بستگی دارد(شکل 5-15f) .(Image 5.15f).
2.  تصادفی بودن: محل نهایی گره جدید را به طور تصادفی دریکی از N حوضچه جذب انتخاب می¬کنیم. گره با بزرگ‌ترین درجه، بزرگ‌ترین حوضچه جذب را خواهد داشت. بنابراین تعداد بیشتری گره و پیوند‌های جدید به دست خواهد آورد. همان‌طور که در شکل 5-16d بیان شده، این مسأله الحاق ترجیحی را به وجود می‌آورد.

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

تنوع سازوکارهایی که در این بخش بحث شد نشان می¬دهد که الحاق ترجیحی در سیستم‌های بسیاری که با هم تفاوت زیادی دارند به‌صورت دقیق وجود دارد، زیرا هم با رویکرد منطقی و هم تصادفی قابل ایجاد است[25]. بیشتر سیستم‌های پیچیده توسط فرآیندهایی هدایت می‌شوند که تا حدی شامل هردو هستند. بنابراین، صرف¬نظر از اینکه از رویکرد تصادفی یا منطقی پیروی شود، الحاق ترجیحی برنده است.

بخش 5-10
قطر و ضریب خوشه‌بندی

برای تکمیل ویژگی‌های مدل باراباشی-آلبرت، درباره رفتار قطر شبکه و ضریب خوشه‌بندی بحث می¬کنیم.

قطر

قطر شبکه که بیشترین فاصله در شبکه باراباشی-آلبرت است برای m>1 و N بزرگ از رابطه زیر پیروی می‌کند[33, 34]

بنابراین قطر کندتر از ln⁡N رشد می‌کند و درنتیجه، فاصله در مدل باراباشی-آلبرت کمتر از فاصله در گراف تصادفی با اندازه مشابه است. این تمایز به‌ویژه در مقادیر بزرگ N به چشم می‌آید.

توجه کنید وقتی‌که رابطه (5-29) برای قطر به دست آمد، متوسط فاصله 〈d〉 با همین نسبت رشد می¬کند. در واقع همان‌طور که در شکل 5-18 نشان دادیم، برای N کوچک، عبارت ln⁡N مقیاس 〈d〉 را با N نشان می¬دهد اما برای N بزرگ N(≥10⁴) تأثیر اصلاح لگاریتمی ln⁡ln⁡N چشم‌گیر می‌شود.

ضریب خوشه‌بندی

ضریب خوشه‌بندی مدل باراباشی- آلبرت از فرمول زیر پیروی می‌کند(مباحث پیشرفته 5-C) [35, 36]:

نتیجه رابطه (5-30) تا حدودی با نسبت 1/N به‌دست‌آمده از مدل شبکه تصادفی متفاوت است (شکل 5-19). این تفاوت‌ به دلیل جمله lnN)² است که ضریب خوشه‌بندی را برای N بزرگ افزایش می¬دهد. درنتیجه شبکه باراباشی-آلبرت به‌صورت محلی بیشتر از شبکه‌های تصادفی خوشه‌بندی می‌شود.

بخش 5-11
خلاصه

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

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

مدل آلبرت-باراباشی سؤال اساسی‌ای را مطرح می‌کند: آیا ترکیب رشد و الحاق ترجیحی دلیل واقعی به وجود آمدن شبکه‌های بدون مقیاس است؟ برای پاسخ به این پرسش، در مورد شرط لازم و کافی شبکه‌های بدون مقیاس استدلال کردیم. در ابتدا نشان دادیم که رشد و الحاق ترجیحی، هردو برای ایجاد شبکه‌های بدون مقیاس لازم هستند. بنابراین اگر یکی از آنها حذف شود ویژگی بدون مقیاس بودن یا ایستایی از بین می‌رود. دوم، نشان دادیم که اگر هر دوی آنها حضور داشته باشند باعث به وجود آمدن شبکه‌های بدون مقیاس می‌شوند. این استدلال، احتمالی را در ذهن باز می¬گذارد: آیا این دو سازوکار ماهیت بدون مقیاس بودن تمام شبکه‌ها را توضیح می‌دهند؟ آیا ممکن است شبکه‌های بدون مقیاس دیگری وجود داشته باشد که به خاطر سازوکار¬های کاملاً متفاوتی به وجود آمده باشند؟ در بخش5-9 درباره روش‌های انتخاب پیوند، تقلید و مدل‌های بهینه‌سازی که بدون داشتن تابع الحاق ترجیحی به صورت صریح، باعث ایجاد شبکه‌های بدون مقیاس می‌شوند، صحبت کردیم و به این پرسش هم پاسخ دادیم. نشان دادیم که این مدل‌ها با ایجاد Π(k) خطی باعث به وجود آمدن شبکه‌های بدون مقیاس می‌شوند. این یافته الگوی کلی‌تری را مورد تأکید قرار می¬دهد: تا به امروز تمام مدل‌های شناخته‌شده و سیستم‌های واقعی بدون مقیاس، دارای الحاق ترجیحی هستند. بنابراین به نظر می‌رسد سازوکار پایه مدل باراباشی-آلبرت می‌تواند منشأ پیدایش شبکه‌های بدون مقیاس را توصیف کند.

مدل باراباشی-آلبرت قادر به توضیح بسیاری از ویژگی‌های سیستم‌های واقعی نیست:

• مدل مقدار γ=3 را پیش‌بینی می‌کند اما توان درجه در شبکه‌های واقعی بین 2 و 5 متغیر است(جدول 4.2).
•  بسیاری از شبکه‌ها مثل وب یا شبکه ارجاعات، جهت‌دار هستند در¬حالی¬که این مدل صرفاً شبکه‌های بدون جهت تولید می‌کند.
• بسیاری از مفاهیم رایج شبکه‌ها مثل ایجاد پیوند بین گره‌های موجود در شبکه، حذف گره‌ها و پیوندها در این مدل لحاظ نشده است.
• مدل، بین گره‌هایی که ویژگی‌های ذاتی متفاوتی دارند مثل جدید بودن یک مقاله تحقیقاتی یا مفید بودن یک صفحه وب، تمایز قائل نمی‌شود.
•  هرچند گاهی مدل باراباشی-آلبرت برای مدل کردن شبکه اینترنت و شبکه سلولی استفاده شده است، ولی در عمل این مدل برای نمایش جزئیات هیچ شبکه واقعی خاصی طراحی نشده است. در واقع این یک مدل اثبات مفهومی است که هدف اصلی آن نمایش سازوکار پایه ایجاد کننده ویژگی بدون مقیاس است. بنابراین اگر می‌خواهیم تکامل سیستم‌هایی مثل اینترنت، سلول‌ها یا وب را درک کنیم، لازم است ویژگی‌های مهمی که در تکامل این سیستم‌ها نقش داشته‌اند مثل ماهیت وب، احتمال پیوندهای درونی و گره‌ها و حذف پیوند را در نظر بگیریم.

همان‌طور که در فصل 6 نشان می‌دهیم، این محدودیت‌ها می‌توانند به‌صورت سیستمی حل شوند.

بخش 5-12
تمرین

1. . ایجاد شبکه باراباشی-آلبرت

   با کمک کامپیوتر و استفاده از مدل باراباشی-آلبرت شبکه‌ای با N = 10⁴ گره و m=4 ایجاد کنید. به عنوان وضعیت شروع از یک شبکه کامل با m=4 استفاده کنید.

   1. توزیع درجه را در گام‌های میانی برای مثال وقتی شبکه10², 10³ و 10⁴ گره دارد، اندازه‌گیری کنید.
   2. نمودار توزیع درجه در گام‌های میانی را رسم و با هم مقایسه کنید. همچنین آنها را با قانون-توان با نمای درجهγ تطبیق دهید. آیا توزیع‌ها "همگرا" هستند؟
   3.  نمودار توزیع درجه تجمیعی را برای گام‌های میانی رسم کنید.
   4.  ضریب خوشه‌بندی میانگین را به عنوان تابعی از N اندازه‌گیری کنید.
   5.  طبق شکل 5-6a دینامیک درجه برای یکی از گره‌های اولیه و یکی از گره‌هایی که در زمان‌های t=100، t=1000 و t=5000 به شبکه اضافه شده‌اند را اندازه‌گیری کنید.
   
   
2. مدل باراباشی-آلبرت جهت‌دار

   گونه‌ای از مدل باراباشی-آلبرت را در نظر بگیرید که در هر گام زمانی گره جدیدی وارد می‌شود و با اتصال جهت‌دار به گره‌ای که مطابق با احتمال زیر انتخاب شده متصل می‌شود:

   $\Pi (k_i^{in} ) = \frac{{k_i^{in} + A}}{{\sum\nolimits_j {(k_j^{in} + A)} }}$

   در این فرمول k_iⁱⁿ درجه ورودی گره i را نشان می¬دهد و A هم مقداری ثابت برای تمام گره‌ها است. هر گره، m اتصال جهت‌دار دارد.

   1. با استفاده از رویکرد معادله نرخ، توزیع درجه ورودی و خروجی را برای شبکه حاصل محاسبه کنید.
   2. آیا با استفاده از ویژگی‌های تابع گاما و بتا می‌توانید مقیاس بندی قانون-توان برای توزیع درجه ورودی را به دست آورید؟
   3. برای A=0 نمای مقیاس¬بندی توزیع درجه مخالف γ=3 ،نمای مدل باراباشی- آلبرت، است. چرا؟
   
   
3. مدل تقلید

   با استفاده از رویکرد معادله نرخ نشان دهید که مدل تقلید جهت‌دار، شبکه‌های بدون مقیاس با نمای درجه ورودی $\gamma _i = \frac{{2 - p}}{{1 - p}}$ایجاد می¬کند

4. رشد بدون الحاق ترجیحی

   در مدل A برای حالتی که شبکه با اتصال تصادفی گره جدید به m گره موجود رشد می‌کند، توزیع درجه (5-18) را به دست آورید. با کمک کامپیوتر و با استفاده از مدل A، شبکه‌ای با 10⁴گره ‌ایجاد کنید. توزیع درجه را اندازه‌گیری کنید و بررسی کنید که با پیش‌بینی رابطه (5-18) سازگار است.

بخش 5-13
مباحث پیشرفته
به دست آوردن توزیع درجه

تعدادی تکنیک تحلیلی برای به دست آوردن دقیق توان درجه وجود دارد(5-11). در ادامه آن را با استفاده از معادله نرخ به دست می‌آوریم[12, 13]. این متد به اندازه¬ای عمومیت دارد که بتواند در پیدا کردن ویژگی‌های دامنه وسیعی از شبکه‌های در حال توسعه به کار آید. در نتیجه، محاسبات ارائه شده در اینجا ارتباط مستقیمی با بسیاری از سیستم‌ها دارند، از مدل‌های مرتبط با وب گرفته[16, 17, 18] تا مدل‌هایی که تکامل شبکه برهم¬کنش بین پروتئین‌ها را از طریق تکثیر ژن نمایش می‌دهند[19, 20].

اجازه دهید تعداد گره‌هایی که در زمان t درجه آن‌ها k است را با N(k.t) نمایش دهیم. توزیع درجه p_k(t) از طریق رابطه p_k(t) = N(k,t)/N(t)با این پارامتر مرتبط می‌شود. از آنجایی که در هر گام زمانی یک گره به شبکه اضافه می¬کنیم، پس داریم N=t. یعنی در هر لحظه تعداد کل گره‌ها برابر است با تعداد گام‌های زمانی(نکته 5-2).

الحاق ترجیحی را به‌صورت زیر می‌نویسیم:

از آنجا که در گراف‌های بدون جهت هر اتصال روی درجه دو گره تأثیرگذار است، از عبارت 2m استفاده شده است. هدف، محاسبه تغییر تعداد گره‌هایی است که بعد از اضافه شدن گره جدید به شبکه درجه آنها k است:

1.  گره جدید می‌تواند به گره‌ای با درجه k متصل شود و درجه آن را به K+1 برساند بنابراین مقدار N(k,t) کاهش می‌یابد.
2. گره جدید می‌تواند به گره‌ای با درجه (k-1) وصل شود و درجه آن را به k برساند در نتیجه مقدار N(k,t) افزایش می‌یابد.

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

اولین عبارت سمت چپ رابطه (5-32) احتمال اتصال گره جدید به گره‌ای با درجه k را نشان می¬دهد (الحاق ترجیحی)، عبارت دوم تعداد کل گره‌ها با درجه k را نشان می¬دهد، هر چه تعداد این گره‌ها بیشتر باشد، احتمال اینکه گره جدید به یکی از آنها وصل شود بیشتر می‌شود. عبارت سوم درجه گره ورودی است، هر چه m بیشتر باشد احتمال اینکه گره جدید به گره‌ای با درجه k وصل شود بیشتر می‌شود. سپس رابطه (5-32) را روی دو حالت (i) و (ii) که در بالا ذکر شد اعمال می¬کنیم:

1. تعداد گره‌های با درجه k که اتصال جدید به دست می‌آورند و جزء گره‌های با درجه (K+1) می‌شوند: $\frac{k}{2}p_k (t) \hspace{20 mm} (5 . 33)$
2. تعداد گره‌ها با درجه (k-1) که اتصال جدید به دست می‌آورد و درجه آن به k افزایش می‌یابد: $\frac{{k - 1}}{2}p_{k - 1} (t) \hspace{20 mm} (5 . 34)$

با ترکیب رابطه¬های (5-33) و (5-34) تعداد مورد انتظار گره‌ها با درجه k بعد از اضافه شدن گره جدید را به دست می‌آوریم:

این رابطه به همه گره‌ها با درجه K>m اعمال می‌شود. از آنجایی که تعداد گره‌ها با درجه k=0,1,…,m-1 در شبکه کم است (هر گره با درجه m وارد می‌شود) به معادله جداگانه‌ای برای گره‌های با درجه m نیاز داریم. در ادامه از استدلال مشابه که در رابطه (5-35) استفاده شد استفاده می کنیم و فرمول زیر به دست می‌آید.

رابطه‌های (5-35) و (5-36) نقطه شروع فرآیند بازگشتی هستند که p_k را ایجاد می‌کند. از آنجایی که به دنبال یافتن توزیع درجه پایدار هستیم که با نتایج شبیه‌سازی‌های عددی نیز تطابق دارد(شکل 5-6)، در حالت حدی N=t→∞ ، p_k(∞)= p_k می‌شود. بدین ترتیب می‌توانیم سمت چپ رابطه¬های (5-35) و (5-36) را به‌صورت زیر بنویسیم:

بنابراین معادله نرخ (5-35) و (5-36) به‌صورت زیر خواهند شد:

توجه کنید که رابطه (5-37) با تغییر متغیر k→k+1 به‌صورت زیر نوشته خواهند شد:

از رویکرد بازگشتی برای به دست آوردن توزیع درجه استفاده می¬کنیم. یعنی توزیع درجه را با استفاده از (5-38) برای کوچک‌ترین درجه k=m می‌نویسیم، و سپس با استفاده از رابطه (5-39)، p_k را برای درجه‌های بالاتر حساب می¬کنیم.

حال الگوی بازگشتی ساده‌ای را در نظر می‌گیریم: اگر در مخرج m+3 را با k جایگزین کنیم، احتمال مشاهده گره‌ای با درجه k به دست می‌آید.

که فرم دقیق توزیع درجه در مدل باراباشی-آلبرت را نشان می¬دهد.

توجه کنید که:

• به ازای k بزرگ ، رابطه (5-41) بهp_k ~ k^-3) تبدیل می‌شود که با نتایج عددی نیز سازگار است.
•  ضریب رابطه¬های (5-11) یا (5-41) با ضریب رابطه (5-9) متفاوت است.
• ضریب رابطه¬های (5-11) یا (5-41) با ضریب رابطه (5-9) متفاوت است.

در نهایت، معادله نرخ ما را به رابطه پیوسته¬ای می¬رساند که با توزیع درجه نیز سازگار است [16]. بدین منظور از معادله زیر شروع می¬کنیم:

می‌توانیم بنویسیم:

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

با بررسی (5-45) به عبارت زیر می‌رسیم:

بخش 5-14
مباحث پیشرفته5-B
الحاق ترجیحی غیرخطی

در این بخش توزیع درجه مدل باراباشی-آلبرت غیرخطی حاصل از الحاق ترجیحی را به دست می‌آوریم(5-22). مطابق مرجع [13] پیش خواهیم رفت، اما محاسبات را بر مبنای m>1 انجام خواهیم داد.

باید تأکید کرد تنها به ازای α≤1 در رابطه (5-22) توزیع درجه پایدار وجود دارد. همان‌طور که در بخش 5-7 بیان شد، برای α>1 تعداد کمی گره، کسر محدودی از پیوندها را جذب می‌کنند و p_k مستقل از زمان نخواهد بود. بنابراین محاسبات را به حالت α≤1 محدود می-کنیم.

با مدل غیرخطی باراباشی-آلبرت شروع می¬کنیم. در هر گام زمانی یک گره جدید با m اتصال اضافه می‌شود. هر گره جدید را با احتمال زیر به گره‌های موجود متصل می¬کنیم:

که در آن k_i درجه گره i، 0<α≤1 و

فاکتور نرمال‌سازی است و t=N(t) تعداد گره‌ها را نشان می¬دهد. توجه داشته باشید که μ(0, t)= Σp_k (t) =1 و μ(1, t) =Σ_kkp_k (t) =〈k〉=2mt/N متوسط درجه است. از آنجایی که 0<α≤1،

بنابراین در حالت حد زمانی طولانی

که مقدار دقیق آن بعداً محاسبه خواهد شد. برای سادگی، از نمادμ=μ(α.t→∞) استفاده می¬کنیم

با توجه به معادله نرخ که در مباحث پیشرفته 5-A بیان شد، معادله نرخ توزیع درجه شبکه را به‌صورت زیر می‌نویسیم:

اولین عبارت در سمت راست نرخی را نشان می¬دهد که گره‌ای با درجه (k-1)، یک اتصال به دست می‌آورد. عبارت دوم کم شدن گره‌ها با درجه k وقتی اتصال جدیدی به دست می‌آورند و به گره‌ای با درجه (k+1) تبدیل می‌شوند را نشان می¬دهد. آخرین عبارت هم گره‌های جدید از درجه m که اضافه شده‌اند را نشان می¬دهد.

متناوباً، در حالت حدی t→∞ می‌توان نوشت p_k=p_k(t + 1)=p_k(t) که اگر در رابطه (5-51) قرار دهیم k=m ، رابطه زیر به دست می¬آید:

برای k>m

با حل بازگشتی رابطه (5-53) فرمول زیر به دست می‌آید:

برای مشخص کردن رفتار p_k به ازای مقادیر بزرگ k از رابطه (5-57) لگاریتم می‌گیریم:

با استفاده از بسط دنباله $\ln (1 + x) = \sum\limits_{n + 1}^\infty {( - 1)^{n + 1} /n \cdot x^n }$ فرمول زیر به دست می¬آید:

جمع به ازای تمام j ها را با استفاده از انتگرال تخمین می‌زنیم:

که در حالت خاص وقتی nα=1 رابطه زیر به دست می‌آید:

بنابراین رابطه زیر به دست می‌آید:

در نتیجه توزیع درجه به‌صورت زیر خواهد بود:

که در آن

عبارت‌های حذف‌شده از توان روی رفتار تقریبی رابطه وقتی k→∞ تأثیری ندارد و تنها زمانی که 1-nα≥1 باشد تأثیرگذار است. در نتیجه p_k به α بستگی دارد، زیرا:

برای 1⁄2<α<1 توزیع درجه از نمایی کشیده پیروی می‌کند. با کاهش α، وقتی α کمتر از1 /n (که n یک عدد صحیح مثبت است) باشد، تغییراتی رخ خواهد داد.

همان‌طور که در مدل باراباشی-آلبرت انتظار داریم، برای α→1 مقیاس توزیع درجه به k⁻³ نزدیک شود. در واقع برای α=1، μ=2 خواهد بود و

بنابراین p_k ~ k⁻¹exp(−2lnk) = k⁻³.

در آخر μ (α) =Σ^jj^α p_j را محاسبه می¬کنیم. به همین دلیل جمع رابطه (5-58) را به دست می¬آوریم:

با حل عددی رابطه (5-68)، μ(α) به دست می‌آید.

بخش 5-15
مباحث پیشرفته 5-c
ضریب تأثیر خوشه‌بندی

در این بخش ضریب تأثیر خوشه‌بندی (رابطه 5-30) را برای مدل باراباشی-آلبرت به دست می‌آوریم. برای این منظور از استدلال ارائه شده توسط کلم و ایگولوز [35] اقتباس ‌شده است که محاسبات دقیق بلوباس نیز آن را تأیید می‌کند [36].

می‌خواهیم تعداد مثلث‌های مورد انتظار در این مدل را به دست آوریم، زیرا می¬تواند با ضریب تأثیر خوشه‌بندی در ارتباط باشد (بخش 2.10). احتمال وجود اتصال بین گره‌های iو j را با P(I,j) نشان می‌دهیم. بنابراین احتمال اینکه سه گره i،j،k یک مثلث تشکیل دهند برابر است با p(i,j)p(i,l)p(j,l). تعداد مثلث‌های مورد انتظاری که گرهl با درجه k_l در آنها شرکت می‌کند برابر است با مجموع احتمال شرکت گرهl در مثلث‌هایی با گره‌های دلخواه i و j در شبکه. می‌توانیم از تقریب درجه پیوسته برای نوشتن فرمول زیر استفاده کنیم:

در ادامه باید P(i,j) را حساب کنیم بنابراین باید شیوه تکامل مدل باراباشی-آلبرت را در نظر بگیریم. اجازه دهید از آنجا که در هر گام زمانی یک گره جدید اضافه می‌کردیم، لحظه‌ای که گره j می‌رسد را با t_j =j نشان دهیم (زمان رویداد نکته 5-2). بنابراین احتمال اینکه وقتی گرهj می‌رسد، به گره i با درجه k_i متصل شود، با الحاق ترجیحی نشان داده شده است:

با استفاده از رابطه (5-7) می‌توان نوشت:

از این نکته که زمان رسیدن گرهj برابر باt_j =j و گرهi برابر باt_i = i است، استفاده کردیم. بنابراین رابطه (5-70) به‌صورت زیر درمی‌آید:

با کمک نتیجه حاصل، تعداد مثلث‌ها در رابطه (5-69) را با نوشتن فرمول زیر، حساب می¬کنیم:

ضریب خوشه‌بندی را می‌توان به‌صورت زیر نوشت:

بنابراین خواهیم داشت

برای ساده کردن رابطه(5-74)، می‌دانیم که طبق رابطه (5-7) داریم:

که درجه گرهl در زمان t=N است. بنابراین برای k_l بزرگ داریم:

که به ما این امکان را می¬دهد که ضریب خوشه‌بندی مدل باراباشی-آلبرت را به‌صورت زیر بنویسیم:

که مستقل ازl است بنابراین رابطه (5-30) حاصل می‌شود.

بخش 5-16
مراجع

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

[2] F. Eggenberger and G. Pólya. Über die Statistik Verketteter Vorgänge. Zeitschrift für Angewandte Mathematik und Mechanik, 3:279-289, 1923.

[3] G.U. Yule. A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis. Philosophical Transactions of the Royal Society of London. Series B, 213:21-87, 1925.

[4] R. Gibrat. Les Inégalités économiques. Paris, France, 1931.

[5] G. K. Zipf. Human behavior and the principle of least resort. Addison- Wesley Press, Oxford, England, 1949.

[6] H. A. Simon. On a class of skew distribution functions. Biometrika, 42:425-440, 1955.

[7] D. De Solla Price. A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information Science, 27:292-306, 1976.

[8] R. K. Merton. The Matthew effect in science. Science, 159:56-63, 1968.

[9] A.-L. Barabási. Linked: The new science of networks. Perseus, New York, 2002.

[10] B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18:279-290, 2001.

[11] A.-L. Barabási, H. Jeong, R. Albert. Mean-field theory for scale free random networks. Physica A, 272:173-187, 1999.

[12] S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhin. Structure of growing networks with preferential linking. Phys. Rev. Lett., 85:4633-4636, 2000.

[13] P.L. Krapivsky, S. Redner, and F. Leyvraz. Connectivity of growing random networks. Phys. Rev. Lett., 85:4629-4632, 2000.

[14] H. Jeong, Z. Néda. A.-L. Barabási. Measuring preferential attachment in evolving networks. Europhysics Letters, 61:567-572, 2003.

[15] M.E.J. Newman. Clustering and preferential attachment in growing networks. Phys. Rev. E 64:025102, 2001.

[16] S.N. Dorogovtsev and J.F.F. Mendes. Evolution of networks. Oxford Clarendon Press, 2002.

[17] J.M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The Web as a graph: measurements, models and methods. Proceedings of the International Conference on Combinatorics and Computing, 1999.

[18] R. Kumar, P. Raghavan, S. Rajalopagan, D. Divakumar, A.S. Tomkins, and E. Upfal. The Web as a graph. Proceedings of the 19th Symposium on principles of database systems, 2000.

[19] R. Pastor-Satorras, E. Smith, and R. Sole. Evolving protein minteraction networks through gene duplication. J. Theor. Biol. 222:199–210, 2003.

[20] A. Vazquez, A. Flammini, A. Maritan, and A. Vespignani. Modeling of protein interaction networks. ComPlexUs 1:38–44, 2003.

[21] G.S. Becker. The economic approach to Human Behavior. Chicago, 1976.

[22] A. Fabrikant, E. Koutsoupias, and C. Papadimitriou. Heuristically optimized trade-offs: a new paradigm for power laws in the internet. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), pages 110-122, Malaga, Spain, July 2002.

[23] R.M. D’Souza, C. Borgs, J.T. Chayes, N. Berger, and R.D. Kleinberg. Emergence of tempered preferential attachment from optimization. PNAS 104, 6112-6117, 2007.

[24] F. Papadopoulos, M. Kitsak, M. Angeles Serrano, M. Boguna, and D. Krioukov. Popularity versus similarity in growing networks. Nature, 489: 537, 2012.

[25] A.-L. Barabási. Network science: luck or reason. Nature 489: 1-2, 2012.

[26] B. Mandelbrot. An Informational Theory of the Statistical Structure of Languages. In Communication Theory, edited by W. Jackson, pp. 486-502. Woburn, MA: Butterworth, 1953.

[27] B. Mandelbrot. A note on a class of skew distribution function: analysis and critique of a Paper by H.A. Simon. Information and Control, 2: 90-99, 1959.

[28] H.A. Simon. Some Further Notes on a Class of Skew Distribution Functions. Information and Control 3: 80-88, 1960.

[29] B. Mandelbrot. Final Note on a Class of Skew Distribution Functions: Analysis and Critique of a Model due to H.A. Simon. Information and Control, 4: 198-216, 1961.

[30] H.A. Simon. Reply to final note. Information and Control, 4: 217-223, 1961.

[31] B. Mandelbrot. Post scriptum to final note. Information and Control, 4: 300-304, 1961.

[32] H.A. Simon. Reply to Dr. Mandelbrot’s Post Scriptum. Information and Control, 4: 305-308, 1961.

[33] R. Cohen and S. Havlin. Scale-free networks are ultra small. Phys. Rev. Lett., 90:058701, 2003.

[34] B. Bollobás and O.M. Riordan. The diameter of a scale-free random graph. Combinatorica, 24:5-34, 2004.

[35] K. Klemm and V.M. Eguluz. Growing scale-free networks with small-world behavior. Phys. Rev. E, 65:057102, 2002.

[36] B. Bollobás and O.M. Riordan. Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks, edited by S. Bormholdt and A. G. Schuster, Wiley, 2003.