Rumour Source Detection Using Game Theory.
DOI:
https://doi.org/10.9781/ijimai.2020.10.003Keywords:
Games, Game Theory, Rumour Source Detection (RSD)Abstract
Social networks have become a critical part of our lives as they enable us to interact with a lot of people. These networks have become the main sources for creating, sharing and also extracting information regarding various subjects. But all this information may not be true and may contain a lot of unverified rumours that have the potential of spreading incorrect information to the masses, which may even lead to situations of widespread panic. Thus, it is of great importance to identify those nodes and edges that play a crucial role in a network in order to find the most influential sources of rumour spreading. Generally, the basic idea is to classify the nodes and edges in a network with the highest criticality. Most of the existing work regarding the same focuses on using simple centrality measures which focus on the individual contribution of a node in a network. Game-theoretic approaches such as Shapley Value (SV) algorithms suggest that individual marginal contribution should be measured for a given player as the weighted average marginal increase in the yield of any coalition that this player might join. For our experiment, we have played five SV-based games to find the top 10 most influential nodes on three network datasets (Enron, USAir97 and Les Misérables). We have compared our results to the ones obtained by using primitive centrality measures. Our results show that SVbased approach is better at understanding the marginal contribution, and therefore the actual influence, of each node to the entire network.
Downloads
References
[1] W. Chen, and S.-H. Teng, “Interplay between social influence and network centrality: a comparative study on shapley centrality and single-node-influence centrality,” in WWW ‘17: Proceedings of the 26th International Conference on World Wide Web, 2017, pp. 967–976.
[2] H. Wei, Z. Pan, G. Hu, L. Zhang, H. Yang, X. Li, and X. Zhou, “Identifying influential nodes based on network representation learning in complex networks,” PLoS ONE, vol. 13, 2018, doi: 10.1371/journal.pone.0200091.
[3] J. Zhan, S. Gurung, and S. P. K. Parsa, “Identification of top-k nodes in large networks using katz centrality,” Journal of Big Data, vol. 4, no. 16, 2017, doi: 10.1186/s40537-017-0076-5.
[4] F. A. Rodrigues, “Network centrality: an introduction,” A Mathematical Modeling Approach from Nonlinear Dynamics to Complex Systems, Nonlinear Systems and Complexity, Springer, vol. 22, pp. 177-196, 2019, doi: 10.1007/978-3-319-78512-7_10.
[5] B. A. Bhuiyan, “An overview of game theory and some applications,” Philosophy and Progress, vol. 59, no. 1-2, pp. 111–128, 2018, doi: 10.3329/pp.v59i1-2.36683.
[6] N. Yadati, and R. Narayanam, “Game theoretic models for social network analysis,” in Proceedings of the 20th International Conference Companion on World Wide Web – WWW’ 11, 2011, pp. 291-292.
[7] M. T. Irfan, and L. E. Ortiz, “A game theoretic approach to influence in networks,” in Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI’11), AAAI Press, 2011, pp. 688-694.
[8] T. P. Michalak, K. V. Aadithya, B. Ravindran, N. R. Jennings, and P. L. Szczepanski, “Efficient computation of the shapley value for game-theoretic network centrality,” Journal of Artificial Intelligence Research, vol. 46, no. 1, pp. 607-650, 2013, doi: 10.5555/2512538.2512553.
[9] R. Narayanam, and Y. Narahari, “A shapley value-based approach to discover influential nodes in social networks,” in IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, 2011, pp. 130–147, doi: 10.1109/tase.2010.2052042.
[10] R. Narayanam, and Y. Narahari, “Determining the top-k nodes in social networks using the shapley value,” AAMAS, pp. 1509-1512, 2008, doi: 10.1145/1402821.1402911.
[11] C.-P. Teo, J. Sethuraman, and W.-P. Tan, “Gale-shapley stable marriage problem revisited: strategic issues and applications (extended abstract),” Integer Programming and Combinatorial Optimization Lecture Notes in Computer Science, vol. 1610, pp. 429-438, 1999, doi: 10.1007/3-540-48777- 8_32.
[12] P. Domingos, and M. Richardson, “Mining the network value of customers,” in KDD ‘01: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 57–66.
[13] S. Gao, J. Ma, Z. Chen, G. Wang, and C. Xing, “Ranking the spreading ability of nodes in complex networks based on local structure,” Physica A: Statistical Mechanics and its Applications, vol. 403, pp. 130-147, 2014, doi: 10.1016/j.physa.2014.02.032.
[14] K. Stephenson, and M. Zelen, “Rethinking centrality: methods and examples,” Social Networks, vol. 11, no. 1, pp. 1-37, 1989, doi: 10.1016/0378- 8733(89)90016-6.
[15] L. C. Freeman, “Centraity in social networks conceptual clarification,” Social Networks, vol. 1, no. 3, pp. 215-239, 1978-79, doi: 10.1016/0378- 8733(78)90021-7.
[16] M. A. Al-Garadi, K. D. Varathan, and S. D. Ravana, “Identification of influential spreaders in online social networks using interaction weighted k-core decomposition method,” Physica A: Statistical Mechanics and its Applications, vol. 468, pp. 278-288, 2017, doi: 10.1016/j.physa.2016.11.002.
[17] H.-L. Liu, C. Ma, B.-B. Xiang, M. Tang, and H.-F. Zhang, “Identifying multiple influential spreaders based on generalized closeness centrality,” Physica A: Statistical Mechanics and its Applications, vol. 492, pp. 2237- 2248, 2018, doi: 10.1016/j.physa.2017.11.138.
[18] T. Nie, Z. Guo, K. Zhao, and Z.-M. Lu, “Using mapping entropy to identify node centrality in complex networks,” Physica A: Statistical Mechanics and its Applications, vol. 453, pp. 290-297, 2016, doi: 10.1016/j.physa.2016.02.009.
[19] J. Shetty, and J. Adibi, “Discovering important nodes through graph entropy: the case of enron email database,” in KDD ‘05: Proceedings of the 3rd International Workshop on Link Discovery, 2005, pp. 74–81.
[20] C. W. Tan, P.-D. Yu, L. Zheng, C.-K. Lai, W. Zhang, and H.-L. Fu, “Optimal detection of influential spreaders in online social networks,” in 2016 Annual Conference on Information Science and Systems (CISS), 2016, pp. 145-150.
[21] Y. Zhou, C. Wu, Q. Zhu, Y. Xiang, and S. Loke, “Rumour source detection in networks based on the seir model,” in IEEE Access, vol. 7, 2019, pp. 45240-45258.
[22] F. Liu, and M. Li, “A game theory-based network spreading model: based on game experiments,” International Journal of Machine Learning and Cybernetics, vol. 10, pp. 1449–1457, 2019, doi: 10.1007/s13042-018-0826-5.
[23] T.-H. Fan, and I.-H. Wang, “Rumor source detection: a probabilistic perspective,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 4159-4163.
[24] Y. Zhang, and Y. Zhang, “Top-k influential nodes in social networks: a game perspective,” in Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’17), Association for Computing Machinery, New York, NY, USA, 2017, pp. 1029–1032, doi: 10.1145/3077136.3080709.
[25] T. Qiao, W. Shan, and C. Zhou, “How to identify the most powerful node in complex networks? a novel entropy centrality approach,” Entropy, vol. 19, pp. 614, 2017, doi: 10.3390/e19110614.
[26] J. Hardin, G. Sarkis, and P. C. Urc, “Network analysis with the enron email corpus,” Journal of Statistics Education, vol. 23, 2015, doi: 10.1080/10691898.2015.11889734.
[27] P. Munjal, N. Arora, and H. Banati, “Dynamics of online social network based on parametric variation of relationship,” in 2016 Second International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN), Kolkata, 2016, pp. 241-246.
[28] Bureau of Transportation Statistics. Accessed: July 10, 2020. [Online]. Available: https://transtats.bts.gov/
[29] A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg, “Simplicial closure and higher-order link prediction,” PNAS, vol. 115, no. 48, pp. E11221-E11230, 2018, doi: 10.1073/pnas.1800683115.
[30] email-Enron Dataset. Accessed: Jan. 7, 2020. [Online]. Available: https://www.cs.cornell.edu/~arb/data/email-Enron/index.html
[31] Donald E. Knuth, “The stanford graphbase: a platform for combinatorial computing,” Association for Computing Machinery, New York, NY, USA, 1993.
[32] H. Yang, J. Luo, Y. Liu, M. Yin, and D. Cao, “Discovering important nodes through comprehensive assessment theory on enron email database,” in 3rd International Conference on Biomedical Engineering and Informatics, Yantai, 2010, pp. 3041-3045.
Downloads
Published
-
Abstract217
-
PDF39
Submit Article
Information
