توضیحات
شبیه سازی تشخیص ساختارهای اجتماعی در گراف به زبان C++
هدف این پروژه، پیاده سازی یک الگوریتم مربوط به گراف ها است. این الگوریتم در سال 022۴ ارائه شده است که ساختارهای اجتماعی را در یک گراف تشخیص می دهد. مقاله و ترجمه آن به زبان فارسی در پیوست تعریف پروژه قرار دارد. با انجام آزمایش هایی روی پیاده سازی انجام شده از این الگوریتم، باید میزان حافظه مصرفی و زمان اجرا را برای گراف های با اندازه های مختلف محاسبه نمایید. همچنین، شما باید تاثیر الگوریتم های متفاوت مرتب سازی را در زمان و حافظه مصرفی محاسبه کنید. در ادامه، الگوریتم مورد نظر و جزئیات تعریف پروژه آمده است.
اجتماع در یک گراف به زیرگرافی گفته می شود که تعداد یال های بین رأس های داخلی زیرگراف نسبت به یال های خارج شده از آن زیرگراف (به رئوس دیگر موجود در گراف) بیشتر باشد. به عنوان مثال، شکل زیر اجتماع های موجود در گراف بازی های فوتبال را نشان می دهد.
شرح الگوریتم
در این الگوریتم، با حذف یال های بین اجتماع ها، گراف به زیر گراف های متراکم تر تقسیم می شود.
ساختار داده به کار رفته در برنامه برای ذخیره سازی گراف از نوع std::vector می باشد. تمامی راس ها در vector<int> Vx و تمامی یال ها در vector<vector<int>> Ex یا vector<vector<int>> Mx ذخیره می شوند در صورت انتخاب لیست هر بردار موجود در Ex نمایان گر راس های مجاور به راس متناظر در Vx است و در صورت انتخاب ماتریس هر بردار موجود در Mx نمایان گر اتصال (مجاور بودن) تمامی راس ها در Vx خواهد بود.
برای پیداکردن دور ها به طول سه در گراف می توان از روش Hierarchical level search استفاده کرد که مشابه روش DFS است ولی زمان کمتری نیاز دارد و البته حافظه بیشتری می خواهد در این روش تمام مسیر های بسته با راس های شروع و پایان برابر که از نقطه مورد نظر عبور کرده اند شمارش می شوند این روش به علت تولید مسیر سلسله ای به دور های غیر ساده مقاوم است. با پیدا کردن مسیرها در گراف می توان الگوریتم موجود در سوال را اجرا کرد پس از اینکه آن روش C جدیدی تولید نکرد گراف به دست آمده توسط پیمایش آخرین عمق پایا LLSS (توضیحات روش مشابه در کتاب the art of programming آمده) به دو قسمت تقسیم می شود. در این مرحله اولین راس موجود در Vx انتخاب می شود و سپس تا آخرین عمق آن جلو می رویم که البته در صورتی که الگوریتم موجود در سوال دقت کافی در تقسیم گراف نداشته باشد( دقت به شدت وابسته به مسیر ها در گراف است و گراف هایی با تعداد محدود دور نتیجه خوبی تولید نمی کنند) این فرآیند ممکن است چند بار انجام شود در نهایت گروه حاوی راس اول Vx به نام A و سایر راس ها به نام B ذخیره می شوند.
شبیه سازی تشخیص ساختارهای اجتماعی در گراف به زبان C++ توسط کارشناسان گروه ۱.۲.۳ پروژه پیاده سازی گردیده و به تعداد محدودی قابل فروش می باشد.
- فایلهای پروژه به صورت کامل پس از خرید فایل بلافاصله در اختیار شما قرار خواهد گرفت.
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.