بخش 1.2
پل‌های کونیگسبرگ

مشخص کردن زمان دقیق پیدایش بیشتر زمینه‌های تحقیقاتی امکان‌پذیر نیست. اما در مورد نظریه گراف که زیربنای نظری علم شبکه است، این امر امکان‌پذیر است. ریشه نظریه گراف به سال ۱۷۳۵ میلادی در شهر کونیگسبرگ که پایتخت پروس شرقی و یکی از پررونق‌ترین شهرهای آن زمان ازنظر اقتصادی بود برمی‌گردد. رونق تجارت و کشتیرانی در این شهر امکان ساخت پل‌های متعدد را فراهم آورده بود و 7 پل روی رودخانه پِرِگل که شهر را احاطه کرده بود، ساخته شد. پنج‌تا از این پل‌ها جزیره زیبای نایهوف را که در بین دو شاخه رود پِرگل قرار گرفته بود، به مرکز شهر وصل می‌کرد. دوتای دیگر از روی دو انشعاب رودخانه عبور می‌کردند (شکل ۲-۱). چیدمان خاص پل‌ها باعث طرح معمایی در بین مردم شده بود: آیا می‌توان از روی هر هفت پل عبور کرد، بدون اینکه از روی یکی از پل‌ها دو بار گذشت؟ علیرغم تلاش‌های فراوان هنوز کسی نتوانسته چنین مسیری پیدا کند. این مسئله تا سال ۱۷۳۵ که لئونارد اویلر، ریاضی‌دان سوئیسی، به کمک ریاضیات ثابت کرد که چنین مسیری وجود ندارد، حل‌نشده باقی ماند.

اویلر هرکدام از چهار بخش شهر را که توسط پل‌ها از هم جدا شده بودند، با چهار حرف A، B، C و D نشان داد (شکل ۲-۱). سپس هر دو بخشی را که توسط یک پل به هم متصل بودند، با یک خط به هم وصل کرد. بدین ترتیب گرافی ساخت که رأس-هایش بخش‌های شهر و یال‌هایش پل‌ها بودند. اویلر متوجه نکته ساده‌ای شد: اگر مسیری وجود داشته باشد که از همه پل‌ها عبور کند ولی از هیچ پلی دو بار نگذرد، رأس‌های با درجه فرد باید یا رأس شروع و یا رأس پایان باشند. دلیل این مطلب این است که اگر وارد یک رأس با تعداد فرد یال شویم، چون برای خارج شدن باید از یال دیگری استفاده کنیم، پس از چند بار وارد شدن سرانجام یال استفاده‌نشده‌ای برای خروج باقی نخواهد ماند.

پل‌های کونیگسبرگ: — شکل 2.1: پل‌های کونیگسبرگ
• نقشه شهر کونیگسبرگ در زمان اویلر (اکنون در کالینینگراد روسیه واقع است)
• طرحی از کونیگسبرگ متشکل از چهار بخش و 7 پل که از روی آن‌ها رد شده است.
• اویلر گرافی ساخت که دارای چهار گره (A, B, C, D) متناظر با هریک از بخش‌های شهر و 7 یال متناظر با پل‌ها بود. او سپس نشان داد که هیچ مسیر پیوسته‌ای وجود ندارد که از این هفت پل عبور کند، به‌طوری‌که از هیچ‌کدام دو بار نگذرد. مردم کونیگسبرگ درنهایت دست از جستجوی بی‌حاصل برای یافتن چنین مسیری برداشتند و در سال ۱۸۷۵ پل جدیدی بین B و C ساختند که تعداد یال‌های بین این دو گره را به 4 افزایش داد. حال تنها یک گره با تعداد یال فرد باقی می¬ماند. بنابراین پیدا کردن مسیر مورد نظر امکان¬پذیر می¬شود. سعی کنید این مسیر را پیدا کنید.

مسیری که از این هفت پل می‌گذرد، تنها می‌تواند یک نقطه شروع و یک نقطه پایان داشته باشد. بنابراین چنین مسیری نمی‌تواند در گرافی که بیش از یک رأس با تعداد یال¬های فرد دارد، وجود داشته باشد. در گراف کونیگسبرگ چهار رأس A، B، C و D تعداد یال¬هایشان فرد است، بنابراین هیچ مسیری که شرایط مسئله را ارضا کند، در این گراف وجود ندارد.

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

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

منبع آنلاین 1.1:پیش بینی شیوع H1N1
پیش بینی شیوع H1N1 در سال 2009 اولین نمونه از پیش بینی موفق لحظه ای از شیوع بیماری به شمار می آید[13].. این پروژه، با تکیه بر داده های توصیف جنبه های ساختاری و پویای شبکه حمل و نقل در سراسر جهان، پیش بینی کرد که شیوع ویروسH1N1 در اکتبر 2009 به اوج خود می رسد. پیش از آن تصور می شد شیوع آنفولانزا در ماه های ژانویه-فوریه به اوج خود برسد و برنامه ریزی شده بود که واکسن هایی در ماه نوامبر 2009 در اختیار قرار گیرد. پیش بینی به کمک علم شبکه نشان داد که این زمان خیلی دیر خواهد بود و فاقد اثربخشی لازم در کنترل ویروس است. موفقیت این پروژه قدرت علم شبکه را در بهبود در زمینه های اساسی زندگی بشر نشان می دهد.

بخش 2.2
شبکه‌ و گراف‌

اگر بخواهیم درک درستی از یک سیستم پیچیده به دست آوریم، نخست باید نحوه برهم¬کنش اجزای آن را بشناسیم. به‌بیان‌دیگر، نیاز به یک نقشه از نحوه اتصال اجزای آن که اصطلاحاً به آن نمودار سیم‌کشی گفته می‌شود داریم. یک شبکه از مجموعه‌ای از اجزای سیستم، که اغلب آن‌ها را گره‌ یا رأس می‌نامند، و تعاملات بین آن‌ها، که اغلب پیوند یا یال خوانده می‌شود، تشکیل می‌شود (نکته 2-۱). این نحوه توصیف شبکه یک زبان مشترک برای مطالعه شبکه‌ها علیرغم تفاوت در ماهیت، ظاهر، یا دامنه کاربرد آن¬ها ارائه می‌دهد. همان‌طور که در شکل 2-۲ نشان داده شده، سه نوع شبکه متفاوت، در قالب شبکه، نمایشی کاملاً یکسان دارند.

شکل ۲-۲ دو پارامتر اصلی شبکه را معرفی می‌کند:

تعداد گره‌ها، که با N نمایش داده می‌شود، که نشان‌دهنده تعداد مؤلفه‌های سیستم است. ما معمولاً N را اندازه شبکه می‌خوانیم. برای اینکه بین گره‌ها تمایز قائل شویم، آن‌ها را با i=1,2,..N برچسب‌گذاری می‌کنیم.
تعداد پیوندها، که با L نشان داده می‌شود، بیانگر تعداد کل تعاملات بین گره‌ها است. پیوندها به‌ندرت برچسب‌گذاری می‌شوند، زیرا توسط گره‌هایی که به آن‌ها متصل هستند قابل شناسایی هستند. برای مثال، پیوند (۲،۴) گره‌های ۲ و ۴ را به هم وصل می‌کند.

در شبکه‌هایی که در شکل 2-۲ نشان داده شده، N=۴ و L=۴ است

شبکه‌های متفاوت، با گراف‌های یکسان: — شکل 2.2: شبکه‌های متفاوت، با گراف‌های یکسان
این شکل زیرمجموعه¬های کوچکی از چند شبکه معروف را نشان می‌دهد: (الف) اینترنت، که در آن مسیریاب‌ها به یکدیگر متصل شده‌اند، (ب) شبکه بازیگرهای هالیوود، که در آن دو بازیگر به هم متصل می‌شوند، اگر در یک فیلم هم‌بازی شده باشند، (ج)شبکه تعاملی پروتئین-پروتئین، که در آن دو پروتئین به هم متصل هستند، اگر بتوانند در یک سلول با یکدیگر تشکیل پیوند بدهند. بااینکه ماهیت این گره‌ها و پیوندها متفاوت است، همه آن‌ها نمایش گرافی یکسانی دارند (د) و با گرافی با 4 گره و 4 پیوند قابل نمایش هستند (N=4 و L=4).

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

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

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

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

نکته 2.1
شبکه‌ یا گراف؟

در ادبیات علمی واژه‌های شبکه و گراف به‌جای هم استفاده می‌شود:

علم شبکه	نظریه گراف
شبکه	گراف
گره	رأس
پیوند	یال

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

بااینکه پیوندهای زیادی در این چهار شبکه هم‌پوشانی دارند (بعضی از همکاران ممکن است باهم دوست باشند یا رابطه داشته باشند)، این شبکه‌ها کاربردها و اهداف متفاوتی خواهند داشت.

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

در این کتاب ما برای نشان دادن ابزارهای علوم شبکه از ده شبکه استفاده خواهیم کرد. این شبکه‌های مرجع که شامل سیستم‌های اجتماعی (گراف تماس تلفن همراه یا شبکه پست الکترونیکی)، شبکه‌های همکاری (همکاری علمی یا شبکه بازیگران هالیوود)، سیستم‌های اطلاعاتی (وب)، سیستم‌های فناوری و زیرساختی (اینترنت و شبکه توزیع برق)، سیستم‌های بیولوژیکی (شبکه برهم¬کنش¬های پروتئینی و متابولیک)، و شبکه‌های ارجاع (ارجاع به مقالات علمی) هستند در جدول 2-۱ فهرست شده‌اند. اندازه این شبکه‌ها کاملا با هم متفاوت است: از ۱۰۳۹ گره در شبکه‌های متابولیک E coli گرفته تا حدود نیم میلیون گره در شبکه‌های ارجاعات علمی. همان‌طور که در جدول 2-۱ نشان داده‌ شده، تعدادی از این شبکه‌ها جهت‌دار و تعدادی بدون جهت هستند. در فصل‌های بعدی به‌منظور فهم شبکه‌های پیچیده، در مورد ویژگی‌ها و ماهیت هرکدام از این شبکه به‌تفصیل بحث خواهیم کرد.

شبکه	گره ها	پیوند ها	جهتدار / بدون جهت	N	L	â€¹Kâ€º
شبکه اینترنت	دستگاه های روتر	ارتباطات اینترنتی	بدون جهت	192,244	609,066	6.34
شبکه جهانی وب	صفحات وب	پیوند ها	جهتدار	325,729	1,497,134	4.60
شبکه برق قدرت	نیروگاه ها و ترانسفورماتورها	کابل ها	بدون جهت	4,941	6,594	2.67
تماس های تلفن همراه	مشترکین	تماس های تلفنی	جهتدار	36,595	91,826	2.51
پست الکترونیکی	آدرس ایمیل	ایمیل ها	جهتدار	57,194	103,731	1.81
همکاری های علمی	دانشمندان	مقالات مشترک	بدون جهت	23,133	93,437	8.08
شبکه هنرپیشگان	هنرپیشگان	بازی در فیلم مشترک	بدون جهت	702,388	29,397,908	83.71
شبکه ارجاعات علمی	مقالات	ارجاع به مقاله	جهتدار	449,673	4,689,479	10.43
متابولیسم باکتری اشریشیا کُلی	متابولیتها	واکنش های شیمیایی	جهتدار	1,039	5,802	5.58
برهمکنش پروتئین ها	پروتئین ها	پیوند	بدون جهت	2,018	2,930	2.90

جدول 2.1
Canonical Network Maps

ویژگی‌های اصلی ده شبکه که در این کتاب برای نمایش ابزارهای علم شبکه استفاده می‌شوند.

این جدول ماهیت گره‌ها و پیوندهای این شبکه‌ها را با نشان دادن جهت‌دار یا بدون جهت بودن پیوندها، تعداد گره‌ها (N) و پیوندها (L)، و میانگین درجه هر شبکه فهرست می‌کند. برای شبکه‌های جهت‌دار میانگین درجه‌ها عبارت است از میانگین درجه‌های ورودی یا خروجی (رابطه (۲-۵) را ببینید). ‹k› = ‹k_in›=‹k_out›

بخش 3-2
درجه، میانگین درجه و توزیع درجه

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

درجه

درجه iامین گره در شبکه را با k_i نمایش می‌دهیم. برای مثال، برای گراف بدون جهتی که در شکل۲-۲ نمایش داده شده، داریم: k₁=2, k₂=3, k₃=2, k₄=1

در یک گراف بدون جهت تعداد کل پیوندها را می‌توان با جمع درجه¬های همه گره‌ها محاسبه کرد:

$L = \frac{1}{2}\sum\limits_{i = 1}^N {k_i } \hspace{20 mm} (2 . 1) \$

در اینجا ضریب ۲\۱ به این دلیل استفاده می‌شود که در جمع (2-۱) هر پیوند دو بار شمرده می‌شود. برای مثال، پیوندی که در شکل۲-۲ گره‌های ۲ و ۴ را به هم وصل می‌کند، یک‌بار در درجه گره ۲ و یک‌بار در درجه گره ۴ لحاظ می‌شود.

میانگین درجه

یک ویژگی مهم شبکه، میانگین درجه‌هایش است(نکته ۲-۲)، که برای شبکه‌های بدون جهت عبارت است از:

$\left\langle k \right\rangle = \frac{1}{N}\sum\limits_{i = 1}^N {k_i } = \frac{{2L}}{N} \hspace{20 mm} (2 . 2)$

در شبکه‌های جهت‌دار بین درجه ورودی k_iⁱⁿ ، که بیانگر تعداد پیوندهایی است که به گره i اشاره می‌کنند، و درجه خروجی k_i^out، که بیانگر تعداد پیوندهایی است که از سمت گره i به دیگر گره‌ها اشاره می¬کند، تمایز قائل می‌شویم. درنهایت درجه کلی یک گره، k_i ، عبارت است از:

فاکتور ۲\۱ که در رابطه (۲-۱) استفاده شده بود، اینجا وجود ندارد، زیرا در گراف جهت‌دار، دو جمع موجود در رابطه (2-۴) درجه‌های ورودی و خروجی را به‌طور جداگانه شمارش می‌کنند. میانگین درجه شبکه جهت‌دار عبارت است از:

$\left\langle {k^{in} } \right\rangle = \frac{1}{N}\sum\limits_{i = 1}^N {k_i^{in} } = \left\langle {k^{out} } \right\rangle = \frac{1}{N}\sum\limits_{i = 1}^N {k_i^{out} } = \frac{L}{N} \hspace{20 mm} (2 . 5)$

توزیع درجه

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

$\sum\limits_{k = 1}^\infty {p_k } = 1 \hspace{20 mm} (2 . 6)$

برای یک شبکه با N گره، توزیع درجات یک هیستوگرام نرمال¬سازی¬شده است (شکل 2-3)، که عبارت است از:

$p_k = \frac{{N_k }}{N} \hspace{20 mm} (2 . 7)$

که در آن N_k عبارت است از تعداد گره‌های با درجه k. بنابراین تعداد گره‌های با درجه k با استفاده از توزیع درجه N_k = Np_k. به دست می‌آید.

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

$\left\langle k \right\rangle = \sum\limits_{k = 0}^\infty {kp_k } \hspace{20 mm} (2 . 8)$

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

Degree Distribution. — شکل 2-۳
توزیع درجه
توزیع درجه یک شبکه با معادله (2-7) تعیین می‌شود..

• برای شبکه (الف) با N = 4، توزیع درجه در (ب) نشان داده شده است.

داریم: p₁ = 1/4 (یکی از چهار گره دارای درجه k1=1 است)، p2=1/2 (دو گره دارای درجه k3=k4=2 هستند)، و p3=1/4 (k2=3). ازآنجاکه هیچ گره‌ای با درجه بیشتر از 3 نداریم، p_k=0 برای k > 3.

• بخش ج یک شبکه‌بندی یک‌بعدی را نشان می‌دهد که هر گره درجه k = 2دارد k = 2.

• توزیع درجه (ج) تابع دلتای کرونکر است،( *p_k* = δ(k - 2

Degree Distribution of a Real Network. — شکل 2-۴
توزیع درجه در یک شبکه واقعی
در شبکه‌های واقعی درجه گره‌ها می‌تواند تفاوت گسترده‌ای داشته باشد.

طرح تعاملات شبکه پروتئینی مخمر (جدول 2-۱). هر گره متناظر با یک مخمر پروتئینی است، و پیوندها متناظر با تعاملاتی هستند، که مرتبط با هم تشخیص داده شده‌اند. دقت کنید که پروتئین‌هایی که در قسمت پایین نشان داده شده‌اند، دارای طوقه هستند، بنابراین درجه آن‌ها k=2 است.

توزیع درجه شبکه تعاملات پروتئین که در (a) نشان داده شده است. درجه‌های مشاهده‌شده بین k=0 (گره‌های ایزوله) و k=92، که درجه گره با بیشترین پیوند یا همان قطب (هاب) است، متغیرند. همچنین بین تعداد گره‌ها با درجات مختلف تفاوت گسترده‌ای وجود دارد: تقریباً نصف گره‌ها درجه یک دارند (p1=0.48)، درحالی‌که فقط یک گره خیلی بزرگ با درجه 92 داریم (p92 = 1/N=0.0005).

توزیع درجه شبکه تعاملات پروتئین که در (a) نشان داده شده است. درجه‌های مشاهده‌شده بین k=0 (گره‌های ایزوله) و k=92، که درجه گره با بیشترین پیوند یا همان قطب (هاب) است، متغیرند. همچنین بین تعداد گره‌ها با درجات مختلف تفاوت گسترده‌ای وجود دارد: تقریباً نصف گره‌ها درجه یک دارند (p1=0.48)، درحالی‌که فقط یک گره خیلی بزرگ با درجه 92 داریم (p92 = 1/N=0.0005).

بخش 2-۴
ماتریس مجاورت

برای مدل کردن یک شبکه باید اطلاعات یال‌های آن را به نحوی نگهداری کرد. ساده‌ترین راه این است که لیست کاملی از پیوندها نگهداری شود. برای مثال شبکه شکل 2-۲ با استفاده از لیست چهار پیوندش: {(2،4)، (2،3)، (1،3)، (1،2)} به‌طور یکتا تعریف می‌شود. در ریاضیات اغلب یک شبکه را با ماتریس مجاورت نمایش می‌دهیم. ماتریس مجاورت یک شبکه جهت‌دار با N گره شامل N سطر و N ستون است، و درایه¬های آن عبارت‌اند از:

• A_ij = 1 اگر از گره i به گره j یال وجود داشته باشد.

• A_ij = 0 اگر بین گره‌های i و j یالی وجود نداشته باشد.

در ماتریس مجاورت یک گراف بدون جهت، هر یال دوبار تکرار می شود، برای مثال پیوند (2,1) به شکل A12=1 و A21=1 نمایش داده می‌شود. بنابراین ماتریس گراف بدون جهت، متقارن است،A_ij = A_ji (شکل 2-۵ ب) .

درجه k_i برای گره i را می‌توان مستقیماً از ماتریس مجاورت به دست آورد. برای شبکه‌های بدون جهت درجه گره عبارت است از مجموع مقادیر درایه¬ها روی سطرها یا ستون‌ها:

$k_i = \sum\limits_{j = 1}^N {A_{ji} = } \sum\limits_{i = 1}^N {A_{ji} } \hspace{20 mm} (2-۹)$

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

$k_i^{in} = \sum\limits_{j = 1}^N {A_{ij} } , \hspace{15 mm}\ k_i^{out} = \sum\limits_{j = 1}^N {A_{ji} } \hspace{20 mm} (2-۱۰)$

با توجه به اینکه در گراف بدون جهت تعداد یال¬های ورودی و خروجی باهم برابر است، داریم:

$2L = \sum\limits_{i = 1}^N {k_i^{in} = } \sum\limits_{i = 1}^N {k_i^{out} = } \sum\limits_{ij}^N {A_{ij} } \hspace{20 mm} (2-۱۱)$

تعداد عناصر غیر صفر ماتریس مجاورت دو برابر تعداد یال‌ها یا همان 2L است. درواقع یک یال بدون جهت که گره‌های i و j را به هم وصل می‌کند، دو بار در ماتریس ظاهر می‌شود: A_ij = 1 ، پیوندی که از j به i اشاره می‌کند، و A_ji = 1 ، پیوندی که از i به j اشاره می‌کند (شکل 2-۵ ب) .

The Adjacency Matrix. — شکل 2-۵
ماتریس مجاورت

برچسب‌گذاری درایه¬های ماتریس مجاورت

• الف: ماتریس مجاورت یک شبکه بدون جهت. شکل نشان می‌دهد که درجه یک گره (در اینجا گره ۲) می‌تواند از روی مجموع عناصر روی ستون یا سطر مربوطه از ماتریس مجاورت به دست آید. همچنین تعدادی از ویژگی‌های اصلی شبکه، مانند تعداد کل یال‌ها L ، و میانگین درجات ، که با ادبیات ماتریس مجاورت بیان شده‌اند را نشان می‌دهد.

• ب: برای شبکه‌های جهت‌دار هم به طریق مشابه نشان داده شده است.

بخش 2-۵
Real شبکه‌های واقعی تنک هستند

در شبکه‌های واقعی تعداد گره‌ها (N) و تعداد پیوندها (L) می‌توانند بسیار متنوع باشند. برای مثال در شبکه عصبی کرم الگانس سی، که تنها سیستم عصبی از یک موجود زنده است که نقشه آن موجود است، N = 302 نورون (گره) وجود دارد. در مقابل تخمین زده می‌شود که مغز انسان حدود صد میلیارد نورون (N ≈ 10¹¹) داشته باشد. شبکه ژنتیک سلولی انسان حدود ۲۰،۰۰۰ ژن به‌عنوان گره دارد، شبکه اجتماعی شامل هفت میلیارد نفر (N ≈ 7×10⁹) ، و وب حدودا بیش از یک تریلیون صفحه (N > 10¹²) دارد.

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

جدول 2-۱ نشان می‌دهد که تعداد پیوندها نیز تفاوت‌های گسترده‌ای دارد. در یک شبکه که شامل N گره است، تعداد پیوندها می‌تواند بین L = 0 و Lmax تغییر کند، که در آن:

$L_{\max } = \frac{N}{2} = \frac{{N(N - 1)}}{2} \hspace{20 mm} (2-۱۲)$

عبارت است از تعداد کل یال‌های موجود در یک گراف کامل با اندازه N (شکل 2-6). در یک گراف کامل هر گره به تمام گره‌های دیگر متصل است.

Complete Graph. — شکل 2-۶
گراف کامل
یک گراف کامل با N=16 گره و *L_max* = 120 پیوند را نشان می¬دهد، (مطابق رابطه 2-۱۲). در ماتریس مجاورت یک گراف کامل به ازای همه i و j *A_ij* = 1 و *A_ii* = 0ها، است. میانگین درجات یک گراف کامل برابر با = N-1 است. یک گراف کامل را اغلب کلیک می‌نامند، واژه‌ای که استفاده از آن در شناسایی انجمن‌، مسئله‌ای که در فصل ۹ به آن خواهیم پرداخت، رایج است.

در شبکه‌های واقعی L خیلی کوچک‌تر از L_max است، که نشان می¬دهد بیشتر شبکه‌های واقعی تُنک هستند. یک شبکه را تنک می‌نامیم، اگر L‹‹ L_max باشد. برای مثال، گراف وب در جدول 2-۱حدود ۱.۵ میلیون پیوند دارد. اما اگر وب یک گراف کامل بود، باید طبق رابطه 2-۱۲ به تعداد L_max ≈ 5x10¹⁰ پیوند می‌داشت. بدین ترتیب، گراف وب تنها کسر 3x10^-5 از کل پیوندهای ممکن را دارد. این مطلب برای همه‌ شبکه‌های جدول 2-۱ صحیح است: می‌توان بررسی کرد که تعداد پیوندهای آن‌ها تنها کسر کوچکی از تمام پیوندهای ممکن برای یک گراف کامل با همان تعداد گره است.

تُنک بودن شبکه‌های واقعی بدین معناست که ماتریس‌های مجاورت هم تُنک هستند. در یک گراف کامل به ازای تمام i و j ها A_ij = 1 است، بنابراین تمام درایه‌های ماتریس نیز با 1 پر می‌شود. در عوض در شبکه‌های واقعی تنها بخش کوچکی از درایه‌های ماتریس مجاورت مقداری غیر 0 دارند. این موضوع در شکل 2-7 نشان داده شده است. این شکل ماتریس مجاورت شبکه برهم-کنش پروتئین-پروتئین مطرح¬شده در جدول 2-۱ و شکل 2-4 (الف) را نشان می‌دهد. مشاهده می‌شود که این ماتریس تقریباً خالی است.

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

The Adjacency Matrix is Sparse. — شکل 2-۷
ماتریس مجاورت تنک است
ماتریس مجاورت شبکه برهم¬کنش پروتئین-پروتئین مخمر، شامل ۲،۰۱۸ گره که هرکدام نشان‌دهنده یک پروتئین مخمر هستند (جدول 2-۱). در هر درایه ماتریس مجاورت که در آن *A_ij* = 1 است، یک نقطه قرار داده شده، که نشان‌دهنده وجود یک برهم-کنش است. برای *A_ij* = 0 هیچ نقطه‌ای گذاشته نشده است. وجود کسر کوچکی از نقاط نشان‌دهنده ماهیت تنک بودن شبکه برهم¬کنش پروتئین-پروتئین است.

بخش 2-۶
شبکه‌های وزن‌دار

تاکنون تنها در مورد شبکه‌هایی بحث کردیم که وزن تمام یال‌های آن¬ها یکسان بود، A_ij = 1. در بسیاری از کاربردها نیاز به مطالعه شبکه‌های وزن‌دار داریم، که در آن هر پیوند (i,j) یک وزن یکتا w_ij دارد. در شبکه‌های تماس تلفن همراه، وزن می‌تواند نشان‌دهنده مجموع دقایقی باشد که دو نفر با تلفن همراه باهم صحبت کرده¬اند، در شبکه انرژی، وزن نشان‌دهنده مقدار جریانی است که در طول خط انتقال می‌یابد.

برای شبکه‌های وزن‌دار درایه¬های ماتریس مجاورت، حامل وزن پیوندها هستند:

$A_{ij} = w_{ij} \hspace{20 mm} (2 . 13)$

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

نکته 2-۳
قانون متکاف: ارزش یک شبکه

قانون متکاف که در حدود سال ۱۹۸۰ در زمینه ابزارهای ارتباطی توسط رابرت متکاف ارائه شده است بیان می‌کند که ارزش یک شبکه متناسب است با مجذور تعداد گره‌هایش یعنی N². ایده پشت این قانون این است که هرچه افراد بیشتری از یک شبکه استفاده کنند، شبکه باارزش‌تر می‌شود. درواقع، هرچه دوستان شما بیشتر از پست الکترونیکی استفاده کنند، این سامانه برای شما باارزش‌تر می‌شود.

در زمان رشد فزاینده اینترنت در اواخر دهه ۱۹۹۰ قانون متکاف متناوباً برای ارائه ارزش‌گذاری کمّی شرکت‌های اینترنتی استفاده می‌شد. این قانون بیان می‌کرد که ارزش یک خدمت (سامانه) متناسب است با تعداد روابطی که تولید می‌کند، که عبارت است از مجذور تعداد کاربرانش. در مقابل هزینه به‌طور خطی با N افزایش می‌یابد. بنابراین اگر سیستمی تعداد کافی کاربر را جذب کند، به‌طور حتم سودآور خواهد شد، همان‌طور که N² به ازای Nهای بزرگ از N پیشی خواهد گرفت (شکل 2-۸). بنابراین قانون متکاف از ذهنیت « بسازش و خودشان خواهند آمد» پشتیبانی می‌کرد.

قانون متکاف بر مبنای رابطه (2-۱۲) است که می‌گوید اگر همه پیوندهای یک شبکه ارتباطی با N کاربر ارزش یکسان داشته باشند، ارزش کل شبکه متناسب است با N(N-1)/2 ، که تقریباً با N² متناسب است. اگر یک شبکه N= 10 کاربر داشته باشد، L_max = 45 رابطه مختلف بین آن‌ها وجود دارد. اگر اندازه شبکه دو برابر شود N=20، تعداد روابطش دو برابر نمی‌شود، بلکه تقریباً چهار برابر یعنی ۱۹۰ خواهد شد که در اقتصاد به آن پدیده برون¬دهی شبکه می‌گویند. دو مسئله قانون متکاف را محدود می‌کند:

بیشتر شبکه‌های واقعی تنک هستند، یعنی تنها کسر کوچکی از پیوندها وجود دارد. بنابراین، ارزش شبکه مطابق N² رشد نمی‌کند، بلکه به‌طور خطی متناظر با N افزایش می‌یابد.
• همان‌طور که پیوندها می¬توانند وزن متفاوت داشته باشند، همه پیوندها ارزش یکسانی ندارند. بعضی از پیوندها بیشتر استفاده می‌شوند، درحالی‌که اکثریت قریب به‌اتفاق پیوندها ندرتاً مورد استفاده قرار می¬گیرند.

شکل 2-۸
قانون متکاف
طبق قانون متکاف هزینه خدمات مبتنی بر شبکه به‌طور خطی با تعداد گره‌ها (کاربران یا دستگاه‌ها) افزایش می‌یابد. در مقابل مزیت یا درآمد، متناسب با تعداد پیوندهایی L_max که ایجاد می¬شود رشد می کند، که طبق رابطه (2-۱۲) با نسبت N² رشد می‌کند. بنابراین هنگامی‌که تعداد کاربران یا دستگا‌ه‌ها از یک حدی بیشتر شود، تکنولوژی یا سامانه مورد نظر سودآور می‌شود.

بخش 2-۷
شبکه‌های دوبخشی

یک گراف دوبخشی گرافی است که گره‌هایش به دو مجموعه مجزای U و V تقسیم می‌شوند، به‌طوری‌که هر پیوند یک گره از U را به یک گره از V وصل می‌کند. به‌بیان‌دیگر، اگر گره‌های U را با سبز و گره‌‌های V را با بنفش رنگ‌آمیزی کنیم، هر پیوند باید گره‌های با رنگ‌های متفاوت را به هم وصل کند (شکل 2-۹).

برای شبکه دوبخشی می‌توان دو طرح ارائه داد. در طرح اول دو گره U به هم متصل می‌شوند، اگر در نمایش دوبخشی، هردوی آن‌ها به یک گره از V متصل باشند. در طرح دوم دو گره از V به هم متصل می‌شوند، اگر هردوی آن‌ها به یک گره از U متصل شده باشند (شکل 2-۹).

Bipartite Network. — شکل 2-۹
شبکه دوبخشی
یک شبکه دوبخشی دو مجموعه گره U و V دارد. گره‌های مجموعه U مستقیماً به گره‌های مجموعه V متصل هستند. بنابراین هیچ پیوند مستقیمی از مجموعه U به U یا از مجموعه V به V وجود ندارد. این شکل دو طرحی را که برای شبکه دوبخشی معرفی کردیم، نمایش می‌دهد. طرح U با اتصال دو گره از U که هر دو به یک گره از V وصل هستند، به دست می‌آید. طرح V با اتصال دو گره از V که هر دو به یک گره از U وصل هستند، به دست می‌آید.

در نظریه شبکه با تعداد زیادی شبکه دوبخشی سروکار داریم. یکی از شبکه‌های معروف، شبکه بازیگران هالیوود است که یک مجموعه از گره‌ها (U) به فیلم‌ها و مجموعه دوم (V) به بازیگران اختصاص دارد. یک فیلم به یک بازیگر متصل می‌شود اگر آن بازیگر در آن فیلم بازی کرده باشد. یک تصویر از این شبکه، شبکه بازیگران است که در آن دو گره (بازیگر) به هم متصل هستند اگر هر دو در یک فیلم بازی کرده باشند. این شبکه در جدول 2-1 نشان داده شده است. تصویر دیگر شبکه فیلم‌ها است که در آن دو فیلم به هم متصل می‌شوند اگر حداقل یک بازیگر مشترک داشته باشند.

منبع آنلاین 2-2
شبکه بیماری‌های انسان
نسخه باکیفیت شبکه بیماری‌های انسان ]1[ را دانلود کنید یا آن را به‌صورت آنلاین از طریق نیویورک‌تایمز مشاهده کنید.

یکی دیگر از شبکه‌های دوبخشی، شبکه بیماری‌های انسان است که به حوزه پزشکی بازمی¬گردد. این شبکه بیماری‌ها را به ژن‌هایی که جهش آن‌ها منجر به آن بیماری می‌شود، متصل می‌کند (شکل 2-10).

علاوه بر این، امکان تعریف شبکه‌های چندبخشی نیز وجود دارد. به‌عنوان‌مثال شبکه سه‌بخشی دستور پخت-مواد لازم-ترکیب که در شکل 2-11 نشان داده شده است.

Tripartite Network. — شکل2-۱۱
شبکه سه‌بخشی

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

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

بخش 2-8
مسیرها و فواصل

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

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

در شبکه فاصله فیزیکی با طول مسیر جایگزین می‌شود. یک مسیر عبارت است از خط سیری که در طول پیوندهای شبکه حرکت می‌کند. طول یک مسیر عبارت است از تعداد پیوندهایی که در آن مسیر قرار دارند (شکل 2-۱۲a). برخی از متون الزام دارند که هیچ گرهی در یک مسیر دو بار تکرار نشود.

در علم شبکه مسیرها نقش کلیدی ایفا می‌کنند. در بخش‌ بعدی در مورد مهم‌ترین ویژگی‌های آن¬ها بحث می‌کنیم بیشتر این ویژگی¬ها در (شکل 2-۱۳) خلاصه شده‌اند.

Paths. — شکل 2-12
مسیرها

• یک مسیر بین گره‌های i₀ و *i_n* یک لیست مرتب از n پیوند P = {(i₀, i₁), (i₁, i₂), (i₂, i₃), ... ,(*i_n-1*, *i_n*)} است. طول این مسیر برابر با n است. مسیری که با رنگ نارنجی در (a) نشان داده شده، خط سیر 1→2→5→7→4→6 را دنبال می‌کند، بنابراین طول آن 5 است.

• کوتاه‌ترین مسیرهای بین گره‌های ۱ و ۷، یا فاصله *d₁₇* متناظر است با مسیری با کمترین تعداد پیوند که گره 1 را به گره ۷ متصل می‌کند. ممکن است همان‌طور که در شکل با رنگ‌های نارنجی و طوسی نشان داده شده، چندین مسیر با طول یکسان وجود داشته باشد. قطر شبکه عبارت است از طولانی‌ترین فاصله در شبکه، که در اینجا *d_max* = 3 است.

کوتاه‌ترین مسیر

کوتاه‌ترین مسیر بین دو گره i و j مسیری است با کمترین تعداد پیوند (شکل 2-۱۲b). کوتاه‌ترین مسیر را اغلب فاصله بین گره‌های i و j می‌نامند، و با d_ij یا d نمایش می‌دهند. می‌توان بین یک جفت گره چندین کوتاه‌ترین مسیر با طول یکسان داشت (شکل 2-۱۲b). کوتاه‌ترین مسیر هیچ‌گاه شامل حلقه یا طوقه نمی‌شود.

در یک شبکه بدون جهت d_ij = d_ji است، بدین معنی که فاصله بین گره i و j با فاصله بین گره j و i برابر است. در یک شبکه جهت‌دار اغلب d_ij ≠ d_ji است. به‌علاوه، در یک شبکه جهت‌دار وجود یک مسیر از گره i به گره j به معنای وجود مسیر از گره j به گره i نیست.

در شبکه‌های واقعی معمولاً نیاز به تعیین فاصله بین دو گره داریم. برای یک شبکه کوچک مانند شبکه‌ای که در شکل 2-۱۲ نشان داده شده، این کار آسان است. برای شبکه‌ای با میلیون‌ها گره، پیدا کردن کوتاه‌ترین مسیر بین دو گره می‌تواند زمان‌بر باشد. طول کوتاه‌ترین مسیر و تعداد این مسیرها را می‌توان با استفاده از ماتریس مجاورت به دست آورد (نکته 2-۴). در عمل برای این کار از الگوریتم جستجوی سطح-اول (BFS) که در نکته 2-۵ در مورد آن بحث شده، استفاده می‌کنیم.

Pathology. — شکل 2-۱۳
مسیر شناسی

مسیر
یک دنباله از گره‌ها به‌طوری‌که در طول مسیر هر گره با یک پیوند به گره بعدی متصل باشد. هر مسیر شامل n+1 گره و n پیوند است. طول مسیر با تعداد پیوندها برابر است. برای مثال، خط نارنجی 1 → 2 → 5 → 4 → 3 مسیری به طول ۴ را پوشش می‌دهد.

کوتاه‌ترین مسیر
مسیر با کوتاه‌ترین فاصله d بین دو گره. d را همچنین فاصله بین دو گره نیز می‌نامیم. دقت کنید که کوتاه‌ترین مسیر الزاماً یکتا نیست: بین گره ۱ و ۴ کوتاه‌ترین مسیر 1→ 2→ 3→ 4 (آبی) و 1→ 2→ 5→ 4 (نارنجی) را داریم، که طول هردو برابر است با: *d_1,4* =3 .

قطر (*d_max*)
طولانی‌ترین کوتاه‌ترین مسیر در یک گراف، یا فاصله بین دورترین نقاط. در گرافی که اینجا نمایش داده شده، قطر بین گره¬های ۱ و ۴ است، و بنابراین *d_max*=3 است

میانگین طول فواصل (*〈d〉*)
میانگین کوتاه‌ترین فاصله‌های بین جفت گره‌ها. برای گراف سمت چپ *1.6=〈d〉*، که محاسبه آن در کنار تصویر نشان داده شده است.

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

مسیر اویلری
مسیری که هر پیوند را دقیقاً یک‌بار پیمایش می‌کند. در شکل دو مسیر اویلری یکی به رنگ نارنجی و دیگری به رنگ آبی نمایش داده شده است.

مسیر همیلتونی
مسیری که هر گره را دقیقاً یک‌بار ملاقات می‌کند. در شکل دو مسیر همیلتونی به رنگ‌های آبی و نارنجی نشان داده شده است.

نکته 2-۴
تعداد کوتاه‌ترین مسیرهای بین دو گره

تعداد کوتاه‌ترین مسیرها، N_ij، و فاصله بین گره‌ i و j ، d_ij ، را می‌توان با محاسبه مستقیم از ماتریس مجاورت A_ij به دست آورد.

d_ij = 1: : اگر یک پیوند مستقیم بین گره‌های i و j وجود داشته باشد، آنگاه A_ij = 1 (در غیر این صورت A_ij = 0)

d_ij = 2: اگر یک مسیر با طول ۲ بین i و j وجود داشته باشد، آنگاه A_ik A_kj =1 (در غیر این صورت A_ik A_kj = 0). تعداد مسیرهای با طول ۲ بین i و j عبارت است از:

$N_{ij}^{(2)} = \sum\limits_{k = 1}^N {A_{ik} A_{jk} } = A_{ij}^2$

که در آن _ij[...] عبارت است از عنصر ijام ماتریس

d_ij = d: اگر مسیری به طول d بین i و j وجود داشته باشد، آنگاه A_ik ... A_lj = 1 ، در غیر این صورت A_ik ... A_lj = 0 . تعداد مسیرهای به طول d بین i و j برابر است با:

$N_{ij}^{(d)} = A_{ij}^d$

این روابط هم برای شبکه‌های جهت‌دار و هم برای شبکه‌های بدون جهت صادق‌اند. فاصله بین گره‌های i و j عبارت است از مسیر با کوچک‌ترین d که برای آن N_ij^(d) › 0 باشد. باوجود دقت این رویکرد، در مورد شبکه‌های بزرگ استفاده از الگوریتم جستجوی سطح -اول که در نکته 2-۵ توضیح داده شده، کارآمدتر خواهد بود.

قطر شبکه

قطر یک شبکه که با d_max نشان داده می‌شود، عبارت از بیشینه کوتاه‌ترین مسیر در شبکه است. به‌بیان‌دیگر، قطر شبکه طولانی‌ترین فاصله‌ای است که بین هر دو گره در شبکه مشاهده شده است. می‌توان بررسی کرد که قطر شبکه نشان داده شده در شکل 2-۱۳ برابر با d_max = 3 است. برای شبکه‌های بزرگ‌تر قطر شبکه را می‌توان با استفاده از الگوریتم جستجوی سطح-اول که در نکته 2-۵ شرح داده شده، تعیین کرد.

میانگین طول مسیر

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

$d = \frac{1}{{N(N - 1)}}\sum\limits_{i,j = 1,N;i \ne j} {d_{i,j} } \hspace{20 mm} (2 . 14)$

دقت کنید که رابطه (۲-۱۴) تنها برای جفت گره‌هایی که در یک مؤلفه قرار دارند، قابل اندازه‌گیری است (بخش ۲-۹). می‌توانیم برای تعیین میانگین فاصله در شبکه‌های بزرگ از الگوریتم BFS استفاده کنیم. بدین منظور، ابتدا فاصله اولین گره تا دومین گره و تمام گره‌های دیگر را با استفاده از الگوریتم نکته 2-۵ محاسبه می‌کنیم. سپس فاصله گره دوم و تمام گره‌های دیگر به‌جز گره اول را محاسبه می‌کنیم (اگر شبکه بدون جهت باشد). سپس همین روند را برای تمام گره‌های دیگر تکرار می‌کنیم.

نکته 2-۵
الگوریتم جستجوی سطح-اول (BFS)

BFS الگوریتمی متداول در علم شبکه است. همانند پرتاب یک سنگ در برکه و مشاهده امواجی که از آن منتشر می‌شوند، الگوریتم BFS از یک گره شروع می‌کند، و همسایگانش را برچسب‌گذاری می‌کند، سپس سراغ همسایگان همسایگان می¬رود، تا زمانی که به گره موردنظر برسد. تعداد 'امواج' موردنیاز برای رسیدن به گره موردنظر، با فاصله برابر است.

برای پیدا کردن کوتاه‌ترین مسیر بین گره‌های i و j مراحل زیر طی می‌شوند (شکل 2-۱۴):

از گره i، که با “o” برچسب‌گذاری شده، شروع کن..
گره‌هایی که مستقیماً به i وصل شده‌اند را پیدا کن. فاصله آن‌ها را ”۱“ در نظر بگیر، و آن‌ها را در یک صف قرار بده.
اولین گره را که با “n” برچسب‌گذاری شده، از صف خارج کن (در گام اول n=1). گره‌های مجاور با آن را که برچسب نخورده‌اند، در گراف پیدا کن. آن‌ها را با n+1 برچسب‌گذاری کن و در صف قرار بده..
مرحله ۳ را تکرار کن تا زمانی که به گره موردنظر j برسی، یا هیچ گره دیگری در صف باقی نماند
فاصله بین i و j برابر است با برچسب j. اگر j هیچ برچسبی نخورده باشد، d_ij = ∞ در نظر گرفته می شود.

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

شکل 2-۱۴
اجرای الگوریتم BFS

• با شروع از گره نارنجی، که با 'o' برچسب‌گذاری شده، تمام همسایه‌هایش را شناسایی و با '۱' برچسب می‌گذاریم.
• سپس همسایه‌های برچسب نخورده تمام گره‌هایی که برچسب '۱' دارند را برچسب '۲' می‌زنیم، و به همین ترتیب ادامه می‌دهیم، به‌طوری‌که در هر تکرار شماره برچسب‌ها افزایش می‌یابد، تا زمانی که هیچ گره‌ای بدون برچسب نماند. طول کوتاه‌ترین مسیر، یا فاصله d0i بین گره ۰ و چپ‌ترین گره برابر است با d=3.

بخش 2-9
همبندی

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

در یک شبکه بدون جهت گره‌های i و j به هم متصل هستند، اگر مسیری بین آن‌ها وجود داشته باشد. این گره‌ها از هم جدا هستند، اگر چنین مسیری وجود نداشته باشد، که در این صورت داریم: d_ij = ∞. این مفهوم در شکل 2-۱۵a ، که شبکه‌‌ای با دو خوشه مجزا است، نشان داده شده است. درحالی‌که بین هر دو گره در یک خوشه مسیری وجود دارد (برای مثال گره‌های ۴ و ۶)، بین گره‌هایی که متعلق به خوشه‌های مجزا هستند(گره‌های ۱ و ۶)، هیچ مسیری وجود ندارد.

یک شبکه همبند است، اگر تمام جفت گره‌های شبکه به هم متصل باشند. یک شبکه ناهمبند است اگر حداقل یک جفت گره وجود داشته باشد، که به ازای آن d_ij = ∞ باشد. واضح است که شبکه نشان داده شده در شکل 2-۱۵a ناهمبند است. دو زیرشبکه آن را مؤلفه یا خوشه‌ می‌نامیم. یک مؤلفه، زیرمجموعه‌ای از گره‌های شبکه است، به‌طوری‌که بین هر دو گره متعلق به آن مؤلفه مسیری وجود داشته باشد، اما نتوان گره‌های بیشتری به این مجموعه اضافه کرد و درعین‌حال این خاصیت حفظ شود.

اگر یک شبکه شامل دو مؤلفه باشد، با استفاده از یک پیوند می‌توان آن‌ها را به هم متصل کرد، و بدین ترتیب شبکه را همبند نمود (شکل 2-۱۵b). چنین پیوندی را پل می‌نامند. در کل پل عبارت است از هر پیوندی که اگر حذف شود، شبکه نا¬همبند گردد.

درحالی‌که برای یک شبکه کوچک، از طریق جستجوی بصری می‌توان فهمید که آیا شبکه همبند است یا نه، برای شبکه‌هایی که شامل میلیون‌ها گره هستند، همبند یا ناهمبند بودن شبکه یک مسئله چالش‌برانگیز است. ابزارهای ریاضیاتی و الگوریتمی می‌تواند در شناسایی مؤلفه‌های همبند به ما کمک کنند. برای مثال، ماتریس مجاورت یک شبکه ناهمبند می‌تواند به شکل قطری-بلوکی بازچینی شود، به‌طوری‌که تمام عناصر غیر صفر ماتریس در بلوک‌های مربعی در طول قطر ماتریس قرار گیرد و سایر عناصر صفر باشند (شکل 2-۱۵ a ). هر بلوک مربعی متناظر با یک مؤلفه است. با استفاده از ابزارهای جبر خطی می‌توان تشخیص داد که آیا یک ماتریس قطری-بلوکی است یا نه، و بدین ترتیب مؤلفه‌های همبندی را شناسایی کرد.

در عمل، الگوریتم BFS روش کارآمدتری برای شناسایی مؤلفه‌های همبندی در شبکه‌های بزرگ به شمار می¬آید.

Connected and Disconnected Networks. — شکل 2-۱۵
شبکه‌های همبند و ناهمبند

یک شبکه کوچک شامل دو مؤلفه همبندی. درواقع، بین هر دو گره در مؤلفه (۱،۲،۳) یک مسیر وجود دارد، همان‌طور که بین هر دو گره در مؤلفه (۴،۵،۶) یک مسیر وجود دارد. اما بین گره‌هایی که متعلق به مؤلفه‌های متفاوت باشند، هیچ مسیری وجود ندارد.
پنل سمت راست ماتریس مجاورت شبکه را نشان می‌دهد. اگر شبکه مؤلفه‌های مجزا داشته باشد، ماتریس مجاورت را می‌توان به شکل بلوکی-قطری بازچینی کرد، به‌طوری‌که تمام عناصر غیر صفر ماتریس در بلوک‌های مربعی در طول قطر ماتریس گنجانده شوند و مابقی درایه‌ها صفر باشند.

• اضافه کردن یک تک پیوند، که پل نام دارد، و با رنگ خاکستری نشان داده شده، یک شبکه ناهمبند را به یک شبکه همبند با یک مؤلفه تبدیل می‌کند. حال بین هر دو گره در شبکه یک مسیر وجود دارد. درنتیجه ماتریس مجاورت را نمی‌توان به شکل بلوکی-قطری نوشت.

نکته 2-۶
پیدا کردن مؤلفه‌های همبندی یک شبکه

از یک گره تصادفی i شروع کرده و الگوریتم BFS را اجرا می‌کنیم (نکته 2-۵). تمام گره‌هایی را که به این طریق به آن‌ها دسترسی پیدا کرده‌ایم با n=1 برچسب‌گذاری می‌کنیم.
اگر تعداد گره‌های برچسب‌گذاری شده برابر با N باشد، شبکه همبند است. اگر تعداد گره‌های برچسب‌گذاری شده کمتر از N باشد، شبکه شامل تعدادی مؤلفه همبندی است. برای شناسایی این مؤلفه‌ها گام ۳ را اجرا کنید.
برچسب را افزایش دهید: nàn+1. یک گره بدون علامت مانند j را انتخاب کنید و آن را با n برچسب‌گذاری کنید. با استفاده از الگوریتم BFS تمام گره‌هایی را که از j قابل‌دسترسی هستند، پیدا کنید، و همه آن‌ها را با n برچسب‌گذاری کنید. به گام ۲ بازگردید.

بخش 2-۱۰
ضریب خوشه‌بندی

ضریب خوشه‌بندی بیان می‌کند که همسایگان یک گره با چه درجه‌ای به همدیگر متصل شده‌اند. برای یک گره i با درجه k_iضریب خوشه‌بندی محلی طبق رابطه زیر تعریف می‌شود [۱۲]:

$C_i = \frac{{2L_i }}{{k_i \left( {k_i - 1} \right)}} \hspace{20 mm} (2 . 15)$

که در آن L_i عبارت است از تعداد پیوندهای بین k_i همسایه گره i. دقت کنید که مقدار C_i بین ۰ و ۱ است (شکل 2-۱۶a):

C_i = 0 ، اگر هیچ‌کدام از همسایه‌های گره i به هم متصل نباشند.
C_i = 1اگر همسایه‌های گره i یک گراف کامل تشکیل دهند، یعنی همه آن‌ها به هم متصل باشند.
• C_iاحتمال این رخداد است که دو همسایه یک گره به هم متصل باشند. بنابراین، C = 0.5 بدین معنی است که ۵۰٪ احتمال دارد که دو همسایه یک گره به هم متصل باشند.

به‌طور خلاصه، C_i چگالی پیوندهای محلی شبکه را اندازه‌گیری می‌کند: هرچه همسایه‌های گره i با چگالی بیشتری به هم متصل باشند، ضریب خوشه‌بندی محلی آن بالاتر است.

Clustering Coefficient. — شکل 2-۱۶
ضریب خوشه‌بندی

ضریب خوشه‌بندی محلی، *C_i* ، برای یک گره مرکزی به درجه ki = 4، برای سه پیکربندی متفاوت از همسایگانش. ضریب خوشه‌بندی محلی، چگالی محلی پیوندهای همسایگی یک گره را اندازه‌گیری می‌کند.

یک شبکه کوچک که ضریب خوشه‌بندی محلی هر گره در کنار آن نشان داده شده است. همچنین میانگین ضریب خوشه‌بندی طبق رابطه (2-۱۶) و ضریب خوشه‌بندی سراسری *C_Δ*، که در بخش 2-۱۲ در رابطه (2-۱۷) آمده، نیز نمایش داده شده‌اند.
دقت کنید که برای گره‌های با درجه *k_i* = 0,1 ضریب خوشه‌بندی برابر صفر است.

درجه خوشه‌بندی کل شبکه با میانگین ضریب خوشه‌بندی، ، به دست می‌آید، که نشان‌دهنده میانگین C_iها روی تمام گره‌ها i=1,…,N است [۱۲].

$\left\langle C \right\rangle = \frac{1}{N}\sum\limits_{i = 1}^N {C_i } \hspace{20 mm} (2 . 16)$

درجه خوشه¬بندی 〈C〉 عبارت است از احتمال اینکه دو همسایه یک گره دلخواه به هم متصل باشند.

بااینکه رابطه (2-۱۶) برای شبکه‌های بدون جهت تعریف شده، می‌توان آن¬را برای گراف‌های جهت‌دار و وزن‌دار نیز تعمیم داد [۱۳،۱۴،۱۵،۱۶]. در متون مربوط به شبکه با ضریب خوشه‌بندی سراسری نیز مواجه می¬شویم که در بخش موضوعات پیشرفته 2-A در مورد آن بحث شده است.

بخش 2-۱۱
جمع¬بندی

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

بسیاری از شبکه‌هایی که در علم شبکه آن‌ها را مطالعه می‌کنیم، شامل هزاران یا حتی میلیون‌ها گره و پیوند هستند (جدول 2-۱). برای کاوش این شبکه‌ها، نیاز داریم از گراف‌های کوچکی که در شکل 2-۱۷ نشان داده شده، فراتر برویم. در شبکه پروتئین-پروتئین مخمر شکل 2-۴aa، یک چشم‌انداز اجمالی از مباحثی که قرار است مطرح شود، ارائه شده است. شبکه پیچیده‌تر از آن است که با بررسی بصری بتوان ویژگی‌هایش را فهمید. بنابراین نیاز داریم تا برای مشخص کردن توپولوژی آن به ابزارهای علوم شبکه روی‌آوریم.

graphology. — شکل 2-۱۷
گراف شناسی

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

**گراف بدون جهت**
شبکه‌ای که پیوندهایش جهت مشخصی ندارند.
مثال: اینترنت، شبکه توزیع برق، شبکه همکاری علمی

**طوقه**
در بسیاری از شبکه‌ها گره‌ها با خودشان تعاملی ندارند، بنابراین درایه‌های قطری ماتریس مجاورت صفر هستند، Aii = 0, i = 1,2,…N. در برخی سیستم‌ها امکان تعامل با خود وجود دارد، ارتباط یک گره با خودش را طوقه یا خود-پیوندی می¬نامیم.
مثال: وب، شبکه برهم‌کنش پروتئین‌ها.

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

**شبکه جهت‌دار**
شبکه‌ای که پیوندها جهت مشخص دارند.
مثال: وب، تماس‌های تلفن همراه، ارجاعات علمی.

**شبکه وزن‌دار**
شبکه‌ای که به پیوندهایش وزن، قدرت، یا پارامتر جریان تخصیص می‌یابد. اگر بین گره i و j پیوندی با وزن *w_ij*باشد، درایه¬های ماتریس مجاورت، به شکل *A_ij* = *w_ij* خواهند بود. برای شبکه‌های بدون وزن (باینری)، ماتریس مجاورت تنها نشان‌دهنده وجود (*A_ij* = 1) یا عدم وجود (*A_ij* = 0) پیوند است.
مثال: تماس‌های تلفن همراه، شبکه پست الکترونیکی.

**گراف کامل (کلیک)**
در یک گراف کامل یا کلیک، تمام گره‌ها به هم متصل هستند.
مثال: بازیگرانی که در یک فیلم بازی می‌کنند، که در شبکه بازیگران همگی به هم متصل هستند.

اجازه دهید از معیارهایی که تاکنون معرفی کرده‌ایم، برای کشف برخی از ویژگی‌های اساسی این شبکه‌ها استفاده کنیم. گراف بدون جهتی که در شکل 2-4a نمایش داده شده، تعداد N = 2,018 پروتئین به‌عنوان گره، و L = 2,930 برهم¬کنش به‌عنوان پیوند دارد. بنابراین طبق (2-۲)، میانگین درجاتش برابر با = 2.90 است، بدین معنی که یک پروتئین معمولی با تقریباً دو یا سه پروتئین تعامل دارد. اما این عدد کمی گمراه‌کننده است. درواقع توزیع درجه p_k که در شکل 2-4a نشان داده شده، بیان می‌کند که اکثریت قریب به‌اتفاق گره‌ها تعداد پیوند کمی دارند. نگاهی موشکافانه¬تر مشخص می¬کند که در این شبکه، ۶۹٪ گره‌ها کمتر از سه پیوند دارند. این تعداد زیاد گره با پیوندهای کم، به همراه تعداد کمی گره با پیوندهای زیاد که هاب نامیده می¬شوند و بزرگ‌ترین آن‌ها ۹۲ پیوند دارد، در شبکه همزیستی دارند. این تفاوت گسترده در درجه نتیجه خاصیت بدون مقیاس بودن شبکه است، که در فصل ۴ بحث شده است. خواهیم دید که شکل توزیع درجه تعیین‌کننده طیف گسترده‌ای از خواص شبکه¬ها از تاب‌آوری شبکه گرفته تا انتشار ویروس‌ها است.

الگوریتم جستجوی سطح- اول (نکته 2-۵) به ما کمک مي‌کند قطر شبکه (14=dmax ) را محاسبه کنیم. ممکن است انتظار تغییر گسترده‌ای در فاصله را داشته باشیم، چراکه برخی گره‌ها به یکدیگر نزدیک هستند، درحالی‌که دیگر گره‌ها ممکن است از یکدیگر دور باشند. توزیع فاصله (شکل 2-۱۸a) نشان می‌دهد p_d مقدار حداکثری بین ۵ و ۶ دارد، یعنی بیشتر فاصله‌ها کوتاه، و در حدود = 5.61 هستند. همچنین p_d برای dهای بزرگ به‌سرعت تنزل می‌یابد، بدین معنی که فواصل بزرگ وجود ندارند. درواقع، واریانس فاصله‌ها عبارت است از σ_d = 1.64، که نشان‌دهنده این است که بیشتر طول مسیرها در محدوده نزدیک به 〈d〉 قرار دارد. این‌ها نمونه‌هایی از ویژگی‌هایی است که در فصل ۳ بحث خواهد شد.

الگوریتم جستجوی سطح اول همچنین نشان می‌دهد که شبکه برهم¬کنش پروتئینی هم¬بند نیست و شامل ۱۸۵ مؤلفه است که به شکل خوشه و گره‌های مجزا در شکل 2-۴a نشان داده شده‌اند. بزرگ‌ترین آن‌ها که به آن مؤلفه غول‌پیکر می‌گویند، ۱،۶۴۷ گره از ۲،۰۱۸ گره را شامل می‌شود، و بقیه مؤلفه‌ها کوچک هستند. همان‌طور که در فصل‌های بعدی خواهیم دید، وجود این نسبت از گره‌ها در یک مؤلفه در شبکه¬های واقعی رایج است.

میانگین ضریب خوشه‌بندی یک شبکه برهم¬کنش پروتئینی برابر است با = 0.12، که همان‌طور که در فصل‌های بعدی خواهیم دید، نشان‌دهنده میزان قابل‌توجهی از خوشه‌بندی محلی است. نکته دیگری که مشخص می¬شود، وابستگی ضریب خوشه‌بندی به درجه گره، یا تابع C(k) است (شکل 2-۱۸b). این واقعیت که C(k) برای kهای بزرگ کاهش می‌یابد، نشان می‌دهد که ضریب خوشه‌بندی محلی گره‌های کوچک به‌طور قابل‌توجهی بزرگ‌تر از ضریب خوشه‌بندی هاب‌ها است. بنابراین، گره‌های با درجه کم در همسایگی‌های متراکم شبکه قرار می‌گیرند، درحالی‌که همسایگی هاب‌ها بسیار خلوت‌تر است. این امر نتیجه ویژگی سلسله‌مراتب است که در فصل ۹ توضیح داده شده است.

درنهایت بررسی بصری شبکه الگوی جالبی را نشان می‌دهد: هاب‌ها تمایل دارند که به گره‌های کوچک متصل شوند (شکل 2-۴a) و شبکه را به شکل منظومه شمسی درآورند (قطب و اقمار). این امر نتیجه همبستگی‌های درجه‌ای است که در فصل ۷ بررسی شده است. چنین همبستگی‌هایی روی تعدادی از فرایندهای مبتنی بر شبکه، از پدیده انتشار گرفته تا تعداد گره‌های موردنیاز برای کنترل شبکه تأثیر می‌گذارد.

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

Characterizing a Real Network. — شکل 2-۱۸
توصیف یک شبکه واقعی
شبکه برهم¬کنش پروتئین-پروتئین مخمر متناوباً توسط زیست‌شناسان و دانشمندان علم شبکه مطالعه می‌شود. نمودار ارتباطات این شبکه با جزئیات در شکل 2-۴a نشان داده شده است. این شبکه شامل N=2,018 گره و L=2,930 پیوند است و دارای مؤلفه بزرگی است که ۸۱٪ پروتئین‌ها را به هم متصل می‌کند. همچنین تعدادی مؤلفه کوچک‌تر و تعداد زیادی پروتئین منفرد که به هیچ گره دیگری متصل نیستند در آن به چشم می¬خورد.

توزیع فاصله، *p_d*، برای شبکه پروتئین-پروتئین نشان‌دهنده احتمال این است که کوتاه‌ترین مسیر بین دو گره‌ای که به‌طور تصادفی انتخاب شده‌اند، برابر با d باشد. خط عمودی خاکستری میانگین طول مسیر را نشان می‌دهد، که برابر است با *〈d〉* =5.61.

وابستگی میانگین ضریب خوشه‌بندی محلی به درجه گره، k. تابع C(k) از میانگین گرفتن روی ضریب خوشه‌بندی محلی تمام گره‌ها با درجه k یکسان به دست می‌آید.

بخش 2-۱۲
تمرین

Königsberg Problem. — شکل 2-۱۹
مسئله کونیگسبرگ

مسئله کونیگسبرگ
کدام مورد از شکل 2-۱۹ را می‌توانید بدون برداشتن مداد از روی کاغذ بکشید، درحالی‌که از روی هیچ خطی بیشتر از یک‌بار عبور نکنید؟ چرا؟
نمایش ماتریسی
فرض کنید A یک ماتریس مجاورت NxNبرای یک شبکه بدون جهت، بدون وزن و بدون طوقه است. فرض کنید ۱ یک بردار ستونی از N درایه باشد که همگی برابر با ۱ هستند. به‌بیان‌دیگر، 1 =^T(1, 1, ..., 1) ) ، که در آن T نشان‌دهنده عملگر ترانهاده است. عبارات زیر را با استفاده از عملگرهای ریاضی و ماتریسی مانند ضرب یک عدد ثابت، ضرب سطر در ستون و ترانهاده به‌غیراز نماد جمع S، بنویسید:
1. بردار k که عناصرش درجه‌های k_iبرای گره‌های i=1,2,…N است
2. تعداد کل پیوندهای شبکه: L
3. تعداد مثلث‌های موجود در شبکه: T. مفهوم مثلث عبارت است از سه گره که تمام آن‌ها به یکدیگر متصل هستند (راهنمایی: می‌توانید از پیمایش ماتریس استفاده کنید).
4. بردار k_nn که عنصر i آن عبارت است از مجموع درجات همسایگان گره i.
5. بردار k_nn که عنصر i آن عبارت است از مجموع درجات همسایگان دوم گره i.
نمایش گراف
ماتریس مجاورت برای بسیاری از محاسبات تحلیلی، روش مناسبی از مدل¬سازی گراف است. اما زمانی که نیاز داریم یک شبکه را در کامپیوتر ذخیره کنیم، می‌توانیم از لیست پیوندی در قالب ماتریس Lx2، که سطرهای آن شامل گره‌های شروع و پایان i و j از هر پیوند هستند، استفاده کنیم. بدین ترتیب در مصرف حافظه صرفه‌جویی خواهد شد. لیست پیوندی مذکور را برای شبکه‌های (a) و (b) در شکل 2-۲۰ ایجاد نمایید:
شکل 2-۲۰
نمایش گراف
1. گراف بدون جهت با ۶ گره و ۷ پیوند.
2. • گراف جهت‌دار با ۶ گره و ۸ پیوند جهت‌دار
1. ماتریس‌های مجاورت متناظر را به دست آورید؟
2. لیست‌های پیوندی متناظر را به دست آورید؟
3. برای شبکه شکل 2-۲۰a میانگین ضریب خوشه‌بندی را تعیین کنید.
4. اگر برچسب‌های گره‌های ۵ و ۶ را در شکل 2-۲۰a باهم تعویض کنیم، چه تغییری در ماتریس مجاورت و لیست پیوندی ایجاد می‌شود؟
5. چه نوع اطلاعاتی را نمی‌توان از نمایش لیست پیوندی به دست آورد، درحالی‌که از ماتریس مجاورت قابل استنتاج است؟
6. در شبکه (a) چند مسیر (با امکان تکرار گره‌ها و پیوندها) به طول ۳ وجود دارد، که از گره ۱ شروع شده و به گره ۳ ختم می‌شود؟ در شبکه (b) چطور؟
7. با کمک کامپیوتر تعداد دورها با طول ۴ در هر دو شبکه را به دست آورید.
درجه، ضریب خوشه‌بندی، و مؤلفه‌ها
1. یک شبکه بدون جهت به اندازه N را در نظر بگیرید، که در آن هر گره درجه k = 1 دارد. N باید چه شرطی داشته باشد؟ توزیع درجه شبکه چیست؟ این شبکه چند مؤلفه خواهد داشت؟
2. حال یک شبکه را در نظر بگیرید که در آن هر گره درجه k = 2 دارد و ضریب خوشه‌بندی برابر با C = 1 است. این شبکه چه شکلی خواهد داشت؟ در این صورت N باید چه شرطی داشته باشد؟
شبکه‌های دوبخشی
شبکه دوبخشی شکل 2-۲۱ را در نظر بگیرید.
1. ماتریس مجاورت آن را تشکیل دهید. چرا این ماتریس بلوکی-قطری است؟
2. ماتریس مجاورت دو طرح آن را به ترتیب روی شبکه‌های بنفش و سبز ایجاد کنید.
3. میانگین درجات گره‌های بنفش و همچنین گره‌های سبز را در شبکه دوبخشی محاسبه کنید.
4. میانگین درجات را در هر دو طرح شبکه محاسبه کنید. آیا تفاوت بین این مقادیر با مقادیر به‌دست‌آمده در مرحله قبل، دور از انتظار است ؟
شکل 2-۲۱
شبکه دوبخشی
شبکه دوبخشی با ۶ گره در یک مجموعه و ۵ گره در مجموعه دیگر، که با ۱۰ پیوند به هم متصل شده‌اند.
شبکه دوبخشی- ملاحظات عمومی
یک شبکه دوبخشی با N₁ و N₂ گره را در دو مجموعه در نظر بگیرید.
1. بیشینه تعداد پیوندها L_max در شبکه چقدر می‌تواند باشد؟
2. ین شبکه در مقایسه با یک شبکه غیر دوبخشی با اندازه N = N₁ + N₂ ، چه تعداد پیوند کمتر خواهد داشت؟
3. • اگر N₁‹‹N₂، در مورد تراکم شبکه، که عبارت است از تعداد پیوندها بخش‌بر بیشینه تعداد پیوندها، L_max چه می‌توان گفت؟
4. • رابطه N₁, N₂ ، و میانگین درجات دو مجموعه در شبکه دوبخشی 〈k₁〉 و 〈k₂〉 را پیدا کنید.

بخش 2-۱۳
مباحث پیشرفته 2-A
ضریب خوشه‌بندی سراسری

در متون مربوط به علم شبکه گاهی با ضریب خوشه‌بندی سراسری مواجه می‌شویم، که تعداد کل مثلث‌های بسته در شبکه را اندازه می‌گیرد. درواقع L_i در رابطه (2-۱۵) عبارت است از تعداد مثلث‌هایی که گره i در آن شرکت دارد، به‌طوری‌که هر پیوند بین دو همسایه i مثلث را ببندد (شکل 2-۱۷). بنابراین درجه خوشه‌بندی سراسری شبکه را می‌توان با استفاده از ضریب خوشه‌بندی سراسری به دست آورد:

$C_\Delta = \frac{{3 \times NumberOfTriangles}}{{NumberOfConnectedTriples}} \hspace{20 mm} (2 . 17)$

که در آن سه‌تایی‌های متصل عبارت است از مجموعه مرتب از سه گره ABC به‌طوری‌که A به B و B به C متصل است. برای مثال مثلث A، B، C از سه سه‌تایی ABC، BCA و CAB تشکیل شده است. در مقابل، زنجیره گره‌های متصل A، B، C، که در آن B به A و C متصل است، اما A به C متصل نیست، یک سه‌تایی باز ABC را تشکیل می‌دهد. ضریب ۳ در رابطه (2-۱۷) به این دلیل آمده که هر مثلث در شمارش سه‌تایی‌ها سه بار شمرده می‌شود. ریشه ضریب خوشه‌بندی سراسری به متون مربوط به شبکه‌های اجتماعی در دهه ۱۹۴۰ [۱۷، ۱۸] برمی‌گردد، که در آن C_Δ اغلب نسبت سه‌تایی‌های تراگذر خوانده می‌شود.

دقت کنید که میانگین ضریب خوشه‌بندی ‹C› که در (2-۱۶) تعریف شده، و ضریب خوشه‌بندی سراسری (2-۱۷) معادل نیستند. شبکه‌ای دو ستاره با N گره را در نظر بگیرید که در آن گره‌های ۱ و ۲ به یکدیگر و به تمام گره‌های دیگر متصل هستند و هیچ پیوند دیگری در شبکه وجود ندارد. ضریب خوشه‌بندی محلی C_i برای i ≥ 3 برابر با ۱ است، و برای i=1,2 برابر است با 2/(N-1). بنابراین میانگین ضریب خوشه‌بندی شبکه برابر است با = 1-O(1)، درحالی‌که ضریب خوشه‌بندی سراسری برابر است با C_Δ ~ 1/N. در شبکه‌های کوچک‌تر دو تعریف مقادیر قابل‌مقایسه‌تری می‌دهند، اما همچنان باهم متفاوت‌اند [۱۹]. برای مثال، برای شبکه شکل 2-۱۶b داریم: = 0.31 و C_Δ = 0.375

بخش 1.2 پل‌های کونیگسبرگ

بخش 2.2 شبکه‌ و گراف‌

بخش 3-2 درجه، میانگین درجه و توزیع درجه

درجه

میانگین درجه

توزیع درجه

بخش 2-۴ ماتریس مجاورت

بخش 2-۵ Real شبکه‌های واقعی تنک هستند

بخش 2-۶ شبکه‌های وزن‌دار

بخش 2-۷ شبکه‌های دوبخشی

بخش 2-8 مسیرها و فواصل

کوتاه‌ترین مسیر

قطر شبکه

میانگین طول مسیر

بخش 2-9 همبندی

بخش 2-۱۰ ضریب خوشه‌بندی

بخش 2-۱۱ جمع¬بندی

بخش 2-۱۲ تمرین

بخش 2-۱۳ مباحث پیشرفته 2-Aضریب خوشه‌بندی سراسری

Section 1.14 Bibliography