کتاب Massive Graph Analytics

کتاب Massive Graph Analytics یا آنالیز گراف‌های عظیم، از جدیدترین کتاب‌های مربوط به علوم داده می‌باشد که به تازگی در سال 2022 به چاپ رسیده است. این کتاب در 5 بخش به آموزش گام‌به‌گام گراف و کار با آن می‌پردازد و در نهایت در عمل و دنیای واقعی مثال‌هایی از آن را به شما نشان می‌دهد.

در ادامه مقدمه‌ای از کتاب Massive Graph Analytics را از زبان نویسنده شرح خواهیم داد.

مقدمه‌ای بر کتاب Massive Graph Analytics:

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

کتاب Massive Graph Analytics شامل مجموعه‌ای جامع از فصول از نویسندگان برجسته در زمینه تجزیه و تحلیل گراف در مقیاس عظیم است.

فصل‌ها در پنج بخش سازمان‌دهی شده‌اند: بخش اول: الگوریتم‌ها: جستجو و مسیرها (فصل 1-2)، بخش دوم: الگوریتم‌ها: ساختار (فصل 3-6)، بخش سوم: الگوریتم‌ها و کاربردها (فصل 7-11)،

بخش IV: مدل‌ها (فصل 12-14)، و بخش پنجم: چارچوب‌ها و نرم‌افزار (فصل 15-20).

بخش اول: الگوریتم‌ها: جستجو و مسیرها

جستجوی نمودار یکی از اساسی‌ترین و مهم ترین الگوریتم‌های گراف است. با افزایش اندازه نمودارها، از موازی‌سازی برای بهبود سرعت الگوریتم استفاده می‌شود.
چارلز ای. لیزرسون و تائو ب. شاردل در فصل 1 کتاب Massive Graph Analytics، الگوریتم جستجوی پهنای موازی کارآمد کارآمد (یا نحوه مقابله با عدم قطعیت کاهنده‌ها)، اجرای چند رشته ای جدید از جستجوی وسعت اول (BFS) را ارائه می‌کنند. نمودار پراکنده با استفاده از پسوندهای Cilk++ به C++.

قابل توجه است که برنامه موازی آن‌ها بر روی یک هسته پردازشی واحد به سرعت اجرای استاندارد C++ BFS اجرا می‌شود. BFS موازی با استفاده از یک پیاده‌سازی جدید از یک ساختار داده چند مجموعه‌ای، به نام “کیسه”، به جای صف FIFO که معمولاً در الگوریتم‌های BFS سریال استفاده می‌شود، به کارایی بالایی دست می‌یابد.

این فصل از کتاب Massive Graph Analytics به زمان‌بندی زیربنایی سرقت کار که محاسبات را متعادل می‌کند، روشن می‌کند و یک روش کلی برای تجزیه و تحلیل برنامه‌های غیر قطعی که از کاهنده‌ها استفاده می‌کنند، ارائه می‌کند.

تجزیه و تحلیل الگوریتمی نشان می‌دهد که یک نسخه بدون مسابقه داده از BFS موازی به طور مؤثر اجرا می‌شود و در بسیاری از موارد عملی زمانی که تعداد پردازنده‌ها کمتر از حد مربوط به اندازه و قطر نمودار است، به سرعت‌های خطی تقریباً عالی می‌رسد.
یکی دیگر از گراف‌های اولیه، یافتن کوتاه ترین مسیر بین دو رأس در یک گراف است.

فصل 2 کتاب Massive Graph Analytics، کوتاهترین مسیرهای چندهدفه، نوشته استفان ارب، موریتز کوبیتز، لارنس ماندو، و پیتر سندرز، بر روی برخی از پیشرفت‌ها در موازی‌سازی جستجوی کوتاه‌ترین مسیر چندهدفه تمرکز دارد. رویکرد آن‌ها از یک الگوریتم تنظیم برچسب استفاده می‌کند که تمام مسیرهای بهینه پارتو را که از یک منبع منفرد در یک گراف سرچشمه می‌گیرند، پیدا می‌کند.

الگوریتم بر اساس تعمیم چندهدفه صف اولویت است. این فصل از کتاب Massive Graph Analytics شامل یک تحلیل نظری است که نشان می‌دهد پیچیدگی اضافه شده در جستجوی کوتاه‌ترین مسیر با تنظیم برچسب تک هدفه را می‌توان کاملاً موازی کرد و نتایج عملی نشان می‌دهد که درختان B متعادل می‌توانند تا حد زیادی از درختان قرمز-سیاه به عنوان صف‌های موازی پارتو بهتر عمل کنند.

در مسائل نمونه، آزمایش‌ها هنگام مقایسه جستجوی دوهدفه موازی با یک رقیب متوالی بسیار تنظیم‌شده، افزایش سرعت 8 بر 16 هسته را نشان می‌دهند.

بخش دوم: الگوریتم‌ها: ساختار

الگوریتم‌های اتصال گراف ساختار درون توپولوژی گراف را بررسی می‌کنند.

فصل 3 کتاب Massive Graph Analytics، الگوریتم‌های چند هسته‌ای برای مسائل اتصال گراف، نوشته جورج ام اسلوتا، سیواسانکاران راجامانیکام، و کامش مدوری، مشکلات یافتن حداکثر مؤلفه‌های متصل قوی، مؤلفه‌های متصل و ضعیف ضعیف، و مؤلفه‌های متصل به دو را در نمودارهای جهت‌دار بزرگ شرح می‌دهد. کلید رویکرد آن‌ها یک روش جدید “Multistep” است که برای نمودارهای بزرگ دنیای واقعی، مانند شبکه‌های اجتماعی آنلاین و خزیدن وب، با استفاده از پلتفرم‌های چند هسته‌ای با حافظه مشترک فعلی طراحی شده است.

روش Multistep شامل سایر هسته‌های گراف مهم مانند BFS و رنگ آمیزی می‌باشد. در یک سرور 16 هسته ای، این رویکرد جدید قادر است این مؤلفه‌ها را در نمودارهای بزرگ دنیای واقعی سریعتر از اکثر رویکردهای رقیب پیدا کند. بسیاری از نمودارهای دنیای واقعی آنقدر بزرگ هستند که ممکن است در حافظه اصلی یک رایانه جا نشوند.

برای این نمودارهای عظیم، استفاده از سیستم‌های موازی حافظه توزیع شده اغلب تنها راه برای یافتن راه حلی برای مسائل تحلیلی گراف است.

فصل 4 کتاب Massive Graph Analytics، الگوریتم‌های موازی حافظه توزیع‌شده برای نمودارهای عظیم، اثر مقسودالعلم، شیخ اریفوززمان، حسن‌زمان بهویان، ملک خان، وی. Anil Kumar و Madhav Marathe، یک بحث عمیق در مورد الگوریتم‌های موازی حافظه توزیع شده برای چندین کلاس از مشکلات گراف عظیم ارائه می‌کنند: تولید نمودار تصادفی، مشکلات BFS و کوتاه‌ترین مسیر، و یافتن ساختار اجتماعی زیربنایی شبکه مانند مثلث‌ها و از نزدیک.

جوامع بافتنی این فصل از کتاب Massive Graph Analytics خواننده را از طریق سه مدل محاسباتی حافظه توزیع‌شده مختلف برای طراحی الگوریتم‌ها راهنمایی می‌کند: رابط ارسال پیام (MPI)، Hadoop مبتنی بر MapReduce و Giraph.
یکی از اهداف کلیدی در سرعت بخشیدن به تجزیه و تحلیل گراف، توسعه الگوریتم‌های نمودار قابل حمل و مقیاس پذیر برای نمودارهای پراکنده بزرگ است که به هیچ روال خاص سخت افزاری متکی نیستند.

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

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

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

فصل 6 کتاب Massive Graph Analytics، محاسبات مثلث توزیع شده در مقیاس عظیم، توسط جفری سندرز، راجر پیرس، بنجامین دبلیو پریست، و ترور استیل، محاسبات مثلثی را که در تجزیه و تحلیل‌های مرتبه بالاتر و در چندین تجزیه و تحلیل داده‌ها و وظایف یادگیری ماشین از جمله ویژگی‌ها استفاده می‌شود، توصیف می‌کند.

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

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

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

بخش سوم: الگوریتم‌ها و کاربردها

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

در فصل 7، محاسبه مرکزیت نزدیکی Top-k در نمودارهای کاملاً پویا، نوشته یوجنیو انگریمن، پاتریک بیسنیوس، الیزابتتا برگامینی، هنینگ میرهنکه، نویسندگان درباره یافتن k ترین رأس‌ها در نمودارهایی که در طول زمان تکامل می‌یابند بحث می‌کنند. رویکرد آن‌ها، اولین در نوع خود، به طور قابل توجهی در محاسبه مجدد استاتیک پس از درج چندین لبه یا حذف لبه بهبود می‌یابد.

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

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

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

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

فصل 9 کتاب Massive Graph Analytics، پارتیشن بندی نمودارهای تریلیون لبه، نوشته جورج ام اسلوتا، کارن دیوین، سیواسانکاران راجامانیکام، و کامش مدوری، بر پارتیشن بندی نمودار تمرکز دارد که اغلب به عنوان یک مرحله کلیدی پیش پردازش برای تجزیه و تحلیل گراف و محاسبات علمی روی مش‌ها استفاده می‌شود.

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

در مجموعه‌ای از نمودارهای پراکنده در مقیاس کوچکتر، کیفیت پارتیشن بندی XtraPuLP با سایر روش‌های پارتیشن‌بندی پیشرفته قابل مقایسه است. اینترنت در حال دگرگونی جامعه ما است و نیاز به درک کمی از ترافیک اینترنت دارد.

فصل 10 کتاب Massive Graph Analytics، پدیده‌های جدید در ترافیک اینترنتی در مقیاس بزرگ، اثر جرمی کپنر، کنجیرو چو، کی سی کلافی، ویجی گدپالی، سارا مک گوایر، لورن مایلچین، ویلیام آرکاند، دیوید بستور، ویلیام برگرون، چانسوپ بیون، متیو هابل، مایکل هوول جونز، اندرو پروت، آلبرت رویتر، آنتونیو روزا، سیدهارت سامسی، چارلز یی، و پیتر میکالیاس، جزئیات مجموعه نویسندگان و سرپرستی بزرگترین مجموعه داده‌های ترافیک اینترنتی در دسترس عموم را شرح می‌دهند.

سپس این داده‌ها از طریق تجزیه و تحلیل گراف در مقیاس عظیم برای آشکار کردن پدیده‌های جدید و بهبود درک ما از اینترنت تجزیه و تحلیل می‌شوند. به عنوان مثال، تجزیه و تحلیل 50 میلیارد بسته با استفاده از 10000 پردازنده در MIT SuperCloud یک پدیده جدید را نشان می‌دهد: اهمیت گره‌های برگ غیرقابل مشاهده و پیوندهای جدا شده در ترافیک اینترنت.

تجزیه و تحلیل بیشتر نشان می‌دهد که یک توزیع Zipf-Mandelbrot اصلاح شده با دو پارامتر به دقت طیف گسترده ای از آمار منبع/مقصد را در پنجره‌های نمونه متحرک از 100000 تا 100000000 بسته در مجموعه‌هایی که سال‌ها و قاره‌ها را در بر می‌گیرند، توصیف می‌کند.

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

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

نمودارهای دوبخشی فاقد مثلث هستند. کوچکترین زیرگراف غیر پیش پا افتاده یک پروانه است (همچنین به عنوان مستطیل شناخته می‌شود) که یک دوقلوی (2،2) است (شامل دو رأس در هر طرف و هر چهار یال ممکن در بین آن‌ها).

جسیکا شی و جولیان شون در فصل 11 کتاب Massive Graph Analytics، الگوریتم‌های موازی برای محاسبات پروانه‌ای، الگوریتم‌های موازی جدیدی را برای مسئله مهم شمارش پروانه‌ها در نمودارهای دوبخشی ارائه می‌کنند. علاوه بر این، شمارش پروانه‌ها به طور طبیعی به یافتن ساختارهای زیرگراف متراکم در شبکه‌های دوبخشی کمک می‌کند.

بخش چهارم: مدل‌ها

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

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

فصل 12 کتاب Massive Graph Analytics، پیشرفت‌های اخیر در تولید شبکه مقیاس‌پذیر، توسط مانوئل پنشاک، اولریک براندز، مایکل هامان، سباستین لام، اولریش مایر، ایلیا سافرو، پیتر سندرز و کریستین شولز، یک نظرسنجی را ارائه می‌کند که در آن آن‌ها جنبه‌های مهم مدل‌های نمودار تصادفی را بررسی می‌کنند.

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

این فصل از کتاب Massive Graph Analytics بر تکنیک‌های مدل‌سازی و الگوریتم‌های ابتدایی که در بدست آوردن نمودارهای عظیم موفق بوده‌اند، تمرکز دارد. نویسندگان مفاهیم و مدل‌های نموداری را برای حوزه‌های متعدد (مانند شبکه‌های اجتماعی، زیرساخت‌ها، بوم‌شناسی و شبیه‌سازی‌های عددی) در نظر می‌گیرند و مولدهایی را برای مدل‌های مختلف محاسبات (شامل موازی‌سازی حافظه مشترک، پردازنده‌های گرافیکی، و سیستم‌های توزیع موازی انبوه) مورد بحث قرار می‌دهند.

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

فصل 13 کتاب Massive Graph Analytics، مدل‌های محاسباتی برای آبشارها در نمودارهای عظیم: نحوه انتشار یک شایعه به صورت موازی، توسط آجیتش سریواستاوا، چارالامپوس چلمیس، و ویکتور کی پرأسانا، بر شایعه پراکنی تمرکز دارد که در زمینه‌های دیگر مانند تکرار و نگهداری از آن نیز استفاده می‌شود. پایگاه‌های داده و پخش شبکه در مقیاس بسیار زیاد، تنوع و پویایی شبکه‌های اجتماعی آنلاین منجر به توسعه مدل‌های شبیه‌سازی شایعه پراکنی شده است. این مدل‌ها سناریوهای «چه می‌شد»، مانند شیوع ویروسی را برای حمایت از تصمیم‌گیری در زمان واقعی (تقریباً) تجزیه و تحلیل می‌کنند.

این فصل از کتاب Massive Graph Analytics راه‌حل‌های احتمالی را برای سرعت بخشیدن به محاسبه شایعات در مقیاس بزرگ در شبکه‌های اجتماعی دنیای واقعی با میلیون‌ها رأس ارائه می‌کند و گام‌های لازم برای موازی‌سازی الگوریتم جدید آن‌ها برای فعال کردن کاربرد بلادرنگ آن برای انتشار «ویروسی» را مورد بحث قرار می‌دهد.

ردیابی از طریق شبکه‌های پویا محاسبه گراف داده – که توسط سیستم‌های برنامه‌نویسی مانند Galois، Pregel، GraphLab، PowerGraph و GraphChi رایج شده است – الگوریتمی است که به‌روزرسانی‌های محلی را در رأس یک نمودار انجام می‌دهد.

فصل 14 کتاب Massive Graph Analytics، اجرای محاسبات دینامیک داده-گراف به صورت قطعی با استفاده از زمان‌بندی رنگی، توسط تیم کالر، ویلیام هاسنپلاف، تائو بی. شاردل، و چارلز ای. لیزرسون، یک الگوریتم زمانبندی رنگی برای اجرای داده‌های دینامیک گراف را معرفی می‌کند. Prism از رنگ‌آمیزی رأس نمودار برای هماهنگ کردن به‌روزرسانی‌های انجام‌شده در یک دور استفاده می‌کند، و از نیاز به قفل‌های حذف متقابل یا سایر همگام‌سازی‌های داده غیرقطعی جلوگیری می‌کند.

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

بخش پنجم: چارچوب‌ها و نرم‌افزارها

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

فصل 15 کتاب Massive Graph Analytics، علوم داده‌های نموداری با استفاده از Neo4j، توسط امی ای. هادلر و مارک نیدهام، بر کاربرد علم داده‌های نموداری در تجارت با استفاده از فناوری نمودار Neo4j برای نشان دادن مثال‌هایی به دلیل محبوبیت تجاری آن تمرکز دارد. مروری بر علم داده‌های گراف و نگاهی کوتاه به فناوری Neo4j وجود دارد: پایگاه داده Neo4j و مدل نمودار ویژگی. Neo4j Cypher Query Language; Neo4j Graph Science Data Library; مرورگر Neo4j; و ابزار تجسم Neo4j Bloom.

سپس این فصل از کتاب Massive Graph Analytics مراحل پذیرش علم داده‌های گراف را بررسی می‌کند، که با نمودارهای دانش و تجزیه و تحلیل گراف شروع می‌شود، به مهندسی ویژگی‌های گراف و تعبیه گراف می‌رود، و با شبکه‌های گراف برای یادگیری بومی گراف خاتمه می‌یابد.
در نهایت، چند مورد استفاده در دنیای واقعی و نمایشی از تشخیص تقلب در Neo4j وجود دارد.

فصل 16 کتاب Massive Graph Analytics، کتابخانه تقویت موازی نمودار 2.0، توسط نیکلاس ادموندز و اندرو لومزدین، کتابخانه تقویت موازی نمودار 2.0 را ارائه می‌کند که مجموعه ای از انتزاعات برنامه نویسی موازی و یک روش طراحی نرم‌افزار را در بر می‌گیرد که امکان اجرای انعطاف پذیر، مقیاس پذیر و بسیار همزمان را فراهم می‌کند.

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

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

فصل 17، RAPIDS cuGraph، توسط الکس فندر، بردلی ریس، و جو ایتون، کتابخانه گرافیکی شتاب‌دار واحد پردازش گرافیکی منبع باز NVIDIA (GPU) را شرح می‌دهد. cuGraph از مفهوم DataFrame در RAPIDS و Pandas API برای مدیریت بارگذاری داده‌ها، عملیات ETL و آماده سازی داده‌ها قبل و بعد از اجرای بارهای کاری نمودار استفاده می‌کند.

cuGraph خود مجموعه‌ای از الگوریتم‌های گراف تسریع‌شده توسط GPU را ارائه می‌کند که در یک API پایتون شبیه به NetworkX، اما با عملکردی تا نمودارهای در مقیاس عظیم پیچیده می‌شوند.

این فصل از کتاب Massive Graph Analytics طراحی و پیاده‌سازی cuGraph را مورد بحث قرار می‌دهد، که به‌عنوان بخشی از RAPIDS، یک اکوسیستم علم داده کامل از سرتاسر، شتاب GPU را در تجزیه و تحلیل گراف فراهم می‌کند. cuGraph ده‌ها الگوریتم گراف محبوب را با یک API بصری پایتون، شبیه به NetworkX API محبوب، پیاده‌سازی می‌کند، در حالی که از فرمت‌ها و فن‌آوری‌های متعدد به صورت شفاف پشتیبانی می‌کند و مرتبه‌ای از افزایش عملکرد را ارائه می‌دهد.

الگوریتم‌هایی که در cuGraph در یک مقیاس GPU تا میلیون‌ها رأس پیاده‌سازی می‌شوند. cuGraph همچنین در چندین GPU مقیاس می‌شود و این مزیت عملکرد را در مقیاس میلیاردها لبه حفظ می‌کند.

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

اما نرخ داده‌های کنونی چالش‌های اقتصادی و زیست‌محیطی را تحمیل می‌کند تا به طور مداوم کل حافظه سیستم را برای «تناسب» با نمودار گسترش دهد.

فصل 18 کتاب Massive Graph Analytics، رویکرد مبتنی بر ابر به نمودارهای بزرگ، توسط پل بورکهارت و کریستوفر آ. وارینگ، یک رویکرد مبتنی بر ابر را ارائه می‌کند که با داده‌های بزرگ مقیاس می‌شود و در عین حال تحمل خطا دارد. با استفاده از این رویکرد، نویسندگان اولین کسانی هستند که بزرگترین اندازه مشکل را در معیار Graph500 تکمیل می‌کنند و یک نمودار پتابایتی متشکل از بیش از 4 تریلیون رأس و 70 تریلیون یال را طی می‌کنند، اندازه‌ای تقریباً بیست برابر ظرفیت حافظه فیزیکی پلت‌فرم محاسباتی آن‌ها.

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

فصل 19 کتاب Massive Graph Analytics، مقدمه‌ای بر GraphBLAS، اثر جرمی کپنر، پیتر آلتونن، دیوید بادر، آیدین بولوک، فرانتس فرانچتی، جان گیلبرت، شانا هاچیسون، مانوج کومار، اندرو لومزدین، هنینگ مایرهنکه، اسکات مک‌میلیان، خوزه موریرا، جان دی. Yang، Marcin Zalewski و Timothy G. Mattson، استاندارد جدیدی برای طراحی الگوریتم‌های گراف به زبان جبر ماتریسی ارائه می‌کنند.

این فصل از کتاب Massive Graph Analytics مفاهیم کلیدی ریاضی GraphBLAS را تشریح می‌کند و نتایج اولیه ای را ارائه می‌دهد که نشان می‌دهد سربار GraphBLAS حداقل است (در مقایسه با کتابخانه‌های ماتریسی زیربنایی آن‌ها). تجزیه و تحلیل داده‌های بزرگ دنیای واقعی اغلب با ساختارها و منابع داده‌های ناهمگن ترکیب می‌شود.

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

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

فصل 20، Graphulo: هسته‌های گراف خطی، نوشته لورن مایلکین، شانا هاچیسون، هیدن جانانتان، جرمی کپنر، بنجامین میلر، اندرو پروت، سیدهارت سامسی، چارلز یی و ویجی گادپالی، ابتکار عمل گرافولو در MIT را ارائه می‌کند.

مستقیماً در پایگاه‌های داده NoSQL مانند Apache Accumulo یا SciDB که دارای یک طرح ذخیره‌سازی داده ذاتاً پراکنده هستند. این فصل از کتاب Massive Graph Analytics مروری کوتاه بر کلاس‌های مختلف الگوریتم‌های گراف ارائه می‌کند و برخی از آن‌ها را به عملیات جبر خطی سازگار با بلوک‌های ساختمان GraphBLAS بازنویسی می‌کند.

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

در فصل 21 از کتاب Massive Graph Analytics، تجزیه و تحلیل گراف تعاملی در مقیاس در آرکودا، توسط Zhihui Du، Oliver Alvarado Rodriguez، Joseph Patchett و David A. Bader، نویسندگان الگوریتم‌های نموداری را در Arkouda ارائه می‌کنند، چارچوبی که در مراحل اولیه توسعه یافته است که بهره‌وری پایتون را در کنار هم قرار می‌دهد.

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

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

این پروژه کتاب چندین سال و چالش‌های همه‌گیری COVID-19 را در بر گرفت. از رندی کوهن، ناشر علوم کامپیوتر و فناوری اطلاعات چاپمن و هال/CRC، گروه تیلور و فرانسیس، برای حمایتش در تشویق، توسعه و انتشار این کتاب، و دستیار تحریریه تالیتا دانکن-تاد برای کمک او در سازماندهی تشکر می‌کنیم. کتاب. امیدوارم شما هم به همان اندازه که من از ویرایش این مجموعه لذت بردم از خواندن این کتاب لذت ببرید. سپاسگزارم.

دیوید A. Bader

نیویورک سیتی

26 ژوئن 2021

سرفصل‌های کتاب Massive Graph Analytics:

• Cover
• Half Title
• Series Page
• Title Page
• Copyright Page
• Table of Contents
• Editor
• Contributors
• Introduction
• SECTION I: Algorithms: Search and Paths
  • Chapter 1 A Work-Efficient Parallel Breadth-First Search Algorithm (or How To Cope With the Nondeterminism of Reducers)
  • Chapter 2 Multi-Objective Shortest Paths
• SECTION II: Algorithms: Structure
  • Chapter 3 Multicore Algorithms for Graph Connectivity Problems
  • Chapter 4 Distributed Memory Parallel Algorithms for Massive Graphs
  • Chapter 5 Efficient Multi-core Algorithms for Computing Spanning Forests and Connected Components
  • Chapter 6 Massive-Scale Distributed Triangle Computation and Applications
• SECTION III: Algorithms and Applications
  • Chapter 7 Computing Top-k Closeness Centrality in Fully Dynamic Graphs
  • Chapter 8 Ordering Heuristics for Parallel Graph Coloring
  • Chapter 9 Partitioning Trillion-Edge Graphs
  • Chapter 10 New Phenomena in Large-Scale Internet Traffic
  • Chapter 11 Parallel Algorithms for Butterfly Computations
• SECTION IV: Models
  • Chapter 12 Recent Advances in Scalable Network Generation
  • Chapter 13 Computational Models for Cascades in Massive Graphs: How to Spread a Rumor in Parallel
  • Chapter 14 Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling
• SECTION V: Frameworks and Software
  • Chapter 15 Graph Data Science Using Neo4j
  • Chapter 16 The Parallel Boost Graph Library 2.0: Active Messages as a Spanning Model for Parallel Graph Computation
  • Chapter 17 RAPIDS cuGraph
  • Chapter 18 A Cloud-Based Approach to Big Graphs
  • Chapter 19 Introduction to GraphBLAS
  • Chapter 20 Graphulo: Linear Algebra Graph Kernels
  • Chapter 21 Interactive Graph Analytics at Scale in Arkouda
• Index

فایل کتاب Massive Graph Analytics را می‌توانید پس از پرداخت، دریافت کنید.