بخش 7.1
مقدمه

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

Hubs Dating Hubs. — شکل 7.1
هاب ها با هاب های دیگر قرار می گذارند
زوج های هنری اثبات واضحی برای این موضوع ارائه می دهند که هاب ها به شناخت، قرار گذاشتن و ازدواج با یکدیگر تمایل دارند(تصویر از http://www.whosdatedwho.com)

فرض کنید هر فرد مشهور می تواند با هر فردی از استخری شامل صد میلیون کاندید (10⁸) از سراسر دنیا قرار بگذارد، احتمال اینکه زوج آنها فرد مشهور دیگری از لیستی شامل 1000نفر باشد برابر است با 10^-5. بنابراین اگر ازدواج رویدادی تصادفی بود، افراد مشهور هرگز با هم ازدواج نمی کردند.

حتی اگر به روال قرار گذاشتن افراد مشهور هم اهمیت ندهیم باید توقف کنیم و درباره آنچه این رویداد درباره ساختار شبکه های اجتماعی به ما میگوید تحقیق کنیم. هنرمندان، رهبران سیاسی و مدیران شرکت های بزرگ به طور بالقوه، افراد بسیاری را می شناسند و حتی افراد خیلی بیشتری آنها را می شناسند. این افراد هاب ها هستند. بنابراین قرار گذاشتن هنرمندان(شکل 7.1) و اعضای هیئت مدیره شرکت (شکل 7-0) آشکار ساز ویژگی جالب شبکه های اجتماعی می باشد: هاب ها تمایل دارند به هاب های دیگر متصل شوند.

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

Hubs Avoiding Hubs. — شکل 7.2
هر هاب از هاب های دیگر اجتناب می کند

شبکه برهم کنش پروتئین مخمر. هر گره معادل یک پروتئین است و اگر شواهد ازمابشگاهی نشان دهد که دو گره می توانند با هم در یک سلول تلفیق شوند، بین آنها پیوند وجود خواهد داشت. دو هاب بزرگتر با درجه 56=k و 13=k’ را مشخص کرده ایم. هر دو اینها به چندین گره با درجه کم متصل می شوند و از اتصال به یکدیگر اجتناب می کنند.

شبکه دارای 1870=N پروتئین و 2277=L پیوند می باشد که یکی از اولین نقشه های برهم کنش پروتئینی را نشان می دهد[1, 2]. تنها بزرگترین مولفه نشان داده شده است. در نظر داشته باشید که شبکه برهم کنش پروتئینی مخمر در جدول 4.1 نقشه جدیدتر را نشان می دهد، بنابراین دارای تعداد بیشتری گره و پیوند نسبت شبکه نشان داده شده در این شکل می باشد. رنگ هر گره ضرورت هر پروتئین را نشان می دهد: حذف گره های قرمز رنگ باعث مرگ ارگانیسم می شود به همین دلیل پروتئین های کشنده یا ضروری نامیده می شوند. در مقابل ارگانیسم بدون یکب از گره های سبز رنگش می تواند زنده بماند[3].

انجام محاسبات مختصر نشان می دهد تا چه میزان این الگو غیر عادی است. اجازه دهید فرض کنیم هر گره به طوری تصادفی گره هایی که به آنها متصل می شود را انتخاب می کند. بنابراین احتمال اینکه گره های با درجه k و k’ به هم متصل شوند برابر است با:

$p_{k,k'} = \frac{{kk'}}{{2L}} \hspace{20 mm} (7 . 1)$

رابطه (7-1) می گوید هاب ها به لطف تعداد پیوند های زیادی که دارند احتمال اتصال آنها به یکدیگر بیشتر از احتمال اتصال آنها به گره هایی با درجه کم است. در واقع اگر k و k’ بزرگ هستند درنتیجه p_k,k’ هم بزرگ خواهد بود. درنتیجه احتمال اینکه پیوند مستقیمی بین هاب هایی با درجه 56=k و 13=k’ وجود داشته باشد برابر است با p_k,k’ = 0.16 که 400 برابر بزرگتر از حتمال پیوند گره با درجه دو به گره ای با درجه یک p_1,2 = 0.0004 است. با اینکه پیوند مستقیمی بین هاب ها در شکل 7.2 وجود ندارد اما چندین پیوند مستقیم بین گره های با درجه کم وجود دارد.

هاب هایی که در شکل 7.2 نشان داده شده اند بجای اتصال با یکدیگر تقریبا تماما به گره های با درجه یک متصل شده اند. به خود خود این اتفاق دور از انتظار نیست: انتظار داریم هابی با درجه 56=k باید به N₁p_{1, 56} ≈ 12 گره با درجه 1=k متصل شود. مشکل اینجاست که این هاب به 46تا همسایه با درجه یک متصل می شود یعنی چهار برابر عدد مورد انتظار.

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

بخش 7.2
هم ساز و غیر هم ساز

تنها به لطف پیوندهای زیادی که هاب ها دارند انتظار می رود به هم متصل شوند. در بعضی از شبکه ها چنین است ولی در بعضی دیگر اینچنین نیست. این موضوع در شکل 7.3 نشان داده شده است در این شکل سه شبکه با دنباله درجه مشابه ولی توپولوژی متفاوت را نشان می دهد

شبکه های خنثی
شکل 7.3b شبکه ای با اتصالات تصادفی را نشان می دهد. به این شبکه ها، شبکه های خنثی می گویند که در آنها تعداد پیوند ها بین گره ها مطابق با چیزی است که ما به صورت تصادفی انتظار داریم همانطور که توسط رابطه 7-1 پیش بینی شده است.
شبکه های همساز
دنباله درجه شبکه شکل 7.3b دقیقا شبیه دنباله درجه شکل 7-3a است. با این حال هاب ها در شکل 7.3a تمایل دارند به هم متصل شوند و از اتصال به گره های با درجه کم اجتناب می کنند. همچنین گره های با درجه کم هم تمایل دارند به دیگر گره های با درجه کم متصل شوند. شبکه هایی که چنین رویکردی دارند را همساز می گویند. نمونه بارزی از این الگو، شبکه کاملا هم ساز است که در آن هر گره با درجه k تنها به گره دیگری با درجه k متصل می شود(شکل 7.4).
شبکه غیر هم ساز
در شکل 7.3c هاب ها از اتصال به یکدیگر اجتناب می کنند و در عوض به گره های با درجه کوچک متصل می شوند. درنتیجه شبکه بصورت قطب و اقمار خواهد بود.که شبکه را غیر همساز می کند.

به طوری کلی اگر تعداد پیوندها بین گره های با درجه بالا و درجه پایین به طوری سیستمی با آنچه بطور شانسی انتظار میرودمتمایز باشد، شبکه همبستگی درجه ای نشان می دهد. به عبارت دیگر تعداد پیوند ها بین گره های با درجه kو k’ از رابطه (7-1) منحرف می شود.

Degree Correlation Matrix. — شکل 7.3
ماتریس همبستگی درجه ای

**(a,b,c)** سه شبکه ای که توزیع درجه دقیقا مشابه دارند (پواسن *p_k*) اما همبستگی های درجه متفاوتی را نشان می دهند. تنها بزرگترین مولفه را نشان می دهیم و پنج گره ای که بیشترین درجه را دارند با رنگ نارنجی نشان داده ایم و بین آنها پیوند برقرار کرده ایم.

**(d,e,f)** همبستگی درجه ای ماتریس *e_ij* برای یک شبکه همساز(d) یک شبکه خنثی (e) و یک شبکه غیر همساز(f) با توزیع درجه پواسن N=1000 و *〈k〉*=10. رنگ ها احتمال اتصال گره ای که به طور تصادفی انتخاب شده به گره هایی با درجه k₁ و k₂ را نشان می دهند.

**(a,d) شبکه های همساز**
برای شبکه های همساز *e_ij* در راستای قطر اصلی بالاست. این نکته نشان می دهد گره های ب درجه های قابل قیاس به یکدیگر متصل می شوند: گره های با درجه کم به گره های با درجه کم و گره های هاب ها هم به هاب ها متصل می شوند. درواقع شبکه (a) چندین پیوند بین هاب ها دارد همانطور که چندین پیوند بین گره های با درجه پایین دارد.

**(b,e) شبگه های خنثی**
در شبکه های خنثی گره ها بطور تصادفی به یکدیگر متصل می شوند. بنابراین چگالی پیوند ها نسبت به میانگین درجه متقارن می باشدکه نشان دهنده فقدان همبستگی در الگوی اتصالات می باشد.

**(c,f)شبکه های غیر همساز**
در شبکه های غیر همساز *e_ij* در راستای قطر دوم بالاتر است که نشان می دهد هاب ها تمایل دارند به گره های با درجه پایین و گره های با درجه پایین به هاب ها متصل شوند. در نتیجه همانطور که در (c)دیده شد این شبکه ها دارای مشخصه قطب و اقمار هستند.

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

$\sum\limits_{i,j} {e_{ij} } = 1 \hspace{20 mm} (7 . 2)$

در رابطه (5-27) احتمال q_k را بدست آوردیم که احتمال وجود گره ای با درجه k در انتهای پیوندیست که بطور تصادفی انتخاب شده است و با بدست آوردن رابطه زیر

$q_k = \frac{{kp_k }}{{\left\langle k \right\rangle }} \hspace{20 mm} (7 . 3)$

با استفاده از رابطه زیر می توانیم q_k را به e_ij وصل کنیم

$\sum\limits_j {e_{ij} = q_i } \hspace{20 mm} (7 . 4)$

در شبکه های خنثی انتظار داریم

$e_{ij} = q_i q_j \hspace{20 mm} (7 . 5)$

اگر e_ij از مقدار مورد انتظار تصادفی رابطه (7.5) منحرف شود، شبکه همبستگی درجه ای نشان می دهد. توجه کنید که (7-2)-(7- 7) برای شبکه های با توزیع درجه دلخواه معتبر هستند بنابراین هم به شبکه های تصادفی هم شبکه های مقیاس-آزاد اعمال می شوند.

Perfect Assortativity. — شکل 7.4
Perfect Assortativity
In a perfectly assortative network each node links only to nodes with the same degree. Hence *e_jk* = *Î´_jkq_k*, where *Î´_jk* is the Kronecker delta. In this case all non-diagonal elements of the *e_jk* matrix are zero. The figure shows such a perfectly assortative network, consisting of complete k-cliques.

اگر e_ij تمام اطلاعات همبستگی درجه ای بالقوه را رمزگزاری کند، از بازرسی بصری آن شروع می کنیم. شکل 7-3d,e,f ، e_ij را برای یک شبکه همساز، شبکه خنثی و شبکه غیر هم ساز نشان می دهد. در شبکه های خنثی گره های با درجه بالا و درجه پایین به طور تصادفی به هم متصل می شوند بنابراین e_ij هیچ گرایشی نخواهد داشت(شکل 7.3e). در مقابل شبکه های همساز همبستگی بالایی در راستای قطر اصلی نشان می دهند که نشان می دهد گره ها غلبا به گره هایی متصل می شوند که درجه قابل قیاسی دارند. بنابراین گره های با درجه کم تمایل دارند به گره های با درجه کم و هاب ها هم تمایل دارند به هاب ها متصل شوند(شکل 7.3d). در شبکه های غیر همساز e_ij گرایش متضادی را نشان می دهد: همبستگی بالایی در راستای دومین قطر دارد. بنابراین گره های با درجه بالا تمایل دارند به گره های با درجه پایین متصل شوند(شکل 7.3a).

بطور خلاصه، همبستگی درجه ای از ماتریس همبستگی درجه ای e_ij بدست می آید. با این حال مطالعه همبستگی درجه ای با استفاده از بررسی e_ij معایب بسیار زیادی دارد:

استخراج اطلاعات از طریق بازرسی بصری ماتریس دشوار است.
نمی توان شدت همبستگی را بدست، مقایسه شبکه ها با همبستگی های متفاوت دشوار است.
e_jk تقریبا شامل k_max²/2 متغیر مستقل است که حجم زیادی از اطلاعات را نشان می هند. مدل سازی این اطلاعات با محاسبات آماری و شبیه سازی دشوار است.

بنابراین نیاز است راه جمع و جور تری برای بدست آوردن همبستگی درجه ای ارائه شود که هدف بخش های بعدی می باشد.

بخش 7-3
اندازه گیری همبستگی درجه ای

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

همبستگی درجه ای ارتباط بین درجه گره هایی که به هم متصل می شوند را نشان میدهد. یکی از راههای ارزیابی میزان همبستگی درجه ای، بدست آوردن میانگین درجه همسایه ها برای هر گرهi می باشد(شکل 7.5).

$k_{nn} (k_i ) = \frac{1}{{k_i }}\sum\limits_{j = 1}^N {A_{ij} k_j } \hspace{20 mm} (7 . 6)$

تابع همبستگی درجه ای، رابطه (7-6) را برای تمام گره ها با درجه k حساب می کند[4, 5].

$k_{nn} (k) = \sum\limits_{k'} {k'} P(k'|k) \hspace{20 mm} (7 . 7)$

The behavior observed in Image 7.6 prompts us to approximate the degree correlation function with [4]

$k_{nn} (k) = ak^\mu \hspace{20 mm} (7 . 10)$

که در آن P(k'|k┤) احتمال شرطی است که با دنبال کردن پیوند گره ای با درجه k به گره ای با درجه k’ می رسیم. بنابراین میانگین درجه همسایه تمام گره ها با درجه k می باشد. برای ارزیابی همبستگی درجه ای انتظار داریم بین و ارتباط باشد

شبکه خنثی
برای شبکه عصبی (7.5)-(7.3) پیش بینی می شود که بدین ترتیب می توانیم k_nn(k) را بصورت زیر تعریف کنیم: بنابراین میانگین درجه گره های همسایه یک گره مستقل از درجه k گره است و تنها به مشخصه های کلی شبکه یعنی > و2> بستگی دارد. بنابراین اگر k_nn(k) را بصورت تابعی از k رسم کنیم، همانطور که در شبکه برق (شکل 7.6b) دیدیم، نتیجه محور افقی روی k²> / می شود. تساوی (7.9) همچنین ویژگی جالبی از شبکه های واقعی را نشان می دهد: دوستان ما معروف تر از ما هستند، پدیده ای که به آن تناقض دوستی می گویند(نکته 7.1).

شبکه های همساز
در شبکه های همساز، هاب ها تمایل دارند به هاب های دیگر متصل شوند، بنابراین هرچه درجه kگره ای بیشتر باشد، میانگین درجه نزدیکترین همسایه هایش هم بیشتر خواهد بود. در نتیجه برای شبکه های همساز، k_nn(k)با افزایش kافزایش می یابد. چنین شرایطی برای همکاری های علمی هم مشاهده شده است(شکل 7.6a).

شبکه های غیر همساز
در شبکه های غیر همساز، هاب ها تمایل دارند به گره ها با درجه پایین متصل شوند. درنتیجه k_nn(k) با کاهش k کاهش می یابد درست شبیه چیزی که برای شبکه متابولیک ( شکل 7.6c) مشاهده شد.

شکل 7.6
تابع همبستگی درجه ای
تابع همبستگی درجه ای k_nn(k) برای سه شبکه واقعی. نمودارها k_nn(k) بصورت نمودار log⁡log⁡ نشان می دهند تا قانون مقیاس را آزمایش کنند.

شبکه برهم کنش
افزایش k_nn(k) با k نشان می دهد که شبکه همساز است.

شبکه برق
در راستای رابطه (7.9) برای شبکه های عصبی k_nn(k) افقی نشان می دهد ارتباط درجه ای وجود ندارد،.

شبکه متابولیک
k_nn(k) کاهشی، طبیعت غیرهمساز بودن شبکه را نشان می دهد.

در هر نمودار، خط عمودی، پیش بینی طبق رابطه () را نشان می دهد و خط چین سبز هم طبق رابطه (7.10 ) رسم شده است.

رفتاری که در شکل 7.6 مشاهده شد. ما را بر آن داشت تا تابع همبستگی درجه ای را طبق [4] تخمین بزنیم.
$k_{nn} (k) = ak^\mu \hspace{20 mm} (7 . 10)$
اگر مقیاس بندی (7.10) برقرار باشد، نوع هبستگی درجه ای با علامت توان همبستگی (μ) مشخص می شود.

شبکه های همساز μ>0
با رسم برازش k_nn(k) برای شبکه همکاری های علمی μ=0.37±0.11 بدست می آِید(شکل 7.6a).

شبکه عصبی μ=0
طبق رابطه (7.9)، k_nn(k) مستقل از k است. به علاوه برای شبکه برق μ=0.04±0.05 بدست می آید تقریبا برابر صفر است(شکل 7.6b).

شبکه های غیر همساز μ<0 < 0
برای شکبه متابولیک μ=0.76±0.04 دست می آید (شکل 7.6c).

نکته 7.1
تناقض دوستی

تناقض دوستی نکته جالبی را بیان می کند: بطور میانگین، دوستان من بیشتر از من معروف هستند [6,7]. این ادعا از رابطه (7.9) سرچشمه می گیرد. این رابطه به ما می گوید میانگین درجه های همسایه های یک گره 〈k〉 نیست اما به〈k² 〉 بستگی دارد

شبکه تصادفی که در آن 〈k² 〉=〈k〉(1+〈k〉)را در نظر بگیرید.طبق رابطه (7.9) خواهیم داشت k_nn(k)=1+〈k〉. بنابراین میانگین درجه همسایه های یک گره از درجه گره ای که به طور تصادفی انتخاب شده است (〈k〉) بیشتر است.

اختلاف بین 〈k〉 و درجه دوستانمان در شبکه های بدون مقیاس بیشتر خواهد بود زیرا در این شبکه ها داریم 〈k〉²⁄〈k〉 که بطور واضح از بیشتر می شود(شکل 4.8). برای مثال شبکه بازیگران را درنظر بگیرید، در این شبکه 〈k〉²⁄〈k〉 =565 (جدول 4.1). در این شبکه میانگین درجه دوستان یک گره هزاران برابر درجه خود گره است.

تناقض دوستی، اصل ساده ای دارد: ما بیشتر تمایل داریم با هاب ها دوست باشیم تا گره هایی با درجه کم زیرا هاب ها ازگره های کوچک دوستان بیشتری دارند.

بطور خلاصه هم بستگی درجه ای به ما کمک می کند وجود یا عدم وجود همبستگی را در شبکه های واقعی پیدا کنیم. تابع k_nn (k) نقش بسیار مهمی در محاسبات تحلیلی ایفا می کند که به کمک آن می توانیم تاثیر هبستگی درجه در شبکه هایی با ویژگی ها متنوع پیش بینی کنیم(بخش 7.6). با این وجود، استفاده از یک عدد واحد برای ثبت میزان همبستگی های موجود در شبکه، بسیار راحت است. این عدد را می توان از توان همبستگی μ که در رابطه (7.10) تعریف شده است یا از ضریب همبستگی درجه ای که در نکته (7.2) بیان شده بدست آورد.

نکته 7.2
ضریب همبستگی درجه ای

اگر بخواهیم همبستگی درجه ای را با استفاده از یک عدد مشخص کنیم، می توانیم از μ یا ضریب توزیع درجه استفاده کنیم. طبق تعریف مارک نیومن در [8,9] ، ضریب توزیع درجه بصورت زیر بیان می شود.

که در آن
$\sigma ^2 = \sum\limits_k {k^2 q_k - \left[ {\sum\limits_k {kq_k } } \right]} ^2 \hspace{20 mm} (7 . 12)$
بنابراین r ضریب همبستگی درجه ای بین درجه های دو گره ای است که دو سر یک پیوند قرار دارند. مقدار r بین -1≤r≤1 متغییر است: برای r<1 شبکه، همساز است، برای r=0 شبکه خنثی است و برای r>0 شبکه غیر همساز است. برای مثال برای شبکه همکاری علمی r=0.13 بدست می آید که متناسب با خاصیت همساز بودن آن است. برای شبکه برهم کنش پروتئینی r=-0.04 بدست می آید که خاصیت غیر همساز بودن آن را تایید می کند و برای شبکه برق هم r=0 است.

فرض پشت ضریب همبستگی درجه ای این است که k_nn (k) بصورت خطی با شیب r به k بستگی دارد. در مقابل توان همبستگی μ فرض می کند k_nn (k) از قانون توان رابطه (7.10) پیروی می کند. همانطور که در مباحث پیشرفته 7.A نشان خواهیم داد، بطور کلی بین rو μ همبستگی وجود دارد.

بخش 7.4
برش های ساخت یافته

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

در شبکه های ساده تناقض گیج کننده ای بین ویژگی بدون مقیاس بودن و همبستگی درجه ای وجود دارد [10, 11]. برای مثال شبکه بدون مقیاس شکل 7.7a را در نظر بگیرید که در آن دو هابی که از همه بزرگتر هستند درجه هایk=55 وk’=46 دارند. در شبکه ای با همبستگی درجه ای e_kk' تعداد مورد انتظار پیوند بین k و k’ مطابق رابطه زیر می باشد.
$E_{kk'} = e_{kk'} \left\langle k \right\rangle N \hspace{20 mm} (7 . 13)$
برای شبکه های عصبی e_(kk^' ) طبق رابطه (7.5) بدست می آید که با استفاده از رابطه (7.3) پیش بینی می کند که:

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

برای kوk’ های کوچک، رابطه (7.14) مقدار E_kk' را هم کم پیش بینی می کند. برای مثال ما انتظار داریم کمتر از یک پیوند بین دو گره وجود داشته باشد. تنها برای گره هایی که درجه آن ها از حد آستانه k_s بیشتر شود رابطه (7.14) چند پیوند را بین آنها پیش بینی می کند. همانطور که در مباحث پیشرفته 7.B نشان می دهیم، k_s که به آن برش ساخت یافته می گویند بصورت زیر مقیاس بندی می شود.

به عبارت دیگر، گره هایی که درجه آنها از رابطه (7.15) تجاوز می کند E_kk'>1 خواهند داشت. درنتیجه تناقضی که در زیر نشان می دهیم برای همبستگی درجه ای پیش خواهد آمد.
$k_s (N) \sim \left( {\left\langle k \right\rangle N} \right)^{1/2} \hspace{20 mm} (7 . 15)$

شکل 7.7
غیر همسازی ساخت یافته

• شبکه بدون مقیاس با N=300، L=450 و y=2.2 با مدل ساختاری (شکل 4.15) ایجاد شده است. با حذف طوقه ها و پیوند های چندگانه، شبکه ساده ای خواهیم داشت. دو گره ای که از همه بزرگتر هستند را مشخص می کنیم. همانطور که رابطه (7.14) پیش بینی می کند برای حفظ خاصیت خنثی بودن شبکه به طور تقریبی 3 پیوند بین این دو گره نیاز داریم. این واقعیت که از پیوند های چندگانه جلوگیری می کنیم(نمایش شبکه ساده) باعث می شود شبکه غیر همساز باشد، همان پدیده ای که به آن غیر همسازی ساخت یافته می گویند.

برای نشان دادن مبدا همبستگی های ساختاری از دنباله درجه ثابتی شروع می کنیم که بصورت تکه های منفرد در سمت چپ نشان داده شده اند. در ادامه بطور تصادفی تکه ها را به هم متصل می کنیم (مدل ساختاری). در این مورد تعداد پیوند های مورد انتظار بین گره های با درجه 8 و 7 8×7/28=2 است. با این حال اگر پیوند های چندگانه مجاز نباشد، این دو گره با یک پیوند به هم متصل می شوند و باعث می شوند که شبکه بصورت ساختاری غیرهمساز باشد.

به عبارت دیگر، گره هایی که درجه آنها از رابطه (7.15) بیشتر می شود دارند که در نتیجه آن تناقضی که در زیر به آن اشاره می کنیم در رابطه با همبستگی درجه ای بوجود خواهد آمد.

برای درک نتایج برش ساختاری اول باید بررسی کنیم آیا شبکه گره هایی دارند که درجه آنها از رابطه (7.15) بیشتر شود. برای این منظور برش ساختاری (k_s) را با برش طبیعی که انتظار می رود بزرگترین درجه در شبکه باشد (k_max) مقایسه می کنیم. طبق رابطه (4.18) برای شبکه های بدون مقیاس k_max ~ N^1/y-1. با مقایسهk_s و k_max بین دو نظام می توانیم تمایز قائل شویم.

هیچ برش ساختاری وجود نداشته باشد
برای شبکه های تصادفی و شبکه های بدون مقیاس با γ≥3 توان k_max کمتر از 2/1 است، بنابراین k_max همیشه کوچکتر از k_s است. به عبارت دیگر سایزی از گره که در آن برش ساختاری فعال می شود از سایز بزرگترین هاب تجاوز می کند. در نتیجه هیچ گره ای نداریم که در آن E_kk' > 1 . برای این شبکه ها تناقضی بین همبستگی درجه ای و شرایط شبکه های ساده وجود ندارد.

غیر همسازی ساختاری
در شبکه های بدون مقیاس با γ<3داریم 1/(γ-1)>1/2 . برای مثال k_s می تواند از k_max کوچکتر باشد. بنابراین گره هایی که درجه آنها بین k_s و k_max است می توانند از E_kk' > 1 پی روی نکنند.ب به عبارت دیگر تعداد پیوند ها بین هاب های شبکه کمتر از تعداد پیش بینی شده در رابطه (7.14) می باشد. بنابراین این شبکه ها می توانند غیر همساز باشند، پدیده ای که آن را غیرهمسازی ساختاری می نامیم. این موضوع در شکل 7.8 a,b, نشان داده شده. این شکل شبکه بدون مقیاس ساده ای را که به وسیله مدل ساختاری ایجاد شده را نشان می دهد. شبکه به رغم عدم القای همبستگی درجه ای در طی ساخت، مقیاس بندی غیر همساز را نشان می دهد.

شکل 7.8
برش های طبیعی و ساختاری
این شکل تنش بین ویژگی بدون مقیاس بودن و ارتباطات درجه ای را نشان می دهد. توزیع درجه(نمودار سمت چپ) و تابع ارتباطات درجه ای k_nn(k) (نمودار سمت راست) را برای شبکه بدون مقیاس با N=10000 و γ=2.5 که توسط بوسیله مدل ساختاری تولید شده را نمایش می دهیم (شکل 4.15).

(a,b) اگر شبکه بدون مقیاس با توزیع درجه قانون- توان که در آن طوقه و اتصال چندگانه ممنوع است و در (a) نشان داده شده را ایجاد کنیم، این شبکه بی نظمی ساختاری را نشان می دهد که در b با k_nn(k) نشان داده شده است. در این حالت به اندازه ای که برای حفظ ذات طبیعی شبکه مورد نیاز است، بین گره های با درجه بالا اتصال وجود ندارد بنابراین برای k های بزرگ تابع k_nn(k) کاهش می یابد.

(c,d) با فراهم کردن آنچه شبکه به آنها نیاز دارد می توان بی نظمی ساختاری را کاهش داد، برای می توان اجازه داد بین دو گره اتصال چندگانه وجود داشته باشد. همانطور که در (c,d) نشان داده شده است، با اضافه کردن این امکان به شبکه های بدون مقیاس خنثی می رسیم.

(e,f) اگر با حذف گره هایی که در آنها طبق آنچه در (7.15) پیش بینی کردیم k≥k_s≃100 برش بالایی ایجاد کنیم همانطور که در f دیده می شود شبکه خنثی ایجاد خواهد شد.

به دو طریق می توان شبکه هایی ایجاد کرد که بی نظمی ساختاری ندارند:

می توان روی ویژگی های شبکه های ساده سخت گیری نکرد و اجازه داد چند پیوند بین گره ها وجود داشته باشد. در این صورت تناقضات برطرف می شوند و شبکه ها خنثی خواهند شد(شکل 7.8C,d).

اگر بر داشتن شبکه های مقیاس آزاد یا مجموعه ای اصرار دشته باشیم، باید تمام های هایی که درجه آنها ازk_s بیشتر است را حذف کنیم. این مساله در شکل 7.8e,f. نشان داده شده است: شبکه ای است که گره ای با در جه k≥100 در آن وجود ندارد و طبعا خنثی است.

در نهایت چطور می توان فهمید که همبستگی های مشاهده شده در بعضی از شبکه ها ماحصل بی نظمی ساختاری است یا در نتیجه بعضی از فرآِندهای ناشناخته ایجاد می شود که نتیجه آنها همین همبستگی بین درجات است؟ تصادفی سازی درجه-حفاظت (شکل 4.17) در تمایز قائل شدن بین این دو احتمال کمک می کنند:

تصادفی سازی حفظ درجه با پیوند های ساده (R-S)
تصادفی سازی درجه-حفاظت را به شبکه اصلی اعمال می کنیم و در هر گام باید اطمینان حاصل شود که اجازه ایجاد بیش از یک پیوند بین یک زوج گره وجود ندارد. از دید الگوریتمی باید گفت که هر پیوندی که ایجاد می شود در صورتی که پیوند چندگانه ایجاد کند، حذف می شود. اگر k_nn(k) و k_nn^R-S(k) قابل تمیز از یکدیگر نباشند، بدین معنی است که تمام همبستگی های ایجاد شده در شبکه های واقعی، ساختاری هستند و تماما به واسطه توزیع درجه قابل توضیح و توجیه هستند. در صورتی که k_nn^R-S(k) تصادفی همبستگی درجه ای را نشان ندهد در حالیکه k_nn(k) این همبستگی درجه ای را به تصویر بکشد بدین معنی است که فرآیند های دیگری عامل ایحاد همبستگی درجه ای هستند.

تصادفی سازی حفظ درجه با لینک های چندگانه (R-M)
گاهی برای بررسی خود سازگاری می تواند از تصادفی سازی حفظ درجه ای که پیوند چندگانه در آن مجاز است استفاده کنیم. از دید الگوریتمی بدین معنی است که هر پیوندی بین گره ها حتی اگر پیوند چندگانه ایجاد کند مجاز است. این فرآیند تمام همبستگی های درجه ای را حذف می کند.

تصادفی سازی ای که پیش تر در مورد آن بحث شد را برای سه شبکه واقعی اجرا کردیم. همانطور که شکل7.9a. نشان می دهد، ماهیت پیوند زوج گره ها در شبکه همکاری علمی در اثر هر دو روش تصادفی سازی از بین می رود. این مساله بیان می کند که همبستگی پیوند ها در شبکه همکاری علمی به ماهیت مقیاس آزاد بودن آن مرتبط نیست. در مقابل در شبکه متابولیک ماهیت پیوند های ناگزیده با اعمال R-S بدون تغییر باقی می ماند(شکل 7.9c). در نتیجه پیوند ناگزیده ذر شبکه متابولیک، ساختاری است و در نتیجه توزیع درجه آن ایجاد می شود.

شکل 7.9
تصادفی سازی و همبستگی درجه ای
برای کشف پیدایش همبستگی درجه ای مشاهده شده، باید k_nn(k) (نماد طوسی)، k_nn^R-S(k) وk_nn^R-M(k) که بعد از تصادفی سازی حفظ درجه بدست آمده اند را با هم مقایسه کرد. هر دو روش تصادفی سازی حفظ درجه در این مطالب زیادی برای آموزش دارند:

تصادفی سازی با پیوند های ساده (R-S):
در هر گام از فرآیند تصادفی سازی، بررسی می کتیم بین هیج دو گره ای بیش از یک پیوند وجود نداشته باشد.

تصادفی سازی با پیوند های چندگانه(R-M):
در فرآیند تصادفی سازی پیوند های چندگانه مجاز است.

این دو روش تصادفی سازی را روی شبکه های شکل 7.6 اعمال کردیم. فرآیند R-M همیشه شبکه های خنثی ایجاد می کند، در نتیجه k_nn^R-M(k) همیشه افقی است. وقتی k_nn(k) را با k_nn^R-S(k) مقایسه کنیم دید صحیحی بدست می آید که به کمک آن می توان تصمیم گرفت آیا همبستگی مشاهده شده ساختاری است:

شبکه همکاری علمی
در این شبکه k_nn(k) صعودی با k_nn^R-S(k) متفاوت است که نشان می دهد پیوند های ناگزیده در شبکه، ساختاری نیستند. در نتیجه پیوند های گزیده در اثر فرآیندهایی ایجاد می شوند که مسئول رشد شبکه هستند. این اتفاق دور از انتظار نیست: تاثیرات ساختاری تنها می توانند پیوند های ناگزیده ایجاد کنند نه پیوند های گزیده.

شبکه برق
k_nn(k) افق، k_nn^R-S(k) و k_nn^R-M(k) نقص همبستگی درجه ای را پشتیبانی می کند (شبکه های خنثی).

شبکه متابولیک
از آنجایی که هم k_nn(k) و هم k_nn^R-S(k) کاهشی هستند نتیجه می گیریم ناگزیدگی درجه ها، ماحصل خاصیت مقیاس آزاد بودن آنهاست. در نتیجه همبستگی درجه ای مشاهده شده ساختاری است.

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

بخش 7.5
همبستگی ها در شبکه های واقعی

برای آنکه تاثیر همبستگی درجه ای را روی ویژگی های شبکه های متنوع بررسی کنیم، باید همبستگی ای که به عنوان ویژگی شبکه به حساب می آید و تا کنون درباره آن صحبت کردیم را بشناسیم. در Image 7.10 تابع k_nn(k) برای 10 شبکه مرجع نشان داده شده است که هر کدام الگوهای متفاوتی دارند:

شبکه برق:
در شبکه برق k_nn(k) مسطح است و تفاوتی با نمونه تصادفی نداردکه بیانگر عدم همبستگی درجه ای است(شکل 7.10a). بنابراین شبکه برق خنثی است.

اینترنت
به ازای درجه های پایینk≤30 تابع k_nn(k) به وضوح رویکرد گزیده را نشان می دهد، اثری که برای درجه های بالاتر به مرور کاهش پیدا می کند (شکل 7.10b). همبستگی درجه ای در نمونه تصادفی نقشه اینترنت از بین می رود. بنابراین اینترنت پیوند های گزیده دارد اما برش های ساختاری در درجه های بالا این تاثیر را حذف می کند.

شبکه های اجتماعی
سه شبکه ای که تعاملات اجتماعی را نشان می دهند، شبکه تلفن های همراه، شبکه همکاری علمی و شبکه بازیگران، همه k_nn(k) صعودی دارند که بیانگر گزیده بودن پیوند ها است (شکل 7.10c-e). بنابر این در این شبکه ها هاب ها تمایل دارند به هاب های دیگر متصل شوند و گره های با درجه پایین تمایل دارند یه سایر گره ها با درجه پایین متصل شوند. این حقیقت که k_nn(k) با k_nn^R-S(k) متفاوت است نشان می دهد که ماهیت گزینشی بود شبکه های اجتماعی به خاطر توزیع درجه مقیاس آزاد بودن آنها نیست.

شبکه پست الکترونیکی
از آنجایی که گاهی شبکه پست الکترونیکی به عنوان شبکه های اجتماعی در نظر گرفته می شوند، k_nn(k) آن یا k کاهش پیدا می کند و نشان دهنده رفتار ناگزیدنی است(شکل 7.10f). k_nn^R-S(k) تصادفی هم کاهش پیدا می کند که بیان کننده پیوند های ناگزیدنی ساختاری در اثر ماهیت مقیاس آزاد بودن شبکه است.

شبکه بیولوژیکی
شبکه برهم کنش پروتئینی و شبکه متابولیک، هر دو μ منفی دارند و پیشنهاد می کند که این ها شبکه هایی با پیوند های ناگزیدنی هستند. با این حال، با تغییر مقیاس، k_nn^R-S(k) از k_nn(k) قابل تمیز نخواهد بود. همین مساله نشان می دهد که ما شاهد ناگزیدنی ساختاری هستیم که از ماهیت مقیاس آزاد بودن این شبکه ها نشات می گیرد (شکل 7.10h,g).

وب
k_nn(k) کاهشی نشان دهنده همبستگی ناگزیدنی است (شکل 7.10i). k_nn^R-S(k) تصادفی هم کاهش پیدا می کند اما با سرعتی کمتر از k_nn(k). بنابراین ماهیت ناگزیدنی بودن وب با توزیع درجه آن توجیه پذیر نیست.

شبکه ارجاعات
این شبکه رفتار های گیج کننده ای نشان می دهد: در k≤20 تابع همبستگی درجه ای k_nn(k) به وضوح رویکرد گیزیدنی بودن را نشان می دهد؛ k>20 مقیاس بندی ناگزیدنی را نشان می دهند (شکل 7.10j). این رفتار های متنوع در شبکه هایی که پیوند های گزیدنی شدید دارند ظاهر می شود، اما ماهیت مقیاس آزاد بودن آنها ناگزیدنی بودن ساختاری را القا می کند و باعث تغییر شیب k_nn(k) برای k >> k_s می شود.

شکل 7.10
تصادفی سازی و همبستگی درجه ای
تابع هم بستگی درجه ای k_nn (k) مربوط به شبکه های مرجع (جدول 4.1). علامت های طوسی، نشان دهنده تابع k_nn(k) با استفاده از نمایش خطی است؛ دایره های بنفش، داده های مشابه را با نمایش لگاریتمی نشان می دهد( بخش 4.11). خط چین سبز هم بهترین برازش برای (7.10) را در بازه ای که در شکل به وسیله فلش ها تعیین شده اند را نشان می دهد. مربع های نارنجی رنگ هم k_nn^R-S(k) را برای 100 تا تصادفی سازی حفظ درجه مستقل را نشان می دهد در حالی که ویژگی های ساده ای شبکه ها را حفظ می کند. دقت کنید که هنگام اندازه گیری k_nn(k) شبکه های جهت دار را به شبکه های بدون جهت تبدیل کردیم. برای اینکه تمام ویژگی های همبستگی ظاهر شده در شبگه های جهت دار مشخص کنیم، باید از تابع همبستگی جهت دارد استفاده کنیم(نکته 7.3).

بطور خلاصه، شکل 7.10 نشان می دهد که برای پیدا کردن همبستگی درجه ای همیشه باید k_nn(k) را با درجه تصادفی شده k_nn^R-S(k) مقایسه کنیم. به علاوه می توانیم چند تا نتیجه گیری جالب هم داشته باشیم:

در بین ده شبکه مرجع، شبکه برق تنها شبکه ای است که حقیقاتا خنثی است. بنابراین بیشتر شبکه های واقعی همبستگی درجه ای دارند.

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

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

مکانیزم های زیادی برای شرح پیدایش گزیدنی بودن پیوند ها در شبکه های ارائه شده اند. برای مثال، تمایل افراد به تشکیل انجمن ها که در فصل 9 به آن پرداخته شده است می تواند عامل ایجاد همبستگی های گزینشی باشد[12]. همچنین جامعه مکانیزم های نامحدودی از انجمن ها تخصصی گرفته تا نمایش های تلویزیونی برای جمع کردن هاب ها دور هم دارد تا ماهیت گزیدنی بودن شبکه های تخصصی و اجتماعی را ارتقا دهد. در نهایت، هموفیلی به عنوان پدیده اجتماعی است که به خوبی مستند سازی شده است[13]،نشان می دهد که افراد تمایل دارند با افراد دیگری که گذشته و ویژگی های مشابه دارند در اتباط باشند، بنابر این افرادی که درجه آنها نزدیک به هم است تمایل دارند با هم ارتباط برقرار کنند. این هموفیلی درجه می تواند همان عامل موثر در ازدواج افراد معروف با یکدیگر باشد(شکل 7.1).

نکته 7.3
همبستگی ها در شبکه های جهت دار

تابع همبستگی درجه ای(7.7) برای شبکه های بدون جهت تعریف شده است. برای اندازه گیری همبستگی ها در شبکه های جهت دار باید در نظر داشته باشیم که هر گره i به واسطه درجه ورودی k_iⁱⁿ و درجه خروجی k_i^out مشخص می شود[14].. به همین دلیل چهار تابع همبستگی درجه ای تعریف کردیم، k_nn^(α,β) (k) که در آن αوβ اندیس های ورودی و خروجی را نشان می دهند(شکل 7.11a-d). در شکل 7.11e، k_nn^(α,β) (k) برای شبکه ارجاعات علمی نشان داده شده است که عدم همبستگی ورودی و خروجی و گزیدنی بودن به ازای kهای کوچک برای سه همبستکی دیگر را نشان می دهد.

شکل 7.11
همبستگی ها در شبکه های جهت دار

(a)-(d) چهار همبستگی ممکن که شبکه های جهت دار را توصیف می کنند. اندیس های αوβ را که تابع همبستگی مناسب را تعریف می کنند با بنفش و سبز نشان داده شده اند [14].. برای مثال a همبستگی k_nn^in,in(k) که همان همبستگی بین درجه های ورودی دو گره متصل به هم است را نشان می دهد.

(e) تابع همبستگی k_nn^(α,β) (k) شبکه ارجاعات علمی که شبکه ای جهت دار است. برای مثال k_nn^in,in(k) میانگین درجه ورودی همسایه هایی است که پیوند آنها با گره مربوطه ورودی به این گره است و درجه ورودی آنها هم k_in است.

بخش 7.6
ایجاد شبکه های هم بسته

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

همبستگی های درجه ای در مدل های ایستا

مدل اردوش- رینی
طبق تعریف، مدل شبکه تصادفی خنثی است. از آنجایی که هاب ندارد، همبستگی ساختاری نخواهد داشت. k_nn(k) برای مدل اردوش رینی در فرمول (7.9) محاسبه شده است که برای هر 〈K〉 و N پیش بینی می کند μ=0.

مدل پیکربندی
مدل پیکربندی (شکل 4.15) هم مستقل از توزیع درجه p_k انتخاب شده، خنثی است. علت آنهم مجاز بودن پیوند های چندگانه و طوقه است. در نتیجه هر تناقضی که در اثر وجود هاب ها ایجاد شده باشد با پیوند های چندگانه بین آنها حل می شود. به هر حال اگر مجبور کنیم که شبکه ها ساده باشند، در شبکه ایجاد شده، پیوند ناگزیده ساخت یافته ایجاد خواهد شد(شکل 7.8).

مدل پارامتر های پنهان
در این مدل e_jk متناسب با حاصلضرب متغیرهای نهانی که به تصادف انتخاب شده اند یعنی η_j η_k است(شکل 4.18). در نتیجه، شبکه از نظر تکنیکی هم نامرتبط خواهد بود. هرچند اگر پیوند های چندگانه مجاز نباشد، باز هم برای شبکه های مقیاس آزاد پیوند های ناگزدنی ساختاری را شاهد خواهیم بود. محاسبات تحلیلی تایید می کنند که در این نمونه خواهیم داشت[18]
$k_{nn} (k) \sim k^{ - 1} \hspace{20 mm} (7 . 16)$
برای مثال تابع همبستگی درجه ای از (7.10) پیروی می کند در حالیکه μ=1 .

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

هم بستگی درجه ای در شبکه های در حال توسعه

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

مدل کشش اولیه
شبکه در حال رشد با الحاق ترجیحی را در نظر بگیرید که از فرمول (6.23) تبعیت می کند. برای مثال Π(k)~A+k که در آن A همان کشش اولیه است. بسته به مقدار A شاهد سه وضعیت متفاوت مقیاس بندی خواهیم بود:

وضعیت ناگزیدنی: γ<3
اگر -m داریم $k_{nn} (k) \sim m\frac{{(m + A)^{1 - \frac{A}{m}} }}{{2m + A}}\zeta \left( {\frac{{2m}}{{2m + A}}} \right)N^{\frac{A}{{2m + A}}} k^{\frac{A}{m}} \hspace{20 mm} (7 . 17)$ بنابراین شبکه حاصل ناگزیدنی خواهد بود و k_nn(k) قانون توان زیر را کاهش می دهد [15, 16]. $k_{nn} (k) \sim k^{\frac{{|A|}}{m}} \hspace{20 mm} (7 . 18)$

وضعیت خنثی: γ=3
اگر A=0 باشد، کشش اولیه مدل آلبرت باراباشی را کاهش می دهد. در این حالت $k_{nn} (k) \sim \frac{m}{2}\ln N \hspace{20 mm} (7 . 19)$ در نتیجه k_nn(k) مستقل از k است، درنتیجه شبکه خنثی است.

گزیدنی ضعیف: γ>3 اگرA>0 باشد محاسبات پیش بینی می کنند که:
$k_{nn} (k) \approx (m + A)\ln \left( {\frac{k}{{m + A}}} \right) \hspace{20 mm} (7 . 20)$ همچنان که k_nn(k) بصورت لگاریتمی با افزایش k افزایش می یابد، در شبکه حاصل هم رویکرد گزینشی بودن ضعیف هم ایجاد می شود ولی از فرمول (7.10) پیروی نمی کند.

بطور خلاصه، (7.17)-(7.20) نشان می دهند که مدل کشش اولیه همبستگی درجه ای نسبتا پیچیده ای ایجاد می کند، از ناگزیدنی بودن تا گزیدنی بودن ضعیف. همچنین معادله (7.19) نشان می دهد که شبکه ایجاد شده به وسیله مدل آلبرت-باراباشی، خنثی است. در نهایت معادله (7.17)قانون توان k-مستقل را برای k_nn(k) پیش بینی می کند که تاییدی تحلیلی برای مقیاس بندی تجربی است(7.10).

مدل بیانکونی-باراباشی
با توزیع برازش یکنواخت، مدل بیانکونی-باراباشی، شبکه ای نا گزینشی ایجاد می کند[5] (شکل 7.12). این حقیقت که نسخه تصادفی شبکه هم ناگزینشی است، نشان می دهدکه ناگزینشی بودن مدل، ساختاری است. توجه کنید که k_nn(k) واقعی و k_nn^R-S(k) تصادفی همپوشانی ندارند که نشان می دهد ناگزینشی بودن مدل تماما به وسیله ماهیت مقیاس آزاد بودن آن توجیه پذیر نیست.

شکل 7.12
همبستگی در مدل بیانکونی-باراباشی
تابع همبستگی درجه مدل بیانکونی-باراباشی برای N=10000، m=3 و توزیع برازش یکنواخت (بخش 6.2). همانطور که خط نقطه چین سبز رنگ نشان می دهد طبق فرمول (7.10)، شبکه ناگزینشی، پایدار با μ≃-0.5 است. نمادهای نارنجی نشان دهنده k_nn^(R-S) (k) هستند و از آنجایی که k_nn^R-S(k) کاهش می یابد ناگزینشی بودن آن ساختاری است. اما تفاوت بین k_nn^R-S(k) و k_nn(k) نشان می دهدکه اثرات ساختاری تنها عوامل موثر در همبستگی درجه ای نیستند.

تنظیم همبستگی درجه ای

الگوریتم های زیادی برای ایجاد شبکه هایی با همبستگی درجه ای مورد نظر وجود دارند [8, 17, 18]. در ادامه نسخه ساده شده الگوریتمی که توسط زالوی-برونت و سوکولو ارائه شده است را توضیح می دهیم. هدف این الگوریتم ایجاد شبکه هایی با بیشترین بیشترین همبستگی درجه ای براساس دنباله درجه از پیش تعیین شده است[19, 20, 21]. این الگوریتم شامل گام های زیر است(شکل 7.13a):

گام 1: انتخاب اتصال
بطور تصادفی دو پیوند انتخاب کنید. چهار گره دو سر این پیوند ها را با a,b,c,d برچسب گذاری کنید بطوری که درجه آنها بصورت زیر مرتب شده باشد: $k_a \ge k_b \ge k_c \ge k_d$

گام 2: اتصال مجدد
پیوند های قبلی را حذف کنید و آنها را مجددا طوری به هم وصل کنید که زوج های جدیدی تشکیل شوند. بسته به همبستگی درجه مورد نظر دو روش برای اتصال مجدد وجود دارد:

گام 2A: گزینشی
دو گره ای که بزرگترین درجه را دارند به هم (A به B)و دو گره ای که کوچکترین درجه را دارند (Cیه D)به یکدیگر متصل کنید. با این کار گره هایی که درجه آنها نزدیک هم هستند به هم متصل می شوند و در نتیجه ماهیت گزینشی بودن شبکه را تقویت می کنند.

گام 2B: نا گزینشی
گره ای که بزرگترین درجه را دارد به گره ای که کوچکترین درجه را دارد متصل کنید(گره a به dو bبه c). در این صورت گره هایی که درجه های متفاوت دارند به هم وصل می شوند و ماهیت ناگزینشی بودن شبکه را تقویت می کنند.

شکل 7.13
الگوریتم زولوی-برونت و سوکولوو

این الگوریتم شبکه هایی با همبستگی درجه ای بیشینه تولید می کند

(a)گام های بنیادی الگوریتم

(b) k_nn(k) برای شبکه های ایجاد شده با این الگوریتم، شبکه مقیاس آزاد با N=1000، L=2500، γ=3.0

(c, d) پیکربندی شبکه های معمول و ماتریس A_ijمربوط به شبکه ای با بیشینه گزینشی که توسط این الگوریتم ایجاد شده است. سطرها و ستون های A_ij از کم به گره ای با درجه k به ترتیب صعودی مرتب شده اند.

(e,f) همانند (c,d) برای شبکه گزینشی بیشینه

ماتریس های (d) و (f) نظم درونی شبکه ها با بیشینه همبستگی را نشان می دهد. این نظم درونی شامل بلوک هایی از گره هاست که به گره هایی با درجه ورودی مشابه(d) متصل می شوند و بلوک هایی از گره ها که به گره هایی با درجه ورودی نسبتا متفاوت (f)متصل می شوند.

با تکرار این گام ها، به مرور ویژگی گزینشی بودن ( گام 2A) یا ناگزینشی بودن (گام 2B) شبکه ها را تقویت می کنیم. اگر بخواهیم شبکه ساده ای ایجاد کنیم(بدون پیوند های چندگانه)، بعد از گام دوم بررسی می کنیم که اتصالات جدیدی باعث ایجاد پیوند چندگانه می شود یا خیر، اگر مثبت بود آن را رد می کنیم و به گام اول بر می گردیم.

همبستگی هایی که ویژگی های شبکه ایجاد شده توسط این الگوریتم را تعیین می کنند یا به سمت مقدار بیشینه (گزینشی) یا مقدار کمینه (ناگزینشی) سوق پیدا می کند و در نهایت می توانیم به دنباله درجه مورد نظر برسیم ( شکل 7.13b). این مدل هیچ مشکلی برای ایجاد همبستگی های ناگزینشی ندارد(شکل 7.13e-f). در محدوده گزینشی بودن، در شبکه های ساده k_nn(k) ترکیبی خواهد بود: برای k های کوچک گزینشی و برای k های بزرگ ناگزینشی است(شکل 7.13b). این نتیجه برش های ساختاری است. برای شبکه های بدون مقیاس، سیستم نمی تواند در k های بزرگ گزینشی بماند. رفتار مشاهده شده تابع k_nn(k)) در شبکه اراجاعات علمی را به یاد می آورد(شکل 7.10j).

نسخه ای از الگوریتم زالوی-برونت و سوکولو که در شکل 7.13 نشان داده شده است شبکه های گزینشی یا ناگزینشی بیشینه را ایجاد می کند. می توانیم دقت هبستگی درجه ای را با استفاده از الگوریتمی که در شکل 7.14 مورد بحث قرار گرفت، تنظیم کنیم.

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

شکل 7.14
تنظیم همبستگی درجه ای

می توانیم از الگوریتم زالوی-برونت و سوکولوو برای تنظیم دقت همبستگی درجه ای استفاده کنیم.

گام های قطعی مربوط به اتصال مجدد را با با احتمال p اجرا می کنیم و با احتمال 1-p گره های a,b,c,d را به هم متصل می کنیم. برای p=1 همان الگوریتم شکل 7.13 خواهد بود که همبستگی درجه ای بیشینه را ایجاد می کند. برای p<1 نویزی که ایجاد می شود دقت اثر را تنظیم می کند.

ساختار شبکه معمولی برا p=0.5

توابع k_nn(k) برای p های مختلف برای شبکه ای با N=10000، =1 و γ=3.0

بخش 7.7
اثر همبستگی های درجه ای

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

یکی از مهمترین ویژگی های شبکه های تصادفی بوجود آمدن فاز انتقال در =1 است که نشان دهنده بوجود آمدن قطعه غول پیکر است (بخش 3.6). شکل 7.15 سایز حدودی قطعه غولپیکر را برای شبکه هایی با همبستگی درجه متفاوت نشان می دهد که الگوهای متفاوتی هم دارد [8, 19, 20]:

شبکه های گزینشی
در شبکه های گزینشی نقطه انتقال فاز به سمت های کوچکتر می رود، بنابراین قطعه غول پیکر در <1 ظاهر می شود. زیرا اگر گره هایی که درجه بالایی دارند یکدیگر را جستجو کنند تشکیل قطعه غول پیکر ساده تر می شود.

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

قطعه غول پیکر
برای های بزرگ قطعه غول پیکر در شبکه های گزینشی کوچکتر از شبکه های خنثی یا شبکه های ناگزینشی است. درواقع گزینشی بودن باعث می شود هاب ها به یکدیگر متصل شوند درنتیجه نمی توانند تعداد بی شمار گره کوچک را به قطعه غول پیکر جذب کنند.

شکل 7.15
همبستگی درجه ای و نقطه انتقال فاز
سایز نسبی قطعه غول پیکر برای شبکه اردوش-رینی با سایز N=10000 (منحنی سبز رنگ) که با الگوریتم زالوی-برونت و سوکولوو p=0.5 پیوند های آنها مجددا ایجاد شده است تا همبستگی درجه ای ایجاد شود(شکل 7.14). شکل نشان می دهد وقتی از پیوند گزینشی به پیوند ناگزینشی می رویم نقطه انتقال فاز عقب می افتد و اندازه قطعه غول پیکر برای های بزرگ افزایش می یابد. هر نقطه میانگین 10 اجرا را نشان می دهد

این تغییرات در سایز و ساختار قطعه غول پیکر در زمینه گسترش بیماری ها تاثیر گذار است [22, 23, 24] موضوع فصل 10.در واقع همانطور که در شکل 7.10 دیدیم شبکه های اجتماعی تمایل به پیوند های گزینشی دارند. گره های با درجه بالا قطعه غول پیکری تشکیل می دهند که در نقش مخزن بیماری ها عمل می کنند. یعنی باعث ادامه اپیدمی می شود حتی اگر شبکه به طور متوسط به اندازه کافی برای پایداری ویروس چگال نباشد.

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

می خواهیم تعدادی از نتایج همبستگی درجه ای را نام ببریم:

شکل 7.16 توزیع طول مسیر در شبکه تصادفی را نشان می دهد که پیوند های آن برای نشان دادن همبستگی های درجه ای متفاوت تغییر کرده اند. این شکل نشان می دهد که در شبکه های گزینشی، متوسط طول مسیر در شبکه های خنثی کمتر است. تاثیر گذارترین تفاوت در قطر شبکه است، d_max، که بطور چشم گیری در شبکه های گزینشی بیشتر است. به علاوه گزینشی بودن به پیوند میان گره ها با درجه مشابه علاقه دارد، در نتیجه در زنجیره های طولانی با گره های k=2، d_max افزایش می یابد(شکل 7.13c c

همبستگی درجه ای روی پایداری شبکه در مقابل محرک ها و اختلال ها موثر است مثل هماهنگ سازی نواساناتی مه در شبکه اتفاق می افتد[27, 28].

همبستگی درجه ای تاثیر بنیادین روی مساله پوشش راسی دارد [29]. این مساله موضوعی است که بیشتر از سایر موضوعات نظریع گراف مورد مطالعه قرار گرفته است و هدف آن پیدا کردن کوچکترین مجموعه ای از گره هاست(پوشش) که در آن هر پیوند در شبکه حداقل به یکی از گره های این مجموعه متصل باشد(نکته 7.4).

همبستگی درجه ای روی توانایی ما در کنترل شبکه موثر است زیرا با استفاده از آن می توان تعداد سیگنال های ورودی که برای بدست آوردن کنترل کامل نیاز است را جایگزین کرد[30].

شکل 7.16
هم بستگی درجه ای و طول مسیر
توزیع فاصله در شبکه تصادفی با N=10000 و =3. همبستگی ها با استفاده از الگوریتم زالوی-برونت و سوکولوو با p=0.5 ایجااد شده اند(شکل 7.14). نمودار ها نشان می دهند وقتی از شبکه ناگزینشی به شبکه گزینشی می رویم میانگین طول مسیر کاهش می یابد. همانطور که مشخص است قله نمودار هم به مرور به سمت چپ حرکت می کند. همزمان، قطر d_max هم افزایش می یابد. هر کدام از منحنی ها میانگین 10 شبکه مستق را نشان می دهند.

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

شکل 7.17
پوشش کمینه

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

نکته 7و4
پوضض راسی و حراست موزه

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

فرض کنید N تقاطع داشته باشیم و m تعداد نگهبانانی است که باید استخدام کنید. از آنجایی که (^N_m) راه متفاوت برای جایدهی m نگهبان در N تقاطع وجود دارد ولی باز هم بیشتر جایدهی ها بدون هیچ نگهبانی باقی می ماند[31]..

تعداد روش های ممکن برای جایدهی نگهبانان بصورت نمایی از N افزایش می یابد. به علاوه، یکی از 6 مساله NP-کامل مبنا است و به آن مساله پوشش راسی می گویند. پوشش راسی یک شبکه مجموعه ای از گره ها هستند که هر پیوند در شبکه به حداقل یکی از گره های موجود در این مجموعه متصل باشد(شکل 7.17). NP-کامل یعنی هیچ الگوریتم شناخته شده ای وجود ندارد که بتواند پوشش راسی کمینه را سریعتر از بررسی کردن تمام حالت های ممکن پیدا کند. تعداد گره ها در پوشش راسی کمینه به توپولوژی شبکه بستگی دارد که تحت تاثیز توزیع درجه و همبستگی درجه ای قرار دارد[29].

بخش 7.8
خلاصه

اولین بار همبستگی های درجه ای در سال 2001 روی اینترنت توسط رومالو پاستور -ساتوراس ، الکسی وزکوئیز و آلساندرو وسپیگنانی کشف شد[4, 5]. همچنین همین افراد تابع همبستگی درجه ای k_nn(k) و مقیاس بندی (7.10) را معرفی کردند. یک سال بعد کیم اسنیپن و سرجی ماسلوو از p(k_i,k_j) کامل که به ماتریس e_ij مرتبط است استفاده کردند تا ویژگی های همبستگی درجه ای را برای شبکه برهم کنش پروتئینی تعیین کنند[32]. در سال 2003 مارک نیومن ضریب همبستگی درجه ای [8, 9] را به همراه شبکه های گزینشی، خنثی و ناگزینشی معرفی کرد. این اصطلاحات در علم شبکه ریشه دار هستند [13]:

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

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

نکته 7.5
در یک نگاه: همبستگی های درجه ای

ماتریس همبستگی درجه ای e_ij

شبکه های خنثی:
$e_{ij} = q_i q_i = \frac{{k_i p_{k_i } k_j p_{k_j } }}{{\left\langle k \right\rangle ^2 }}$
تابع همبستگی درجه ای
$k_{nn} (k) = \sum\limits_{k'} {k'p(k'|k)}$
شبکه های خنثی:
$k_{nn} (k) = \frac{{\left\langle {k^2 } \right\rangle }}{{\left\langle k \right\rangle }}$
فرضیه مقیاس بندی
$k_{nn} (k) \sim k^\mu$
μ>0: گزینشی
μ>0: گزینشی
μ<0: ناگزینشی

ضریب همبستگی درجه ای
$r = \sum\limits_{jk} {\frac{{jk(e_{jk} - q_j q_k )}}{{\sigma ^2 }}}$
r>0: گزینشی
r=0: خنثی
r<0: ناگزینشی

در مجموع دلایل زیادی وجود دارد که علت توجه به همبستگی های درجه ای در شبکه ها را توجیه می کند(نکته 7.5):

همبستگی درجه ای در اغلب شبکه های واقعی وجود دارد(بخش 7.5).

با ظهور همبستگی درجه ای در هر شبکه ای، رفتار شبکه تغییر می کند(بخش 7.7).

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

شکل 7.18
سیاست هرگز خنثی نیست
شبکه زیرساخت وبلاگستان سیاسی ایالات متحده نشان دهنده وجود پیوند های گزینشی مرکب همانند آنچه در جامعه شناسی استفاده می شود، است. یعنی گره هایی که ویژگی های مشابهی دارند تمایل دارند به هم متصل شوند. در این نقشه هر گره آبی مربوط به وبلاگ اصلاح طلبان و هر گره قرمز نشان دهنده وبلاگ اصولگرایات است. پیوند های قرمز اصول گراها را به هم متصل می کنند و پیوند های آبی اصلاح طلبان را به هم متصل می کنند. پیوند های زرد از اصلاح طلبان به اصولگرایان و پیوندهای بنفش از اصول گرایان به اصلاح طلبان هستند. همانطور که این شکل نشان می دهد تعداد خیلی کمی وبلاگ از دو گروه متفاوت با هم مرتبط هستند که نشان دهنده گزینشی بودن شدید وبلاگستان سیاسی می باشد [33].

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

در آخر، دراین فصل روی تابع k_nn(k) تمرکز کردیم. این تابع همبستگی درجه ای دو نقطه ای را تعیین می کند. در اصل، همبستگی های درجه ای مرتبه بالا در بعضی از شبکه ها وجود دارند(نکته 7.6). اما تاثیر همبستگی های 3 و 4 نقطه کشف نشده است و باید آنها را هم فهمید.

نکته 7.6
همبستگی های 2نقطه ، 3نقطه

هم بستگی های درجه ای کاملی که ویژگی های شبکه را توصیف می کنند، با احتمالات پایه ای و قدیمی P(k⁽¹⁾, k⁽²⁾, ..., k^(k)|k) تعیین می شوند که در آن گره با درجه k به گره های با درجه k⁽¹⁾, k⁽²⁾, ..., k^(k) وصل می شود.

همبستگی های 2نقطه
ساده ترین همبستگی نقطه 2 در این فصل مورد بحث قرار گرفته است که همان احتمال شرطیP(k'│k) است که یک گره با درجه k به گره ای با درجه k’ متصل می شود. در شبکه هایی که مبتنی بر همکاری نیستند، این احتمال شزطی مستقل از k است. برای مثال P(k'│k)=k^{' p}_k'/〈k〉[18]. از انجایی که ارزیابی تجربی P(k'│k) در شبکه های واقعی دشوار است، تحلیل تابع همبستگی k_nn(k) که در (7.7) ارائه شده است کاربردی تر است.

همبستگی های 3 نقطه
همبستگی هایی که شامل 3 نقطه هستند با P(k⁽¹⁾,k⁽²⁾|k)تعیین می شوند. این احتمال شرطی به ضریب خوشه بندی مرتبط است. به علاوه، ضریب خوشه بندی میانگین C(k) [22, 23] را می توان بصورت احتمال اتصال گره با درجه k به گره هایی با درجه k⁽¹⁾ و k⁽²⁾ نوشت
$C(k) = \sum\limits_{k^{(1)} ,k^{(2)} } {P(k^{(1)} ,k^{(2)} |k)p_{k^{(1)} ,k^{(2)} }^k }$
که در آن p^k_{_{k⁽¹⁾,k⁽²⁾}} احتمال اتصال گره های k⁽¹⁾ و k⁽²⁾ به یکدیگر است که نشان می دهد آنها همسایه مشترکی از درجه k دارند[18]. در شبکه های حنثی C(k) مستقل از k است درنتیجه
$C = \frac{{\left( {\left\langle {k^2 } \right\rangle - \left\langle k \right\rangle } \right)^2 }}{{\left\langle k \right\rangle ^3 N}}$

بخش 7.9
تمرین ها

توازن تفصیلی برای همبستگی درجه ای
احتمال اشتراک e_kk'، احتمال شرطی P(k'│k)و احتمال q_kرا که در این فصل مورد بحث قرار گرفتند را بر اساس پارامترهای N تعداد گره ها، درجه میانگین ،N_k تعداد گره ها با درجه k، و E_kk' تعداد پیوند هایی که گره ها با درجه k و k’ را به هم متصل می کنند، بیان کنید(توجه کنید که وقتی دوبرابر تعداد پیوند هاست). بر اساس تعریف نشان دهید که قانون زیر برای هر شبکه ای برقرار است.
$e_{kk'} = q_k P(k'|k)$

شبکه ستاره ای
شبکه ستاره ای را در نظر بگیرید که در آن یک گره به N-1 گره با درجه یک متصل شده است. فرض کنید N>>1 باشد.

در این شبکه توزیع درجه p_kرا پیدا کنید.

احتمال اینکه یالی که بطور تصادفی انتخاب شده را طی کنیم و در یکی از دو سر آن گره ای با درجه k وجود داشته باشد یعنی q_kرا پیدا کنید.

ضریب همبستگی درجه ای r را برای این شبکه پیدا کنید. برای محاسبات از تعریف های e_kk' و P(k'│k) از تمرین 7.1 استفاده کنید.

این شبکه گزینشی است یا ناگزینشی؟ علت آن را توضیح دهید.

برش های ساختاری
برش ساختاری k_sرا برای شبکه های بدون جهتی که در جدول 4.1آمده اند را محاسبه کنید. براساس شکل 7.10 پیش بینی کنید کهk_s هر کدام از شبکه ها بزرگتر یا کوچکتر از بیشترین درجه k_max مورد انتظار است. با محاسبه k_max صحت پیش بینی خود را ثابت کنید.

همبستگی درجه ای در شبکه های اردوش-رینی
مدل اردوش-رینی G(N,L) مربوط به شبکه های تصادفی را که در فصل 2(نکته 3.1و بخش 3.2) معرفی شده است را درنظر بگیرید که در آن N گره برچسب دارد با L پیوند تصادفی به هم متصل شده اند. در این مدل احتمال اینوه پیوندی گره های iو j را به هم متصل کند به وجود پیوند بین گره های lو s بستگی دارد.

احتمال وجود پیوند بین iو j،e_ijو احتمال شرطی وجود پیوند بین iو j به شرط وحود پیوند بین lوs را بدست آورید.

نرخ این دو احتمال برای شبکه های کوچک چقدر است؟ برای شبکه های بزرگ چطور؟

درصورتی که از مدل اردوش-رینی G(N,P) استفاده کنید، مقادیر بحث شده در (a) و (b) را بدست آورید.

براساس مقادیر بدست آمده در (a)-(c) اثرات استفاده از مدل G(N,L) به جای مدل G(N,P) برای ایجاد شبکه های تصادفی با استفاده از تعداد کمی نود را مورد بحث قرار دهید.

بخش 7.10
مباحث پیشرفته 7.A
ضریب همبستگی درجه ای

در نکته 7.9 ضریب همبستگی درجه ای را به عنوان جایگزیی از همبستگی درجه ای معرفی کردیم[8, 9]. استفاده از تنها یک عد برای تعیین همبستگی درجه ای جذاب است، زیرا با استفاده از آن می توان همبستگی های مشاهده شده در شبکه های مختلف با ماهیت های گوناگون و سایز های مختلف را با هم مقایسه کنیم. با این حال برای استفاده مفید از r باید از نحوه پیدایش آن هم آگاه باشیم.

فرضیه پشت ضریب همبستگی r القا می کند که تابع k_nn(k)می تواند به وسیله تابع خطی زیر تخمین زده شود.
$k_{nn} (k) \sim rk \hspace{20 mm} (7 . 21)$
این با مقیاس بندی (7.10) که قانون توان را مستقل از k درنظر می گیرد، متفاوت است. فرمول (7.21) مسائل زیادی را بیان می کند:

مدل کشش اولیه قانون توان (7.18) یا k-وابستگی لگاریتمی (7.20) را برای تابع هم بستگی درجه ای پیش بینی می کند. قانون توان مشابهی در (7.16) برای مدل پارامتر نهان ارائه شده است. در نتیجه r برازش خطی به تابعی که ذاتا خطی نیست اعمال می کند. شبیه سازی های عدد یا محاسبات تحلیل این وابستگی خطی را توجیه نمی کنند. به علاوه همانطور که در شکل 7.19 نشان دادیم فرمول (7.21) برازش ضعیفی برای داده های شبکه های گزینشی و ناگزینشی ارائه می دهد.

همانطور که در شکل 7.10 دیدیم، وابستگی k_nn(k) به k پیچیده است، زیرا گاهی به ازای k های بزرگ بخاطر برش های ساختاری، رویکرد شبکه تغییر می کند. برازش خطی این پیچیدگی ذاتی را نادیده می گیرد.

در مدل همبستگی بیشینه به رغم آنکه شبکه همبستگی درجه ای اش را حفظ می کند (نکته 7.7)، به ازای N های بزرگ r ناپدید می شود. همین مساله نشان می دهد که ضریب همبستگی درجه ای در تشخیص همبستگی های توصیف کننده شبکه های بزرگ نقص دارد.

شبکه N r μ

اینترنت 192,244 0.02 0.56

وب 325,729 -0.05 -1.11

شبکه برق 4,941 0.003 0.0

تماس های تلفن همراه 36,595 0.21 0.33

پست الکترونیکی 57,194 -0.08 -0.74

همکاری های علمی 23,133 0.13 0.16

شبکه بازیگران 702,388 0.31 0.34

شبکه ارجاعات علمی 449,673 -0.02 -0.18

شبکه متابولیسم 1,039 -0.25 -0.76

شبکه برهم کنش پروتئینی 2,018 0.04 -0.1

جدول 7.1
همبستگی درجه ای در شبکه های مرجع
این جدول r و μ تخمینی برای 10 شبکه مرجع را نشان می دهد. برای اندازه گیری r و μ، شبکه های جهت دار، بی جهت شده اند. در عوض می توانیم از ضریب همبستگی جهت دارد برای این شبکه های جهت دار استفاده کنیم (نکته 7.8).

شکل 7.19
تابع همبستگی درجه ای
تابع همبستگی درجه ای k_nn(k)برای 3 شبکه واقعی. نمودار های سمت چپ تابع تجمعی k_nn(k) را روی نمودار loglog برای سنجش اعتبار (7.10) نشان می دهد. نمودار های سمت راست k_nn(k) را روی نمودار lin-lin برای سنحش اعتبار (7.21) نشان می دهند. برای نمونه فرض اینکه k_nn(k) بصورت خطی به k وابسته است. این فرضیه پشت ضریب همبستگی r است. شیب خط نقطه چین بیانگر ضریب همبستگی r است. همانطور که نمودار های lin-lin در سمت راست نشان می دهند (7.21) برازش ضعیفی هم برای شبکه های گزینشی و هم شبکه های ناگزینشی ارائه می دهند.

رابطه بین μ و r

در سمت مثبت، r و μ از هم مستقل نیستند. برای نشان دادن این مساله r و μ را برای ده شبکه مرجع نشان می دهیم(جدول 7.1). نتایج حاصل در شکل 7.20 نشان داده شده اند و بیان می کنند که r و μ برای rهای مثبت همبستگی دارند. توجه کنید که این همبستگی برای r های منفی از بین می رود. برای درک پیدایش این رفتار، در ادامه رابطه مستقیم بین r و μ را بدست می آوریم. برای آنکه روی یک مساله تمرکز کنیم، فرض می کنیم (7.10) معتبر است و مقدار r شبکه را با توان همبستگی μ محاسبه می کنیم.

در ابتدا باید a را از رابطه (7.10) بدست آوریم. می توانیم گشتاور دوم توزیع درجه را بصورت زیر مساحبه کنیم:
$\left\langle {k^2 } \right\rangle = \left\langle {k_{nn} (k)k} \right\rangle = \sum\limits_k {ak^{\mu + 1} p_k = a\left\langle {k^{\mu + 1} } \right\rangle }$
که از آن می توان به فرمول زیر رسید
$a = \frac{{\left\langle {k^2 } \right\rangle }}{{\left\langle {k^{\mu + 1} } \right\rangle }}$
اکنون r شبکه را برای μ داده شده محاسبه می کنیم
$r = \frac{{\sum\limits_k {kak^\mu q_k - \frac{{\left\langle {k^2 } \right\rangle ^2 }}{{\left\langle k \right\rangle ^2 }}} }}{{\sigma _r^2 }} = \frac{{\sum\limits_k {ak^{\mu + 2} \frac{{p_k }}{{\left\langle k \right\rangle }} - \frac{{\left\langle {k^2 } \right\rangle ^2 }}{{\left\langle k \right\rangle ^2 }}} }}{{\sigma _r^2 }} = \frac{{\frac{{\left\langle {k^2 } \right\rangle }}{{\left\langle {k^{\mu + 1} } \right\rangle }}\frac{{\left\langle {k^{\mu + 1} } \right\rangle }}{{\left\langle k \right\rangle }} - \frac{{\left\langle {k^2 } \right\rangle ^2 }}{{\left\langle k \right\rangle ^2 }}}}{{\sigma _r^2 }} = \frac{1}{{\sigma _r^2 }}\frac{{\left\langle {k^2 } \right\rangle }}{{\left\langle k \right\rangle }}\left( {\frac{{\left\langle {k^{\mu + 2} } \right\rangle }}{{\left\langle {k^{\mu + 1} } \right\rangle }} - \frac{{\left\langle {k^2 } \right\rangle }}{{\left\langle k \right\rangle }}} \right) \hspace{20 mm} (7 . 22)$
به ازای μ=0عبارت آخرین پرانتز حذف می شود و r=0 بدست می آید. بنابراین اگر μ=0 باشد(شبکه خنثی)، براساس r هم شبکه خنثی خواهد بود. برای k>1 طبق فرمول (7.22) به ازای μ>0 این پرانتز مثبت است در نتیجه r>0 و برای μ<0 پرانتز منفی است یعنی r<0. بنابراین r و μ همبستگی های درجه ای مشابهی را پیش بینی می کنند.

شکل 7.20
همبستگی بین r و N
برای مشخص شدن رابطه بین r و μ مقدار μ را با برازش تابع k_nn(k) بر فرمول (7.10) بدست می آوریم. خواه ناخواه مقیاس بندی قانون توان از نظر آماری چشم گیر بود.

به طور خلاصه، اگر تابع همبستگی درجه ای از فرمول (7.10) تبعیت کند، آنگاه علامت توان همبستگی درجه ای μ علامت همبستگی r را مشخص می کند.
$\begin{array}{l} \mu < 0 \to r < 0 \\ \mu = 0 \to r = 0 \\ \mu > 0 \to r > 0 \\ \end{array}$
شبکه های جهت دار

برای اندازه گیری همبستگی های درجه ای باید در نظر بگیریم که هر گره i با یک درجه ورودیk_iⁱⁿ و درجه خروجی k_i^out تعیین می شود. بنابراین چهار همبستگی درجه ای را تعریف می کنیم، r_in,in, r_in,out, r_out,in, r_out,out تا بتوان تمام ترکیبات ممکن بین درجه های ورودی و خروجی دو گره متصل به هم را نشان دهیم(شکل 7.21 a-d ). در نهایت داریم [14]:
$r_{\alpha ,\beta } = \frac{{\sum\limits_{jk} {jk} \left( {e_{jk}^{\alpha ,\beta } - q_{ \leftarrow j}^\alpha q_{ \to k}^\beta } \right)}}{{\sigma _ \leftarrow ^\alpha \sigma _ \to ^\beta }} \hspace{20 mm} (7 . 23)$
که در آن α و β اندیس های ورودی و خروجی و q_(←j)^α احتمال پیدا کردن گره j با درجه α و پیوند تصادفی رو به عقب و q_(→k)^β احتمال پیوند β با درجه k که پی.ند تصادفی رو به جلو هم داشته باشد. σ_←^α وσ_→^σ انحراف معیار استاندارد مربوطه است. برا مشخص شدن کاربرد فرمول (7.23) در شکل 7.21e چهار ضریب همبستگی را برای پنج شبکه جهت دارد مرجع نشان داده شده اند (جدول7.1). با این حال، در نظر داشته باشید که برای توصیف کامل همبستگی درجه ای باید هر چهار تابع k_nn(k) را مطابق نکته 7.3 اندازه گیری کنیم.

نکته 7.7
مسائل مربوط به شبکه های بزرگ

الگوریتم زالوی-برونت و سوکولوو در اندازه گیری بیشینه(rmin) و کمینه (rmax)ضریب هم بستگی در شبکه های مقیاس آزاد که در [21] آمده است کمک می کند.
$r_{\min } \sim \left\{ \begin{array}{l} - c_1 (\gamma ,k_0 ) \hspace{10 mm} \ for \hspace{5 mm} \ \gamma < 2 \\ - N^{(2 - \gamma )/(\gamma - 1)} \hspace{5 mm} \ for \hspace{5 mm} \ 2 < \gamma < 3 \\ - N^{(\gamma - 4)/(\gamma - 1)} \hspace{5 mm} \ for \hspace{5 mm} \ 3 < \gamma < 4 \\ - c_2 (\gamma ,k_0 ) \hspace{10 mm} \ for \hspace{5 mm} \ 4 < \gamma \\ \end{array} \right.$ $r_{\max } \sim \left\{ \begin{array}{l} - N^{( - \gamma - 2)/(\gamma - 1)} \hspace{5 mm} \ for \hspace{5 mm} \ 2 < \gamma < \gamma _r \\ - N^{ - 1/(\gamma ^2 - 1)} \hspace{5 mm} \ for \hspace{5 mm} \ \gamma _r < \gamma < 3 \\ \end{array} \right.$
که در آن
$\gamma _r \approx \frac{1}{2} + \sqrt {17/4} \approx 2.56$
که نشان می دهد:

در N های بزرگ هم r_max و هم r_min ناپدید می شوند حتی اگر در شبکه مربوطه پیوند ها مجددا ایجاد شوند طوری که همبستگی بیشینه داشته باشند. در نتیجه ضریب همبستگی r نمی تواند همبستگی موجود در شبکه های بزرگ را نشان دهد.

در شبکه های بدون مقیاس با γ<2.6 همیشه r منفی است. این موضوع نتیجه همبستگی ساختاری است(شکل 7.4).

با اعمال محدودیت رو r، انتظار داریم k_nn(k) ویژگی های درجه همبستگی شبکه های بزرگ را بهتر توصیف کند.

بطور خلاصه، ضریب هم بستگی درجه ای فرض می کند مقیاس k_nn(k)بطور خطی با k تغییر می کند. تایید عددی یا تحلیلی برای این فرضیه وجود ندارد. محاسبات تحلیلی قانون توانی که فرمول (7.10) یا وابستگی لگاریتمی ضعیف تر (7.20) را ایجاد می کند را پیش بینی می کنند. با این حال در کل علامت r و μ مشابه هم هستند. بنابراین می توانیم از r استفاده کنیم تا سریعتر ماهیت همبستگی ای که ممکن است وجود داشته باشد را پیدا کنیم. ولی باز هم برای پیدا کردن هم بستگی درجه ای بایدk_nn(k) را اندازه بگیریم.

شکل 7.21
همبستگی جهت دار

(a)-(d) پیوند های بنفش و سبز، اندیس های α و β را نشان می دهند که درواقع ضریب هم بستگی متناسب شبکه جهت دارد است.

(e) همبستگی پنج شبکه جهت دار. در حالی که در شبکه ارجاعات علمی همبستگی کم و قابل چشم پوشی است، هر چهار ضریب همبستگی رفتار گزینشی قوی ای برای تلفن های همراه و ناگزینشی قوی برای شبکه متابولیک ثبت می کنند. در مورد شبکه وب موضوع جالب است: در حالی که سه تا از ضریب های همبستگی اش نزدیک به صفر هستند، اما رفتار گزینشی قوی ای برای ترکیب درجه in-out آن وجود دارد

بخش 7.11
مباحث پیشرفته 7.B
برش های ساخت یافته

همانطور که در بخش 7.4 صحبت کردیم، تناقض بنیادین بین خاصیت مقیاس آزاد بودن و هم بستگی درجه ای باعث ایجاد برش ساختاری در شبکه های ساده می شود. در این بحش با محاسبه نحوه بدست آوردن برش ها بر مبنای سایز سیستم N، (7.15) را محاسبه می کنیم.

با تعریف زیر شروع می کنیم:
$\r_{kk'} = \frac{{E_{kk'} }}{{\m_{kk'} }} \hspace{20 mm} (7 . 24)$
که در آن E_kk' تعداد پیوند ها بین گره های از درجه k و گره ها با درجه k’ است در حالیکه (k≠k'). درواقع دوبرابر تعداد پیوند ها برایk=k’ است، و
$m_{kk'} = \min \{ kN_k ,k'N_k ,N_k N_k \} \hspace{20 mm} (7 . 25)$
بیشترین مقدار ممکن برای E_kk' است. بوجود آوردن (7.25) در شکل 7.22نشان داده شده است. بنابراین r_kk' را می توان بصورت زیر نوشت
$\r_{kk'} = \frac{{E_{kk'} }}{{m_{kk'} }} = \frac{{\left\langle k \right\rangle e_{kk'} }}{{\min \{ kP(k),k'P(k'),NP(k)P(k')\} }} \hspace{20 mm} (7 . 26)$
از آنجایی که m_kk' مقدار بیشینه E_kk' است، باید به ازای هر k و k’ ای r_kk'≤1 باشد. به بیان دقیق تر، در شبکه های ساده زوج درجه هایی که برای آنها r_kk'>1باشد وجود نخواهند داشت. ولی باز هم برای بعضی از شبکه و بعضی از kو k’ ها r_kk' بزرگتر از یک است. به وضوح این مساله فیزیکی نیست و باعث ایجاد تداخل هایی در پیکربندی شبکه می شود. بنابراین برش ساختاری k_sرا به عنوا راه حل فرمول (7.27) تعریف می کنیم
$r_{k_s k_s } = 1 \hspace{20 mm} (7 . 27)$
توجه کنید به محض اینکه k^'>Np_k و k>Np_k' ، تاثیر محدودیت ها روی پیوند های چندگانه احساس می شود و تعریف r_kk' را بصورت زیر تبدیل می کند.
$r_{kk'} = \frac{{\left\langle k \right\rangle e_{kk'} }}{{Np_k p_k }} \hspace{20 mm} (7 . 28)$
برای شبکه های مقیاس آزاد این شرایط در ناحیه k, k' > (aN)^1/(γ+1) کاملا برقرار است که در آن a ثابتی وابسته به p_k است. توجه کنید این مقدار پایین تر از برش طبیعی است. در نتیجه، این مقیاس بندی حد پایینی برای برش ساختاری است، هر وقت برش توزیع درجه پایینتر از این محدوده قرار بگیرد، همیشه شرط r_kk' < 1 برقرار است.

در شبکه های خنثی توزیع اشتراک بصورت زیر عمل می کند
$e_{kk'} = \frac{{kk'p_k p_{k'} }}{{\left\langle k \right\rangle ^2 }} \hspace{20 mm} (7 . 29)$
بنابراین نرخ (7.28) بصورت زیر می شود
$r_{kk'} = \frac{{kk'}}{{\left\langle k \right\rangle N}} \hspace{20 mm} (7 . 30)$
بنابراین، برش ساختاری با رعایت شرط r_kk' بصورت زیر خواهد بود[11, 34, 35, 36]
$k_s (N) \sim \left( {\left\langle k \right\rangle N} \right)^{1/2} \hspace{20 mm} (7 . 31)$
که همان (7.15) است. توجه کنید که (7.31) مستقل از توزیع درجه شبکه مربوطه است. در نتیجه در شبکه مقیاس آزاد k_s (N) مستقل از توان درجه γ است.

شکل 7.22
محاسبه m_kk'

بیشینه تعداد پیوند های ممکن بین دو گروه. این شکل دو گروه از گره ها را نشان می دهد که درجه آنها k=3 و k’=2 است. تعداد پیوند های بین این دو گروه نباید بیشتر از موارد زیر شود:

تعداد پیوند های موجود در گروه k=3 که برابراست با kN_k=9

تعداد پیوند های موجود در گروه k’=2 که برابر است با k'N_k'=8

تعداد پیوند های بالقوه ای که می تواند بین این دو گروه وجود داشته باشد و برابر است با N_kN_k'

در مثالی که در بالا نشان داده شد کمترین مربوط به مورد b است یعنی k'N_k'= 8

بخش 7.12
مراجع

[1] P. Uetz, L. Giot, G. Cagney, T. A. Mansfield, RS Judson, JR Knight, D. Lockshon, V. Narayan, M. Srinivasan, P. Pochart, A. Qureshi-Emili, Y. Li, B. Godwin, D. Conover, T. Kalbfleisch, G. Vijayadamodar, M. Yang, M. Johnston, S. Fields, J. M. Rothberg. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. Nature, 403: 623â€“627, 2000.

[2] I. Xenarios, D. W. Rice, L. Salwinski, M. K. Baron, E. M. Marcotte, D. Eisenberg. DIP: the database of interacting proteins. Nucleic Acids Res., 28: 289â€“29, 2000.

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

[4] R. Pastor-Satorras, A. VÃ¡zquez, and A. Vespignani. Dynamical and correlation properties of the Internet. Phys. Rev. Lett., 87: 258701, 2001.

[5] A. Vazquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of Internet. Phys. Rev., E 65: 066130, 2002.

[6] S.L. Feld. Why your friends have more friends than you do. American Journal of Sociology, 96: 1464â€“1477, 1991.

[7] E.W. Zuckerman and J.T. Jost. What makes you think youâ€™re so popular? Self evaluation maintenance and the subjective side of the â€œfriendship paradoxâ€. Social Psychology Quarterly, 64: 207â€“223, 2001.

[8] M. E. J. Newman. Assortative mixing in networks. Phys. Rev. Lett., 89: 208701, 2002.

[9] M. E. J. Newman. Mixing patterns in networks. Phys. Rev. E, 67: 026126, 2003.

[10] S. Maslov, K. Sneppen, and A. Zaliznyak. Detection of topological pattern in complex networks: Correlation profile of the Internet. Physica A, 333: 529-540, 2004.

[11] M. Boguna, R. Pastor-Satorras, and A. Vespignani. Cut-offs and finite size effects in scale-free networks. Eur. Phys. J. B, 38: 205, 2004.

[12] M. E. J. Newman and Juyong Park. Why social networks are different from other types of networks. Phys. Rev. E, 68: 036122, 2003.

[13] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: homophily in social networks. Annual Review of Sociology, 27:415-444, 2001.

[14] J. G. Foster, D. V. Foster, P. Grassberger, and M. Paczuski. Edge direction and the structure of networks. PNAS, 107: 10815, 2010.

[15] A. Barrat and R. Pastor-Satorras. Rate equation approach for correlations in growing network models. Phys. Rev. E, 71: 036127, 2005.

[16] S. N. Dorogovtsev and J. F. F. Mendes. Evolution of networks. Adv. Phys., 51: 1079, 2002.

[17] J. Berg and M. LÃ¤ssig. Correlated random networks. Phys. Rev. Lett., 89: 228701, 2002.

[18] M. BoguÃ±Ã¡ and R. Pastor-Satorras. Class of correlated random networks with hidden variables. Phys. Rev. E, 68: 036112, 2003.

[19] R. Xulvi-Brunet and I. M. Sokolov. Reshuffling scale-free networks: From random to assortative. Phys. Rev. E, 70: 066102, 2004.

[20] R. Xulvi-Brunet and I. M. Sokolov. Changing correlations in networks: assortativity and dissortativity. Acta Phys. Pol. B, 36: 1431, 2005.

[21] J. Menche, A. Valleriani, and R. Lipowsky. Asymptotic properties of degree-correlated scale-free networks. Phys. Rev. E, 81: 046103, 2010.

[22] V. M. EguÃluz and K. Klemm. Epidemic threshold in structured scale-free networks. Phys. Rev. Lett., 89:108701, 2002.

[23] M. BoguÃ±Ã¡ and R. Pastor-Satorras. Epidemic spreading in correlate complex networks. Phys. Rev. E, 66: 047104, 2002.

[24] M. BoguÃ±Ã¡, R. Pastor-Satorras, and A. Vespignani. Absence of epidemic threshold in scale-free networks with degree correlations. Phys. Rev. Lett., 90: 028701, 2003.

[25] A. VÃ¡zquez and Y. Moreno. Resilience to damage of graphs with degree correlations. Phys. Rev. E, 67: 015101R, 2003.

[26] S.J. Wang, A.C. Wu, Z.X. Wu, X.J. Xu, and Y.H. Wang. Response of degree-correlated scale-free networks to stimuli. Phys. Rev. E, 75: 046113, 2007.

[27] F. Sorrentino, M. Di Bernardo, G. Cuellar, and S. Boccaletti. Synchronization in weighted scale-free networks with degreeâ€“degree correlation. Physica D, 224: 123, 2006.

[28] M. Di Bernardo, F. Garofalo, and F. Sorrentino. Effects of degree correlation on the synchronization of networks of oscillators. Int. J. Bifurcation Chaos Appl. Sci. Eng., 17: 3499, 2007.

[29] A. Vazquez and M. Weigt. Computational complexity arising from degree correlations in networks. Phys. Rev. E, 67: 027101, 2003.

[30] M. Posfai, Y Y. Liu, J-J Slotine, and A.-L. BarabÃ¡si. Effect of correlations on network controllability. Scientific Reports, 3: 1067, 2013.

[31] M. Weigt and A. K. Hartmann. The number of guards needed by a museum: A phase transition in vertex covering of random graphs. Phys. Rev. Lett., 84: 6118, 2000.

[32] S. Maslov and K. Sneppen. Specificity and stability in topology of protein networks. Science, 296: 910â€“913, 2002.

[33] L. Adamic and N. Glance. The political blogosphere and the 2004 U.S. election: Divided they blog (2005).

[34] J. Park and M. E. J. Newman. The origin of degree correlations in the Internet and other networks. Phys. Rev. E, 66: 026112, 2003.

[35] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6: 125, 2002.

[36] Z. Burda and Z. Krzywicki. Uncorrelated random networks. Phys. Rev. E, 67: 046118, 2003.

شبکه	N	r	μ
اینترنت	192,244	0.02	0.56
وب	325,729	-0.05	-1.11
شبکه برق	4,941	0.003	0.0
تماس های تلفن همراه	36,595	0.21	0.33
پست الکترونیکی	57,194	-0.08	-0.74
همکاری های علمی	23,133	0.13	0.16
شبکه بازیگران	702,388	0.31	0.34
شبکه ارجاعات علمی	449,673	-0.02	-0.18
شبکه متابولیسم	1,039	-0.25	-0.76
شبکه برهم کنش پروتئینی	2,018	0.04	-0.1

بخش 7.1 مقدمه

بخش 7.2 هم ساز و غیر هم ساز

بخش 7-3 اندازه گیری همبستگی درجه ای

بخش 7.4 برش های ساخت یافته

بخش 7.5 همبستگی ها در شبکه های واقعی

بخش 7.6 ایجاد شبکه های هم بسته

همبستگی های درجه ای در مدل های ایستا

هم بستگی درجه ای در شبکه های در حال توسعه

تنظیم همبستگی درجه ای

بخش 7.7 اثر همبستگی های درجه ای

بخش 7.8 خلاصه

بخش 7.9 تمرین ها

بخش 7.10 مباحث پیشرفته 7.Aضریب همبستگی درجه ای

رابطه بین μ و r

شبکه های جهت دار

بخش 7.11 مباحث پیشرفته 7.Bبرش های ساخت یافته

بخش 7.12 مراجع

بخش 7.1
مقدمه

بخش 7.2
هم ساز و غیر هم ساز

بخش 7-3
اندازه گیری همبستگی درجه ای

بخش 7.4
برش های ساخت یافته

بخش 7.5
همبستگی ها در شبکه های واقعی

بخش 7.6
ایجاد شبکه های هم بسته

بخش 7.7
اثر همبستگی های درجه ای

بخش 7.8
خلاصه

بخش 7.9
تمرین ها

بخش 7.10
مباحث پیشرفته 7.A
ضریب همبستگی درجه ای

بخش 7.11
مباحث پیشرفته 7.B
برش های ساخت یافته

بخش 7.12
مراجع