انتشار اطلاعات و نفوذ در شبکه‌های اجتماعی ۲۰۲۲
Information and Influence Propagation in Social Networks 2022

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

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

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

Research on social networks has exploded over the last decade. To a large extent, this has been fueled by the spectacular growth of social media and online social networking sites, which continue growing at a very fast pace, as well as by the increasing availability of very large social network datasets for purposes of research. A rich body of this research has been devoted to the analysis of the propagation of information, influence, innovations, infections, practices and customs through networks. Can we build models to explain the way these propagations occur? How can we validate our models against any available real datasets consisting of a social network and propagation traces that occurred in the past? These are just some questions studied by researchers in this area. Information propagation models find applications in viral marketing, outbreak detection, finding key blog posts to read in order to catch important stories, finding leaders or trendsetters, information feed ranking,etc. A number of algorithmic problems arising in these applications have been abstracted and studied extensively by researchers under the garb of influence maximization. This book starts with a detailed description of well-established diffusion models, including the independent cascade model and the linear threshold model, that have been successful at explaining propagation phenomena. We describe their properties as well as numerous extensions to them, introducing aspects such as competition, budget, and time-criticality, among many others. We delve deep into the key problem of influence maximization, which selects key individuals to activate in order to influence a large fraction of a network. Influence maximization in classic diffusion models including both the independent cascade and the linear threshold models is computationally intractable, more precisely #P-hard, and we describe several approximation algorithms and scalable heuristics that have been proposed in the literature. Finally, we also deal with key issues that need to be tackled in order to turn this research into practice, such as learning the strength with which individuals in a network influence each other, as well as the practical aspects of this research including the availability of datasets and software tools for facilitating research. We conclude with a discussion of various research problems that remain open, both from a technical perspective and from the viewpoint of transferring the results of research into industry strength applications.