پديد آورنده :
محمدي، آزاده
عنوان :
بيشينه‌سازي تأثير حساس به زمان در شبكه‌هاي اجتماعي
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده برق و كامپيوتر
صفحه شمار :
چهارده، [153]ص.: مصور، جدول،نمودار(رنگي)
يادداشت :
ص. ع. به فارسي و انگليسي
استاد راهنما :
محمد حسين سرايي
استاد مشاور :
عبدالرضا ميرزايي
توصيفگر ها :
انتشار اطلاعات , بهينه سازي توابع , تابع تازگي , گسترش تاثير
استاد داور :
مازيار پالهنگ، محمد حسين منشئي، علي فانيان
تاريخ ورود اطلاعات :
1395/12/01
رشته تحصيلي :
برق و كامپيوتر
دانشكده :
مهندسي برق و كامپيوتر
كد ايرانداك :
ID999 دكتري
چكيده فارسي :
چكيده يك شبكه اجتماعي نمايانگر مجموعها از افراد و ارتباطات بين آنها است مطالعات جامعهشناسي نشان دادهاند كه افراد مرتبط در يك شبكه اجتماعي از يكديگر تأثير ميپذيرند به اين معني كه هر فرد در شبكه ممكن است با پيرو از آشنايان خود رفتار نظر يا ايده مطرحشده توسط ميشود ناميده اجتماعي تأثير پديده اين نمايد اتخاذ را آنها بنابراين چنانچه مجموعها از افراد در يك شبكه رفتار يا ايده خاصي داشته باشند به علت وجود ارتباطات بين فرد و تأثير اجتماعي آن ايده يا رفتار ميتواند در شبكه منتشر شود اين پديده گسترش تأثير ناميده ميشود مطالعه گسترش تأثير در بسيار از كاربردها ازجمله تبليغات بازاريابي و سيستمها توصيه ميتواند كمككننده باشد هدف از اين مطالعات بررسي نحوه گسترش تأثير در شبكهها اطلاعاتي و بهينهساز مسئله حوزه اين در مطرحشده مسائل مهمترين از يكي ميباشد آن بيشينهساز تأثير ميباشد هدف از بيشينهساز تأثير انتخاب k فرد است كه فعال كردن اوليه آنها درنهايت بتواند رفتار يا ايده موردنظر را در بين تعداد بيشتر از افراد جامعه گسترش دهد در شبكهها اجتماعي واقعي انتشار اطلاعات از گرها به گره ديگر همراه با تأخير زماني است بهعلاوه ارزش اطلاعات منتشره در طول زمان ممكن است كاهش يابد بنابراين نهتنها ميزان گسترش بلكه سرعت گسترش نيز از اهميت ويژها برخوردار است در تحقيقات انجامشده اين جنبه از انتشار اطلاعات يعني وابستگي ارزش اطلاعات به زمان و سرعت گسترش ناديده گرفته شده است در اين رساله با لحاظ كردن جنبه زماني در فرايند انتشار و تعريف مفهومي به نام ميزان تازگي مسئله بيشينهساز در زماني تأخير اعمال با است گرديده مطرح زمان به حساس تأثير مدلساز انتشار مسئله تعريفشده تحت دو مدل انتشار به نامها مدل آبشار مستقل تأخير و مدل انتشار آستانه خطي تأخير بررسي شده است و مدلها تحت زمان به حساس تأثير بيشينهساز مسئله ميگردد اثبات طرحشده از دسته مسائل سخت ميباشد ازاينرو در اين رساله دو رويكرد متفاوت در حل مسئله اتخاذ شده است در رويكرد اول سه روش مكاشفها بهنامها TSPDEG TSDEG و TSBET بهمنظور حل مسئله مذكور ارائه داده شدهاند در رويكرد دوم دو روش تقريبي به نامها GTSIM و RTSIM پيشنهاد داده شدهاند و اثبات ميگردد كه هر دو روش تقريبي پيشنهاد ميباشند قادر به تضمين حد تقريب 1 1 e
چكيده انگليسي :
Time Sensitive Influence Maximization in Social Networks Azadeh Mohammadi azade mohammadi@gmail com December 12 2016 Department of Electrical and Computer EngineeringIsfahan University of Technology 84156 83111 Isfahan IranMohamad Saraee saraee@cc iut ac irAbdolreza Mirzaei mirzaei@cc iut ac irMohamad Reza Taban Department of Electrical and Computer Engineering Isfahan University of Technology Iran Department of Electrical and Computer Engineering Isfahan University of Technology IranAbstractOne of the most significant problems in social networks analysis is influence maximization problem whichaims to find a set of influential nodes In the real world social networks propagation of information from a nodeto another may incur a certain amount of time delay In addition the value of propagated items might reduce intime Therefore in this thesis we propose the Time Sensitive Influence Maximization TSIM problem whichtakes into account the time dependence of the information value We develop two diffusion models DelayedIndependent Cascade DIC and Delayed Linear Threshold DLT model and prove that the TSIM problem isNP hard under these models For solving the TSIM problem we propose three time sensitive heuristic methodsnamely TSDEG TSPDEG and TSBET as well as two approximation algorithms with 1 1 e approximationratio namely GTSIM and RTSIM We evaluate our methods on five real datasets The experimental resultsshow that our proposed algorithms outperform conventional influence maximization methods In addition comparison of the suggested algorithms shows superiority of RTSIM methods to other algorithms Specifically it outperforms other algorithms in terms of propagation value and at the same time it substantially improvesupon the second best algorithm i e GTSIM method in terms of execution time Key WordsApproximation analysis Influence maximization Information diffusion Social networks Time SensitivediffusionIntroductionA social network is a structure made up of different individuals or organizations and therelationships between them One of the main research interests in social network analysis is tofind a small subset of influential nodes such that they can attract the largest number ofmembers in the network This problem is called influence maximization which is proved tobe NP hard Kempe et al 2003 Different approximation algorithms Borgs et al 2014 Kempe et al 2003 Tang et al 2014 and heuristic methods Jung et al 2012 Mochalovaand Nanopoulos 2013 have been proposed to solve this problem However only somerecent works have considered the temporal aspects in information diffusion Chen et al 2012 Gomez Rodriguez et al 2016 Liu et al 2014 2012 In Gomez Rodriguez et al 2016 the underlying graph is inferred from real propagation data by considering a time delayfactor Chen et al Chen et al 2012 and Liu et al Liu et al 2014 2012 independentlystudied the influence maximization problem with a deadline constraint In all of the previous works the aim is to maximize the number of influenced nodes eitheruntil a deadline is reached or without using any time constraint However in real worldapplications the propagation of influence has some time delay and the value of propagateditems may decrease over time For instance in dissemination of hot topics or urgentinformation the propagated news loses its value gradually As another application in viralmarketing the sooner a company sells its product the faster it receives a return on
استاد راهنما :
محمد حسين سرايي
استاد مشاور :
عبدالرضا ميرزايي
استاد داور :
مازيار پالهنگ، محمد حسين منشئي، علي فانيان
