مدل داده و ساختارهای منطقی ذخیره سازی گراف

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

❗️توجه: هر چند این مبحث ساده به نظر میرسد ولی مرجعی برای خیلی از مباحث تحلیلی، در حوزه بیگ دیتا و شبکه های اجتماعی که در آینده مطرح خواهم کرد خواهد بود.

❗️توجه: ضمنا علاقه مندان به پایگاه داده های NOSQL هم این مبحث را دنبال کنند چرا که این مطلب یکی از مباحث پایه ای در حوزه پایگاه داده های غیر رابطه ای مبتنی بر گراف می باشد.

?در حوزه ذخیره و بازیابی گراف عمدتا با سرفصل های زیر مواجه هستیم:

? ساختار های منطقی ذخیره سازی گراف (که در همین پست به آن می پردازیم)
? روش ها و تکنیکهای ذخیره سازی گراف (مثل XML یا JSON)
? قالب فایل های ذخیره سازی گراف
? پایگاه داده های مبتنی بر گراف

برای شروع مورد اول یعنی ساختار های منطقی ذخیره گراف را در ادامه ارائه خواهم داد.

انواع ساختار های منطقی ذخیره سازی گراف

❗️یکی از مواردی که لازم است هر تحلیلگر در حوزه تحلیل شبکه های اجتماعی بداند، ساختار منطقی ذخیره گراف است. تا کنون ساختار مختلفی برای نگهداری گراف ارائه شده است که مهم ترین آنها عبارت است از:
? ماتریس مجاورتی
? ماتریس برخورد
? لیست و آرایه مجاورتی یا وکتور مجاورتی

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

?نکته1: منطق ذخیره سازی گراف با روش (تکنیک) ذخیره سازی متفاوت است. به عنوان مثال تمام منطق های ذکر شده فوق با استفاده از روش XML قابل پیاده سازی میباشد. (در مباحث آینده به روش های ذخیره سازی گراف خواهم پرداخت)

?نکته2: توجه داشته باشید منطق های نگهداری گراف ربطی به محل ذخیره سازی گراف ندارد به عنوان مثلا تمامی منطق های فوق الذکر چه در RAM و چه در Disk قابل پیاده سازی هستند.

ماتریس مجاورتی

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

نکته: دو گراف همریخت دارای ماتریس مجاورت یکسانی هستند.

برای بهتر متوجه شدن این ماتریس، سطر و ستون های ماتریس مجاورت هر دو شامل نام راس ها هستند.به صورت زیر:

ماتریس برخورد

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

لیست و آرایه مجاورتی یا وکتور مجاورتی

در این منطق ذخیره سازی گره های مرتبط با هر گره در یک ساختمان داده ی لیست پیوندی یا آرایه تک بعدی نگهداری می شود.

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

تک جدولی

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

دو جدولی

در روش دو جدولی که تکامل یافته روش تک جدولی است دو جدول وجود دارد. یک جدول به نام Vertex Table که شامل اطلاعات مربوط به گره هاست و یک جدول که مانند روش قبل صرفا اطلاعات یال ها در آن ذخیره میشود. تکنولوژی هایی مثل GraphX در اسپارک و تایتان (Titan) از این روش بهره می گیرند.

آدرس کانال تلگرام ما:

t.me/bigdata_channel
برای ورود به کانال بر روی اینجا کلیک کنید.

بازدیدها: 2010