مقدمه‌ای بر شبکه‌های گراف

۱. گراف چیست و چرا گراف؟

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

شکل: گراف شبکه – موجودیت‌های مرتبط با یکدیگر مطابق با اتصالات

   

2. داده‌ها به عنوان گراف: نمونه‌ها

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

·         شبکه‌های رویداد

·         مسیرهای بیماری

·         شبکه‌های غذایی

·         شبکه‌های ذرات

·         شبکه‌های زیرزمینی

·         شبکه‌های اجتماعی

·         شبکه‌های ارتباطی

·         شبکه‌های استنادی

·         شبکه نورون‌ها (مغز)

·         شبکه‌های اقتصادی

·         مولکول‌ها

·         اشکال سه بعدی

·         گراف-کد کامپیوتری بین توابع مختلف

در زیر توضیح مختصری از شبکه‌های گراف بالا ارائه شده است.

 

گراف‌های رویداد:

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

شکل ۱: نمونه‌ای از گراف رویداد.

 

مسیرهای بیماری:

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

شکل ۲: مسیرهای بیماری

 

شبکه‌های غذایی:

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

شکل: یک شبکه غذایی ساده

 

 شبکه‌های ذرات

 مرجع:

https://commons.wikimedia.org/wiki/File:Elementary_particle_interactions.svg

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

سازماندهی گراف به شرح زیر است: ردیف بالایی رئوس (لپتون‌ها و کوارک‌ها) ذرات ماده هستند. ردیف دوم رئوس (فوتون، W/Z، گلوئون) ذرات میانجی نیرو هستند؛ و ردیف پایین بوزون هیگز است.

شکل: مثالی از شبکه ذرات در فیزیک

 

شبکه زیرزمینی:

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

شکل: نقشه توپولوژی متروی متروی لندن

 

گراف شبکه‌های اجتماعی

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

شکل زیر یک گراف معمولی از یک پلت فرم رسانه‌های اجتماعی به عنوان لینکدین یا فیس بوک یا X (قبلاً توییتر) را نشان می‌دهد.

شکل: یک مدل معمولی گراف شبکه اجتماعی (به عنوان مثال، لینکدین)

 

نمودار شبکه استناد:

در اینجا یک مثال تعاملی خوب از یک گراف شبکه استناد وجود دارد: https://signsat40.signsjournal.org/cocitation/interactive/

 

شبکه نورون‌ها:

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

شکل: شبکه‌ای از نورون‌ها در مغز

 

گراف‌های دانش:

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

شکل: گراف‌های دانش

 

کد نرم افزار:

شکل: کد نرم افزار به عنوان یک شبکه گراف

 

4. گراف‌ها برای یادگیری ماشینی و یادگیری عمیق: تصویر در مقابل پردازش نوشتار در مقابل پردازش گراف برای ML/DL

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

این ما را به موضوع بعدی بحث هدایت می‌کند - اجازه دهید بفهمیم چرا پردازش شبکه‌های گراف برای یادگیری ماشینی و عمیق دشوار است.

چرا پردازش شبکه‌های گراف برای یادگیری عمیق دشوار است؟

باید تاکید کرد که در مقایسه با تصاویر یا متن؛ پردازش گراف‌ها برای یادگیری عمیق نسبتاً دشوار است. این به این دلیل است که شبکه‌های گراف دارای اندازه دلخواه و توپولوژی پیچیده‌ای هستند که در شکل زیر نشان داده شده است.

شکل: شبکه‌های گراف – بدون ترتیب گره یا نقطه مرجع ثابت

 

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

شکل: گراف در مقابل تصویر (شبکه پیکسل‌ها) در مقابل متن (توالی)

 

فرآیند یادگیری عمیق در گراف‌ها چیست؟

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

شکل: فرآیند یادگیری عمیق End-to-End در گراف‌ها (بدون هیچ گونه مهندسی ویژگی‌های انسانی)

 

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

شکل: نگاشت گره‌های یک گراف در یک جاسازی “d” بعدی برای فرآیند یادگیری عمیق

 

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

·         روش‌های سنتی – این روش‌ها شامل گرافلت‌ها، هسته‌های گراف می‌شود

·         روش‌های جاسازی گره – DeepWalk و Node2Vec

·         گراف شبکه عصبی – گراف کانولوشن شبکه عصبی

·         گراف دانش و یادگیری و سپس،

·         مدل‌های مولد عمیق برای گراف

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

 

5. اجزای یک گراف و انتخاب‌های طراحی:

سپس، اجازه دهید ببینیم که اجزای یک گراف یا یک شبکه چیست - شبکه از دو نوع شی تشکیل شده است. ابتدا اشیاء یا موجودیت‌هایی داریم که به عنوان گره‌ها یا رئوس شناخته می‌شوند و سپس تعاملاتی بین این گره‌ها داریم که به صورت پیوند یا یال نشان داده می‌شوند - کل دامنه یک شبکه یا یک گراف نامیده می‌شود.

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

شکل: اجزای یک گراف

 

انتخاب‌های طراحی:

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

گراف‌های بدون جهت در مقابل جهت‌دار:

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

شکل: گراف‌های بدون جهت

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

شکل: گراف‌های جهت‌دار

 

گراف‌های بدون جهت: درجه گره

درجه گره تعداد لبه‌های مجاور یک گره معین را نشان می‌دهد. به عنوان مثال، گره A در شکل زیر دارای درجه 4 است زیرا 4 لبه به آن متصل است.

شکل: درجه گره در یک گراف بدون جهت

 

گراف‌های بدون جهت: میانگین درجه گره:

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

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

موارد فوق برای "گراف‌های بدون جهت" معتبر است.

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

 

گراف‌های جهت‌دار: درجه گره

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

ممکن است از شکل زیر متوجه شوید که گره C دارای درجه درونی 2 و درجه بیرونی 1 است.

شکل: گراف‌های جهت‌دار – در مقطع و خارج

6. گراف‌های دوبخشی و گراف‌های دوبخشی تاشو

گراف دوبخشی [دوبخشی ~ 2 پارتیشن]:

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

·         نویسندگان علمی به مقالاتی که تألیف کرده‌اند پیوند داده‌اند.

·         بازیگران مرتبط با فیلم‌هایی که در آن ظاهر شدند.

·         کاربران به فیلم‌هایی که تماشا کرده‌اند پیوند داده‌اند.

شکل: گراف دوبخشی

 

گراف دوبخشی تاشو:

پس از بحث در مورد گراف دوبخشی، ارزش آن را دارد که در مورد گراف دوجانبه تا شده صحبت کنیم - با در نظر گرفتن مثالی که در آن گراف دوبخشی داریم همانطور که در زیر نشان داده شده است که به نویسندگان علمی (1، 2، 3، 4، 5، 6) مرتبط با انتشارات اشاره می‌کند (A, B, C, D).

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

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

سپس این نوع گراف را Folded یا Projected Bipartite Graph می‌نامند. همانطور که در شکل بالا نشان داده شده است، از آنجایی که 1،2،3 مشترکاً انتشارات A را تالیف کرده اند، آنها به هم متصل هستند. به طور مشابه، از آنجایی که گره‌های 2 و 5 انتشارات 4، 5، 6، 7 را با هم نویسندگی کرده‌اند، همانطور که در بالا نشان داده شده است به هم متصل می‌شوند.

مشابه موارد فوق، می‌توانیم یک شبکه تا شده مطابق با انتشارات A، B، C و D ایجاد کنیم و مانند شکل زیر یک شبکه fold به دست خواهیم آورد.

شکل: شبکه fold

از شکل بالا می توان دریافت که از آنجایی که انتشارات B، C، D با 5 تالیف مشترک بوده‌اند، به هم متصل شده‌اند و از آنجایی که انتشارات B و A با 2 تالیف مشترک هستند، به هم متصل شده‌اند.

 

7. چگونه گرافها را به صورت عددی نمایش دهیم؟

ماتریس مجاورت برای گراف‌های بدون جهت:

بازنمایی عددی گراف‌ها مسئله جالبی است. یکی از راه‌های بازنمایی عددی گراف‌ها از طریق «ماتریس مجاورت» است. به عنوان مثال، در مورد شبکه s که در شکل زیر نشان داده شده است که 4 گره ahs دارد، ماتریس مجاورت یک ماتریس مربع به اندازه 4×4 خواهد بود و ورودی‌های 0 یا 1 خواهد داشت. عنصر ij ماتریس دارای ورودی ۱ خواهد بود اگر گره‌های I و j به هم متصل هستند و ورودی 0 اگر گره‌های I و j متصل نیستند.

با قانون فوق، ماتریس مجاورت یک شبکه 4 گره به صورت زیر نمایش داده می‌شود:

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

 

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

 

ماتریس مجاورت یک گراف جهت‌دار:

اگر گراف جهت‌دار باشد، ماتریس مجاورت آن متقارن نخواهد بود. زیرا اگر گره I به j متصل شود، عنصر Aij برابر با 1 خواهد بود، اما از آنجایی که گره j به I متصل نیست، عنصر Aji 0 خواهد بود.

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

 

درجه گره از نظر ماتریس مجاورت:

من در مورد درجه گره در بخش 5 صحبت کرده‌ام. پس از به دست آوردن ماتریس مجاورت، می‌توان درجه گره را بر حسب ماتریکس مجاورت بیان کرد.

برای یک گراف بدون جهت،

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

برای یک گراف جهت‌دار،

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

 

ماتریس‌های مجاورت پراکنده هستند زیرا شبکه‌ها گراف‌های پراکنده هستند:

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

می‌توان تصور کرد که - شبکه اجتماعی انسانی، شبکه استنادی بسیار پراکنده است [این امکان وجود ندارد که همه به همه متصل باشند یا همه نویسندگان همه انتشارات را داشته باشند!]. بنابراین، به ندرت ماتریس مجاورت یک ماتریس متراکم خواهد بود.

بازنمایی گراف به عنوان یک لیست لبه:

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

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

شکل: بازنمایی گراف به عنوان لیست لبه

 

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

 

بازنمایی گراف به عنوان یک لیست مجاورت:

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

شکل: بازنمایی گراف به عنوان یک لیست مجاورت

 

 8. گره‌ها و ویژگی‌های لبه:

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

مثال:

·         یک لبه می‌تواند وزنی داشته باشد که نشان می‌دهد چقدر رابطه قوی است.

·         این می‌تواند یک نوع رابطه مبتنی بر دوست، رابطه همکار داشته باشد.

·         علامت - دوست یا دشمن

لبه‌ها می‌توانند ویژگی‌های مختلفی داشته باشند - اگر تماس تلفنی باشد - مدت زمان آن.

گره‌ها بسته به موجودیت مورد نظر می‌توانند دارای ویژگی‌هایی مانند سن، جنسیت، مکان باشند.

بازنمایی خواص در ماتریس مجاورت:

همچنین می‌توان وزن‌هایی را در ماتریس مجاورت نشان داد همانطور که در شکل زیر نشان داده شده است - در اینجا وزن نشان دهنده قدرت اتصال است.

شکل: گراف وزنی بدون جهت

چند-گراف

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

شکل: نمونه‌ای از چند-گراف