بصری سازی گراف روشی برای بازنمایی اطلاعات گراف (Visualization)

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

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

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

بصری سازی گراف، ممکن است با تمرکز بر روی نود خاصی به عنوان کانون توجه صورت پذیرد. در این صورت آن را نمایش چشم ماهی (Fish eye visualization) گفته میشود. در نمایش هایی که کل شبکه در کنار هم رسم میشود سعی میشود نودهای مرتبط با هم کنار هم رسم شده و نودهای غیرمرتبط دور از هم در صفحه قرار گیرند تا کاربر مشاهده کننده دید مناسبی از کلیات شبکه داشته باشد. ابزارهای متنوعی از جمله نرم افزار پرکاربرد گفی (Gephi) به منظور بصری سازی و نمایش گراف تولید شده است.

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

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

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

• Reingold Fruchterman-Reingold(FR)
• Force Atlas (FA)
• Yifan-Hu (YH)
• OpenOrd (OO)
•  

نرم افزارهای بازنمایی گراف

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

نرم افزارهای بازنمایی باید گراف را به گونه‌ای رسم کنند که قواعد زیر در آنها رعایت شده باشد:

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

در ادامه چند نمومنه زیبا از بصری سازی گراف آمده است.

 

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

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

جهت دیدن سرفصل های دوره های آموزشی بر روی اینجا کلیک کنید.l

بازدیدها: 2463