یافتن افراد تاثیرگذار در گراف شبکه های اجتماعی براساس الگوریتم cscs و مقدار شاپلی در نظریه بازی

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

Finding Influential Individuals in Social Network Graphs using CSCS Algorithm and Shapley Value in Game Theory

IntroductionIn recent years, social network analysis gains great deal of attention. Social networks have various applications in different areas, namely predicting disease epidemic, search engines and viral advertisements. A key property of social networks is that interpersonal relationships can influence the decisions that they make. Finding the most influential nodes is important in social networks because such nodes can greatly affect many other people. In this paper, diffusion among nodes is investigated using the centrality of Shapely value and by dividing a network into communities in linear threshold and by the independent cascade model. Furthermore, this algorithm is evaluated by different data sets and compared with benchmarks.Material and methodsIn the proposed algorithm, according to the cooperative game, the value of each coalition is equal to the nodes inside it or at least adjacent to n nodes inside the coalition. After calculating the Shapley value for each node in the social network, the Shapley value of the community is allocated to each community by summing the Shapley values of nodes inside the community which is used as a criteria for community evaluation.It is worth mentioning that a social network is divided into nonoverlapping communities. In other words, each node should belong to only one community. As each community has a unique Shapley value, the fair selection algorithm is utilized to select nodes from communities. Subsequently, the fair selection is applied to the network. Finally, the selected nodes are evaluated to find k influential nodes.Results and discussionIn this research, we propose a heuristic method called CSCS to tackle the influential maximization problem. This open problem focuses on influencing a larger number of individuals within a social network. The proposed algorithm is based on communities and centrality of the Shapley value.In order to evaluate the performance of our algorithm, the CSCS algorithm has been applied to six different social networks and then results are compared with four benchmarks. Results of experiments demonstrate that in the linear threshold model, the CSCS algorithm has an acceptable performance by increasing the number of initial nodes. Furthermore, in the independent cascade model, the CSCS algorithm performance is often similar to the Community Based Degree algorithm and in some cases its even better.ConclusionThe execution time of the algorithm is improved efficiently, and consequently, it can easily be applied on large social networks.In the linear threshold model, the CSCS algorithm has an acceptable performance by increasing the number of initial nodes. Furthermore, in the independent cascade model, the CSCS algorithm performance is often similar to the Community Based Degree algorithm and in some cases its even better.The CSCS algorithm also works well with disconnected social networks because it divides the network into communities../files/site1/files/63/5.pdf