بررسی مدل ها، تکنیک ها، و کاربردهای مساله افزایش تاثیر
چکیده
افزایش تاثیر، که توسط کمپ و همکارانش [3] تعریف شده است، یک مساله ی مهم در زمینه ی تحلیل شبکه می باشد. هدف این مساله انتخاب k کاربر به عنوان دانه ( seed ) در شبکه ی G، و سپس افزایش وسعت تاثیر در آن شبکه می باشد. مدل های بسیاری برای تقلید رفتار های خاصی از شبکه های اجتماعی طبق مشاهدات شبکه، ارائه شده اند. بر اساس این مدل ها، تکنیک های مختلفی ارائه می شوند و می توانند یک راه حل تقریب عملی، حتی برای شبکه های بزرگ تر، ارائه کنند. در این مقاله، مساله ی افزایش تاثیر فرموله شده، و چند قضیه اثبات می شود. مدل ها و تکنیک های آن، به همراه مجموعه داده ها و کاربرد های متداول آن، جمع بندی می شوند. همچنین مسیر آتی این مساله در انتهای مقاله مورد بحث قرار خواهد گرفت.
1 . مقدمه
با گسترش سریع اینترنت در سراسر دنیا، شبکه های اجتماعی محبوبیت بیشتری به دست می آورند. شبکه های اجتماعی تعداد زیادی از افراد را در بازه ی زمانی کوتاهی به یکدیگر وصل می کند، و روش ارتباط مردم با یکدیگر را تکامل بخشیده اند. اطلاعات در شبکه های اجتماعی منتشر می شوند، ایده ها و دانش از طریق شبکه های اجتماعی به اشتراک گذاشته می شوند، و افراد می توانند از طریق تعامل در شبکه های اجتماعی، بر یکدیگر تاثیر بگذارند. این ویژگی ها دانشمندان جامعه شناسی، اقتصاد، و علوم کامپیوتری را به خود جذب کرده اند. بنابراین، مسائل بسیاری از تحلیل شبکه های اجتماعی، از قبیل مدل های انتشار، و تاثیر اجتماعی، مورد مطالعه قرار می گیرند. مدل های انتشار به منظور مدل سازی رفتار شبکه های اجتماعی مورد مطالعه قرار می گیرند، که به حل مسائل مبتنی بر این مدل ها کمک می کند، از جمله مساله افزایش تاثیر (IM) که در آن هدف یافتن k گره پر تاثیر در شبکه ی اجتماعی است که وسعت تاثیر را افزایش می دهند. یکی از اهداف مطالعه ی تاثیر اجتماعی، حل مساله ی IM می باشد.
8 . نتیجه گیری
این بررسی خلاصه مدل ها، تکنیک ها، مجموعه داده ها و برنامه های کاربردی در مورد مسئله حداکثر سازی نفوذ است. در ابتدا، مشکل IM، فرموله شده و به سادگی تجزیه و تحلیل شده است. یکنواختی و زیرمجموعه نیز اثبات شده است. سپس مدل ها با توجه به رفتار آنها خلاصه می شوند. مدل های بعدی، تکنیک ها متناسب با ایده اصلی در داخل تقسیم می شوند. مجموعه داده ها نیز برای دانستن جزئیات مجموعه داده ها بر طراحی مدل ها و الگوریتم ها تاثیر می گذارد. برای برنامه های کاربردی، حداکثر سازی نفوذ نقش مهمی در بازاریابی دارد، زیرا انتشار نفوذ می تواند به افزایش سود کمک کند. البته، کنترل گسترش نفوذ نیز نزدیک به مشکل IM است. در نهایت، بعضی از دستورالعمل های آینده در مورد این مشکل با توجه به آثار اخیر مورد بحث قرار می گیرد.
Abstract
Influence maximization, defined by Kempe et al. [3] is a hot problem in the field of network analysis. This problem is to target k users as seeds in a network G and then maximize the spread of influence in that network. Many models are proposed to mimic certain behaviours of the social networks according to the observations on the network. Based on these models, various techniques are applied and they can give a feasible approximation solution even for large-scale networks. In this survey, the influence maximization problem will be formulated and some related theorems are proven. Models and techniques will be summarized following the popular datasets and applications. The future direction on this problem will also be talked in the last.
I. INTRODUCTION
With the rapid development of the Internet around the world, social networks become more and more popular. Social networks connect numerous people together within a short period of time and have revolutionized the way people communicate with each other. Information spreads on social networks, ideas and knowledge are shared through social networks, and people can influence others by interaction on social networks. These properties have attracted scientists from sociology, economics as well as computer science. Thus, many problems from social network analysis are studied, such as the diffusion models and the social influence. Diffusion models are studied to model the behaviour of social networks which further help solve some problems based on these models like influence maximization(IM) problem which is to find the k most influential nodes in a social network that maximize the spread of the influence. One of the goal to study the social influence is also to solve the IM problem.
VIII. CONCLUSION
This survey summarizes the models, techniques, datasets, and applications about the influence maximization problem. At first, the IM problem is formulated and simply analysed. The monotonicity and submodularity are also proven. Then models are summarised according to their behaviour. Following models, techniques are divided corresponding to the core idea inside. Datasets are also essential to know the details of the dataset will affect the design of models and algorithms. For the applications, influence maximization plays an important role in marketing since the influence propagation can contribute to the increment of profits. Of course, controlling influence spreading is also closely related to IM problem. At last, some future directions on this problem are discussed according to recent works.
(جهت بزرگ نمایی روی عکس کلیک نمایید)
چکیده
1 . مقدمه
A . ترتیب مقاله
2 . فرموله سازی مساله
A . معرفی و تعریف
B . تعریف مساله
C . یکنواختی
D . شبه ماژولار
E . ورودی
F . خروجی
G . پیچیدگی
H . مسائل مختلف
3 . مدل ها
A . مدل های آبشاری
B . مدل های آستانه
C. تناظر مدل های آبشاری و مدل های آستانه
D . مدل های دیگر
E . جمع بندی ( خلاصه )
4 . فناوری ها
A . تکنیک های حریصانه
B. تکنیک های ارسال تنبل
C. تکنیک های فراابتکاری (metaheuristic)
D. تکنیک های اکتشافی
E. SIMPATH
F. مبتنی بر یادگیری
G. مبتنی بر اجتماع
H. خلاصه
5 . مجموعه داده
A. شبکه های همکاری
B. شبکه های اجتماعی
C. خلاصه
6 . کاربردها
7 . مسیر آینده
8 . نتیجه گیری
منابع
Abstract
I. INTRODUCTION
A. Organization of This Survey
II. PROBLEM FORMALIZATION
A. Notation and Definition
B. Problem Definition
C. Monotonicity
D. Submodularity
E. Input
F. Output
G. Complexity
H. Variant Problems
III. MODELS
A. Cascade Models
B. Threshold Models
C. Equivalence of Cascade Models and Threshold Models
D. Other Models
E. Summary
IV. TECHNIQUES
A. Greedy Techniques
B. Lazy-Forward Techniques
C. Metaheuristic Techniques
D. Heuristic Techniques
E. SIMPATH
F. Learning-based
G. Community based
H. Summary
V. DATASETS
A. Collaboration Networks
B. Social Networks
C. Summary
VI. APPLICATIONS
VII. FUTURE DIRECTIONS
VIII. CONCLUSION
REFERENCES
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه