بصری سازی گراف شبکه های اجتماعی به روش الگوریتم OO یا (OpenOrd)

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

روش OpenOrd به علت سرعت پردازش و همچنین توانایی پردازش گراف‌های بزرگ، به‌منظور بصری سازی و نمایش گراف شناخته شده است. الگوریتم‌هایی مثل force-directed layout می‌تواند تا به‌منظور پردازش 1میلیون گره توسعه داده شود اما الگوریتم OpenOrd ایده‌ای برای گراف‌های بزرگ‌تر است. این الگوریتم وزن گراف‌های غیر جهت‌دار را پیش‌بینی می‌کند و برای مشخص کردن کلاستر بهتر استفاده می‌شود. این الگوریتم  می‌تواند به‌صورت موازی در چند ماشین مجزا با سرعت بالا اجرا شود و به‌صورت خودکار متوقف می‌شود. شاید این الگوریتم یکی از بهترین انتخاب ها برای پایگاه داده های مبتنی بر گراف (مثل Titan و OrientDB و Neo4j) باشد. مبنای این الگوریتم روش force-directed است. این روش قابلیت توزیع‌شدگی را دارد به همین دلیل، قادر به پردازش گراف‌های بزرگ است. این الگوریتم از سه ویژگی به‌صورت همزمان استفاده می‌کند که باعث شده سرعت اجرای آن نسبتاً به دیگر روش‌ها بالا باشد:

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

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

t.me/bigdata_channel

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

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

بازدیدها: 1515