Volume 6, Issue 3 (Vol. 6, No. 3 2020)                   mmr 2020, 6(3): 373-386 | Back to browse issues page


XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Khademi M, Sheikh Khani N, Khodabakhsh P. Finding Influential Individuals in Social Network Graphs using CSCS Algorithm and Shapley Value in Game Theory. mmr 2020; 6 (3) :373-386
URL: http://mmr.khu.ac.ir/article-1-2800-en.html
1- Islamic Azad University South Tehran Branch , khademi@azad.ac.ir
2- Islamic Azad University South Tehran Branch
Abstract:   (2246 Views)

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../files/site1/files/63/5.pdf

 

Full-Text [PDF 882 kb]   (425 Downloads)    
Type of Study: Original Manuscript | Subject: alg
Received: 2018/06/18 | Revised: 2020/12/27 | Accepted: 2019/01/29 | Published: 2020/11/30 | ePublished: 2020/11/30

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2024 CC BY-NC 4.0 | Mathematical Researches

Designed & Developed by : Yektaweb