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

Authors
Maryam Khademi
Nima Sheikh Khani
Pooneh Khodabakhsh
Islamic Azad University South Tehran Branch
10.52547/mmr.6.3.373
Abstract
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
Keywords
community
Game theory
Influence maximization
Shapley Value
social Network
1. Wallis W., "Graph Theory with Applications (JA Bondy and USR Murty)", Society for Industrial and Applied Mathematics (1979).## 2. Fu P., Zhu A., Ni H., Zhao X., Li X., "Threshold behaviors of social dynamics and financial outcomes of Ponzi scheme diffusion in complex networks", Physica A: Statistical Mechanics and its Applications, Vol. 490 (2018) 632-642. ## 3. Yang Y., Xu Y., Wang E., Lou K., Luan D., "Exploring influence maximization in online and offline double-layer propagation scheme", Information Sciences, Vol. 450 (2018) 182-199. ## 4. Narayanam R., Narahari Y., "A shapley value-based approach to discover influential nodes in social networks", IEEE Transactions on Automation Science and Engineering, Vol. 8, No. 1, (2011) 130-147. ## 5. Granovetter M., "Threshold models of collective behavior", American journal of sociology, Vol. 83, No. 6 (1978) 1420-1443. ## 6. Riquelme F., Gonzalez-Cantergiani P., Molinero X., Serna M., "Centrality measure in social networks based on linear threshold model", Knowledge-Based Systems, vol. 140 (2018) 92-102. ## 7. Zhang H., Mishra S., Thai M. T., Wu J., Wang Y., "Recent advances in information diffusion and influence maximization in complex social networks", Opportunistic Mobile Social Networks, Vol. 37, No. 1.1 (2014). ## 8. Scott J., Carrington P. J., "The SAGE handbook of social network analysis", SAGE publications (2011). ## 9. Wasserman S., Faust K., "Social network analysis: Methods and applications", Cambridge university press (1994). ## 10. Radicchi F., Castellano C., Cecconi F., Loreto V., Parisi D., "Defining and identifying communities in networks", Proceedings of the National Academy of Sciences of the United States of America, Vol. 101, No. 9 (2004) 2658-2663. ## 11. Gibbons R., "A primer in game theory", Harvester Wheatsheaf (1992). ## 12. Schmidt C., "Game theory and economic analysis: a quiet revolution in economics", Routledge (2003). ## 13. Osborne M. J.. Rubinstein A., "A course in game theory", MIT press (1994). ## 14. Morton D. D., "Game theory, A nontechnical introduction", Dover publications, Inc., Mineola, NewYork (1983). ## 15. Shapley L., "A Value for N Person Games", RAND P 295, Santa Monica, CA: Rand Corporation (1952). ## 16. Chalkiadakis G., Elkind E., Wooldridge M., "Computational aspects of cooperative game theory," Synthesis Lectures on Artificial Intelligence and Machine Learning, Vol. 5, No. 6 (2011) 1-168. ## 17. Michalak T. P., Aadithya K. V., Szczepanski P. L., Ravindran B., Jennings N. R., "Efficient computation of the Shapley value for game-theoretic network centrality", Journal of Artificial Intelligence Research, Vol. 46 (2013) 607-650. ## 18. Domingos P., Richardson M., "Mining the network value of customers", in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (2001) 57-66. ## 19. Kempe D., Kleinberg J., Tardos E., "Maximizing the spread of influence through a social network", in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (2003) 137-146. ## 20. Leskovec J., et al., "Cost-effective outbreak detection in networks", in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, (2007) 420-429. ## 21. Pandit S., Yang Y., Chawla N. V., "Maximizing information spread through influence structures in social networks," in 2012 IEEE 12th International Conference on Data Mining Workshops (2012) 258-265. ## 22. Zhou S., Yue K., Fang Q., Zhu Y., Liu W., "An efficient algorithm for influence maximization under linear threshold model", in The 26th Chinese Control and Decision Conference (2014 CCDC) (2014) 5352-5357. ## 23. Sinha N., Annappa B., "Cuckoo Search for Influence Maximization in Social Networks", in Proceedings of 3rd International Conference on Advanced Computing, Networking and Informatics(2016) 51-61. ## 24. Yang Y.-C., "A NewGreedy Genetic Algorithm for Influence Maximization in Social Network" (2016). ## 25. Gong M., Yan J., Shen B., Ma L., Cai Q., "Influence maximization in social networks based on discrete particle swarm optimization", Information Sciences, Vol. 367 (2016) 600-614. ## 26. Jiang Q., et al., "Simulated Annealing Based Influence Maximization in Social Networks", in AAAI, Vol. 11 (2011) 127-132. ## 27. Cui L., et al., "DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks", Journal of Network and Computer Applications, Vol. 130 (2018) 119-130. ## 28. Anjerani M., Moeini A., "Selecting influential nodes for detected communities in real-world social networks", in Electrical Engineering (ICEE), 2011 19th Iranian Conference on. IEEE, (2011) 1-6. ## 29. Zachary W. W., "An information flow model for conflict and fission in small groups", Journal of anthropological research (1977) 452-473. ## 30. Isella L., et al., "What's in a crowd? Analysis of face-to-face behavioral networks", Journal of theoretical biology, Vol. 271, No. 1 (2011) 166-180. ## 31. Leskovec J., Mcauley J., "Learning to discover social circles in ego networks", in Advances in neural information processing systems (2012) 539-547. ## 
Mathematical Research
Volume 6, Issue 3 - Serial Number 14
Autumn 2020
Pages 373-386