سیف اله سلیمانی

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