عنوان پایان‌نامه
پیش بینی پیوندها در شبکه های اجتماعی با استفاده از گام برداری تصادفی نظارت شده
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 98..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 77645;کتابخانه پردیس یک فنی شماره ثبت: 98..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 77645
- تاریخ دفاع
- ۱۶ شهریور ۱۳۹۵
- دانشجو
- پرستو زارع
- استاد راهنما
- علی معینی
- چکیده
- در این پایان نامه ضمن بررسی روش های مدل سازی شبکه های اجتماعی با گراف ها، روشی بهبود یافته ارائه می گردد. در مدل سازی شبکه های اجتماعی باید به دو مسئله توجه داشت ، اول آن که شبکه های اجتماعی در حال گسترش هستند و همواره افراد جدیدی به این شبکه ها افزوده می شوند ، دوم آن که ایجاد اتصالات جدید در این شبکه ها تصادفی نیست و هر فرد بر اساس معیارهای متعددی به سایرین متصل می شود. در مدل پیشنهادی در این پایان نامه علاوه برتوجه به دو مسئله فوق، هنگام ایجاد اتصال میان گره های جدید و گره های پیشین به موقعیت مکانی گره ها نیز توجه شده است. مسئله دیگری که در شبکه های اجتماعی بسیار مورد توجه است، ایجاد اتصالات جدید بین افرادی است که پیشتر در شبکه حضور داشتند. به عبارت دیگر ی پیش بینی لینک درشبکه های اجتماعی نیز بسیار مورد توجه است. در این جا علاوه بر ارائه ی روش پیشنهادی برای مدل سازی شبکه های اجتماعی، به بررسی روش های متعدد ارائه شده برای پیش بینی لینک نیز می پردازیم . سپس عملکرد آن ها را در مدل پیشنهادی بررسی می کنیم. در آزمایشات صورت گرفته، دریافتیم که توزیع درجات گره ها در مدل پیشنهادی دارای توزیع نمایی است و با تقریب خوبی بر توزیع درجات فیسبوک منطبق است. همچنین در میان روش های پیش بینی لینک، گام برداری تصادفی نظارت شده بهترین عملکرد را از خود نشان داد. سپس با اعمال گام برداری تصادفی نظارت شده بر مدل پیشنهادی و مقایسه آن با سایر مدل ها، نشان دادیم که پیش بینی لینک در این مدل عملکرد بهتری نسبت به سایر مدل ها دارد.
- Abstract
- In this thesis, we proposed a model for implementing social networks, which like other models, is based on two kinds of mechanisms: incremental growth and preferential attachment.in this model we pay attention to position of graph nodes in making new connections. Creating new edges and relationships in the network in this model is based on its position and its neighbors. We showed that the degree distribution of this model is an exponential distribution and it is somehow similar to Facebook’s degree distribution. So it would be a satisfying method for implementing social networks via graphs. Studying the future of networks is also a fundamental problem in social network analysis, so we should show that our model has acceptable performance in link prediction, so we firs evaluate the link prediction methods, then we showed that the supervised random walk has the best performance among this methods, so we applied it on our model and evaluate the performance of link prediction accuracy on it. After many experiments we showed that the link prediction accuracy would be slightly better on this model in comparison with other models. Keywords: social networks, graph presentation of social networks, data mining, link prediction
