گراف

گراف ساختاری است که اشیاء و اتصالات میان آن‌ها را نشان می‌دهد. در علوم کامپیوتر، شبکه‌های عصبی بر روی ساختارهای داده گرافی عمل می‌کنند، جایی که روابط (یال‌ها) موجودیت‌ها (گره‌ها) را به هم متصل می‌کنند. از نظر ریاضی، یک گراف G به صورت G = (V, E) تعریف می‌شود، که V مجموعه گره‌ها/رأس‌ها و E مجموعه یال‌ها/لینک‌ها است. هر یال جفتی از رأس‌ها را نشان می‌دهد که اتصالی بین آن‌ها وجود دارد.

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

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

ماتریس های توصیف گر گراف

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

۱. ماتریس مجاورت (Adjacency Matrix)

ماتریس مجاورت (A) یک ماتریس مربعی با ابعاد n×n است (که n تعداد گره‌هاست) و درایه 𝑎𝑖𝑗 در این ماتریس نشان‌دهنده وجود یا عدم وجود یال بین رأس 𝑖 و رأس 𝑗 است.

در یک گراف ساده (بدون جهت)، اگر یالی بین رأس 𝑖 و 𝑗 وجود داشته باشد، 𝑎𝑖𝑗=1 و در غیر این صورت 𝑎𝑖𝑗=0 است.

برای گراف‌های وزن‌دار هر عدد روی یال نشان دهنده وزن ارتباط بین دو گره می باشد، در این حالت برای ماتریس مجاورت 𝑎𝑖𝑗 می‌تواند وزن یال را نشان دهد.

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

توان‌های ماتریس مجاورت (𝐴^𝑘)، تعداد مسیرهای به طول 𝑘 بین دو رأس را نشان می‌دهند.

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

2. ماتریس درجه (Degree Matrix)

ماتریس درجه یک ماتریس قطری D است که تعداد یال‌های متصل به هر گره (درجه گره) را نشان می‌دهد:

• برای گره i، مقدار D[i,i] برابر است با تعداد یال‌های متصل به آن گره.
• سایر درایه‌ها صفر هستند ( D[i,j]=0 اگر i≠j ).

3. ماتریس لاپلاسین (Laplacian Matrix)

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

L = D−A

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

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

4. ماتریس وقوع (Incidence Matrix)

ماتریس وقوع (یا Incidence Matrix) یک ماتریس مستطیلی است که روابط بین گره‌ها (رأس‌ها) و یال‌ها را نشان می‌دهد. این ماتریس برای گرافی با n گره و m یال، ابعاد n×m دارد و برای تحلیل جریان‌ها، مدارها و ساختارهای گرافی در حوزه‌هایی مانند فیزیک، مهندسی و یادگیری گرافی مفید است.

در گراف بدون جهت: هر ستون مربوط به یک یال است و دو درایه 1 در ردیف‌های گره‌های متصل به آن یال قرار می‌گیرد (سایر درایه‌ها 0 هستند).

• در گراف جهت‌دار: برای یال ek​ از گره i (مبدأ) به گره j (مقصد) داریم:

این ماتریس برای محاسبه‌هایی مانند جریان‌های گرافی (مثلا در شبکه‌های الکتریکی) استفاده می‌شود و پایه‌ای برای الگوریتم‌های بهینه‌سازی است.

5. ماتریس ویژگی (Feature Matrix)

ماتریس ویژگی (یا Node Feature Matrix) ماتریسی است که ویژگی‌های عددی یا برداری هر گره را ذخیره می‌کند. این ماتریس برای ورودی به مدل‌های یادگیری ماشین، به‌ویژه GNNها، حیاتی است و گراف را از حالت انتزاعی به داده‌های قابل پردازش تبدیل می‌کند.

• ابعاد ماتریس ویژگی معادل n×f است، که n تعداد گره‌ها و f تعداد ویژگی‌ها (dimensions) هر گره است.
• هر ردیف مربوط به یک گره است و مقادیری مانند برچسب‌ها، embedding ها یا ویژگی‌های استخراج‌شده (مثل سن در شبکه اجتماعی یا جرم اتمی در مولکول) را شامل می‌شود.

در GNNها، این ماتریس به عنوان X (input features) استفاده می‌شود و در فرآیند انتشار پیام به‌روزرسانی می‌گردد.
مثال: برای گرافی با 3 گره و 2 ویژگی (مثلاً “سن” و “درآمد”) ماتریس ویزگی به صورت زیر تعریف می شود:

(ردیف اول: گره 1 با سن 25 و درآمد 50000)

کاربرد ماتریس‌های توصیف‌گر در GNNها

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

• ماتریس مجاورت در فرآیند انتشار پیام (Message Passing) برای تعیین همسایگان هر گره استفاده می‌شود.
• ماتریس لاپلاسین در شبکه‌های کانولوشنی گرافی (GCNها) برای نرمال‌سازی ویژگی‌ها و بهبود پایداری مدل کاربرد دارد.
• ماتریس درجه برای تنظیم وزن همسایگان در فرآیند یادگیری استفاده می‌شود.

این ماتریس‌ها به GNNها امکان می‌دهند تا روابط پیچیده بین گره‌ها را مدل کنند، مثلاً در پیش‌بینی لینک یا طبقه‌بندی گره‌ها.

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

برای کار با ماتریس‌های گراف، می‌توانید از کتابخانه‌های NetworkX و NumPy استفاده کنید. در ادامه، مراحل اولیه برای ایجاد و تحلیل ماتریس‌های گراف ارائه می‌شود.

نصب کتابخانه‌ها

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

pip install networkx numpy matplotlib

ایجاد گراف و ماتریس مجاورت

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

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# ایجاد گراف بدون جهت
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4])
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)])

# استخراج ماتریس مجاورت
A = nx.adjacency_matrix(G).toarray()
print("ماتریس مجاورت:\n", A)

# نمایش گراف
nx.draw(G, with_labels=True)
plt.title("گراف نمونه")
plt.show()

خروجی نمونه ماتریس مجاورت:

محاسبه ماتریس درجه و لاپلاسین

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

# ماتریس درجه
degrees = np.sum(A, axis=1)
D = np.diag(degrees)
print("ماتریس درجه:\n", D)

# ماتریس لاپلاسین
L = D - A
print("ماتریس لاپلاسین:\n", L)

ماتریس درجه:

ماتریس لاپلاسین:

سخن پایانی

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