بستن× ارتباط ۸۴۹۷۷۶۷۲
بستن×

فرم جستجو

کشف سلسله مراتب جوامع در شبکه‌های اجتماعی بزرگ

زمان برگزاری: 04/24/1397 - 14:00 الی 16:00
نوع: کارگاه آموزشی
زبان: فارسی
سازمان ارائه دهنده:
ارائه دهنده: دکتر مجتبی رضوانی
تلفن تماس:
مکان: سالن آموزش
نشانی تارنما:

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

مستنداتی یافت نشد.