تحلیل گراف

تحلیل گراف

مقدمه

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

در این مقاله و مقاله های بعدی به معرفی گراف و تحلیل گراف و مسائل جذاب این حوزه می پردازیم.

گراف چیست ؟

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

گراف ها انواع مختلفی دارند:

گراف های مستقیم (Directed graphs):  همه یال ها از یک گره به سمت گره دیگر هدایت می شوند. به آن digraph یا directed network نیز می گویند. این نوع گراف ها روابط نامتقارن در بین گره ها را نشان می دهند.

گراف های غیرمستقیم (Undirected graphs):  تمام یال ها یک گره را به گره دیگر متصل می کنند، اما جهت رابطه مشخص نیست. این گراف همچنین یک شبکه بدون جهت نامیده می شود. گراف های بدون جهت، روابط متقارن را بیان می کنند.

شکل 1 - گراف های مستقیم و غیر مستقیم

گراف های وزنه دار (Weighted graphs): یک گراف وزنه دار، دارای یال هایی است که عددی به عنوان وزن بر روی آن ها تعریف می شود. این وزنه ها برای مشکلاتی نظیر کوتاه ترین مسیر لازم است.

گراف های چرخشی (Cyclic graphs): گراف چرخشی، مسیری از حداقل یک گره به سمت همان گره دارد. 

شکل 2 - گراف های چرخشی و غیر چرخشی

تحلیل گراف 

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

تحلیل گراف با توجه به رشد نیاز بازار، بسیار اهمیت پیدا کرده است. بر اساس گزارش ها بازار تحلیل گراف، در سال 2019 600 میلیون دلار بود و انتظار می رود تا سال 2024 به 2.5 میلیارد دلار برسد.

انواع مختلف تحلیل گراف چیست؟

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

تحلیل هایی که وجود دارد: 

تجزیه و تحلیل مرکزیت (Centrality): این تحلیل میزان مهم بودن یک گره را در اتصالات یک شبکه گرافی مشخص می کند و کمک می کند تا با استفاده از الگوریتم PageRank تأثیر گذارترین افراد در یک شبکه اجتماعی یا صفحات وب را تخمین بزنید.

شکل 3 - نمایی از گراف به منظور تحلیل مرکزیت

تشخیص انجمنی (Community): از فاصله و تراکم روابط بین گره ها می توان گروه هایی از گره ها را یافت که به صورت مرتب در یک شبکه با یکدیگر تعامل دارند. تجزیه و تحلیل انجمنی همچنین با الگوهای تشخیص رفتار جوامع سر و کار دارد.

شکل 4 -  نمایی از گراف به منظور تحلیل انجمنی

تحلیل اتصال (Connectivity): این تحلیل تعیین می کند که دو گره به چه شدت یا ضعفی به هم متصل شده اند. به صورت خلاصه هرچه تعداد یال های مستقیم و غیر مستقیم دو گره بیشتر باشد اتصال این دو گره بیشتر است.

تحلیل مسیر (Path): روابط بین گره ها را بررسی می کند. بیشتر در مسئله های کمترین مسافت استفاده می شود.

پیش بینی پیوند (Link Prediction): با محاسبه مجاورت و فرم ساختاری گره ها، روابط جدید یا اتصالات موجود که بر روی گراف مشخص نشده اند را تخمین می زند.

شکل 5 - پیش بینی پیوند

موارد استفاده از تحلیل گراف چیست؟

 کشف تقلب

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

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

بهینه سازی زنجیره تامین

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

تحلیل شبکه اجتماعی

شبکه های اجتماعی مانند اینستاگرام، Spotify و LinkedIn، برنامه هایی بر محور ارتباط هستند. تجزیه و تحلیل گراف به شناسایی تاثیرگذاران (influencers) و جوامع در شبکه های رسانه های اجتماعی کمک می کند. بازاریابی تاثیرگذاران شبکه های اجتماعی به دلیل افزایش تعداد کاربران آن ها از اهمیت بالایی برخوردار شده است.

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

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

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

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

جهان با بیماری همه گیری COVID-19 روبرو است. از آن جا که شیوع این ویروس بسیار سریع است، استفاده از یک پایگاه داده گرافی به دولت ها کمک می کند تا شیوع ویروس را ردیابی کنند. با استفاده از پایگاه داده گرافی مانند Neo4j برنامه هایی ساخته شده که به شهروندان اجازه می دهد، بررسی کنند که آیا با یک عامل شناخته شده ویروس تماس گرفته اند یا خیر.

ابزارهای برجسته پایگاه داده گراف چیست؟

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

  • Amazon Neptune
  • ArangoDB
  • Cayley
  • DataStax
  • FlockDB
  • Neo4j
  • OrientDB
  • Titan

برای اینکه بیشتر با این دیتابیس های گرافی آشنا شوید و تفاوت آن ها را دریابید، بهتر است به مقاله  آشنایی با Graph database و انواع آن سری بزنید. 

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

نظرات
اگر login نکردی برامون ایمیلت رو بنویس: