پژوهش های ریاضی، جلد ۶، شماره ۳، صفحات ۳۷۳-۳۸۶

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

عنوان انگلیسی Finding Influential Individuals in Social Network Graphs using CSCS Algorithm and Shapley Value in Game Theory
چکیده انگلیسی مقاله

Introduction
In 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 methods
In 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 non-overlapping 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 discussion
In 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.
Conclusion

  • The 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.

 

کلیدواژه‌های انگلیسی مقاله Community, Game theory, Influence maximization, Shapley value, Social network.

نویسندگان مقاله مریم خادمی | Maryam Khademi
Islamic Azad University South Tehran Branch
دانشگاه آزاد اسلامی واحد تهران جنوب

نیما شیخ خانی | Nima Sheikh Khani
Islamic Azad University South Tehran Branch
دانشگاه آزاد اسلامی واحد تهران جنوب

پونه خدابخش | Pooneh Khodabakhsh
Islamic Azad University South Tehran Branch
دانشگاه آزاد اسلامی واحد تهران جنوب


نشانی اینترنتی http://mmr.khu.ac.ir/browse.php?a_code=A-10-637-1&slc_lang=fa&sid=1
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده جبر
نوع مقاله منتشر شده مقاله مستقل
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات