عنوان پایان‌نامه
ارائه روشی مبتنی بر تشخیص انجمن ها برای پیشینه سازی انتشار در شبکه های اجتماعی
- رشته تحصیلی
- مهندسی کامپیوتر -نرم افزار
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 2539;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 65059
- تاریخ دفاع
- ۱۳ شهریور ۱۳۹۳
- دانشجو
- خدیجه رحیم خانی
- استاد راهنما
- علی معینی, مسعود رهگذر
- چکیده
- شبکه های اجتماعی در دنیای امروز نقش اساسی در گسترش اطلاعات دارند. مشهورترین مسئله در فرآیندهای انتشار مربوط به شبکه‌های اجتماعی، بیشینه‌سازی تأثیر بر روی جامعه است. مسئله بیشینه‌سازی انتشار ازجمله مسائل NP-hard است که توجه محققان بسیاری را به خود جلب کرده است. هدف این مسئله آن است که بیشترین تعداد از افراد در سطح جامعه را به سمت یک رفتار و یا عقیده سوق دهد. با تغییر رفتار و یا عقیده این افراد به دلیل تأثیر عمده‌ای که بر جامعه دارند، رفتار و یا نظر افراد زیادی تغییر خواهد کرد. با توجه به مطالعات صورت گرفته یافتن افراد تأثیرگذار در دو مدل آبشاری مستقل و مدل آستانه خطی بسیار موردتوجه قرار گرفته‌اند. و الگوریتم هایی در راستای حل این مسئله برای این دو مدل ارائه شده‌اند. در این تحقیق ابتدا تأثیر معیارهای مرکزیت و انجمن های موجود در شبکه، در انتخاب گره های آغازین مورد بررسی قرار میگیرد. سپس راه حلی مبتنی بر مدل آستانه خطی برای این مسئله ارائه می شود. هدف این الگوریتم این است که تعداد گره های مورد بررسی را کاهش دهد به‌نحوی‌که کیفیت گره های آغازین نه تنها از دست نرود بلکه بهبود نیز یابد. ضمن اینکه بهترین جوامع شروع را نیز مشخص میکند. نتایج تجربی ما بر روی دو مجموعه داده شناخته شده نشان میدهد که الگوریتم پیشنهادی بسیار سریع تر و در عین حال کارآمد تر از الگوریتم های ارائه شده عمل می کند. واژه های کلیدی: شبکه‌های اجتماعی، مدل آستانه خطی، بیشینه‌سازی انتشار، انتشار اطلاعات، تأثیرگذارترین افراد
- Abstract
- Social networks play an important role in our new world. Finding most influential people is an NP-Hard problem that has attracted many researchers in the field of social networks. The objective of this problem is that most of the people in society are activated a behavior or belief, many people will change their behaviors or beliefs. Finding influential people in two models; independent cascade model and linear threshold model has been addressed, and some algorithms to solve the problem are presented. In the current research, a solution based on the linear threshold model is presented which uses the community structure in the network. In other words, the presented algorithm considers a number of specific communities of a social network. Then, some members of each community are selected as starting points, such that the network has the greatest diffusion with lowest cost. The main benefit of the algorithm is that it reduces the number of investigated nodes without any loss of quality to decrease its execution time. Our experimental results based on two well-known datasets show that the proposed algorithm is much faster and at the same time more efficient than the state of the art algorithms. Keywords: Social Networks, Influential People Retrieval, Influence maximization, Linear Threshold Model, Maximizing Spreading.
