Cooperative game theory methods for text ranking

V. V. Mazalov ; V. A. Khitraya ; A. V. Khitryi

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 18 (2022) no. 1, pp. 63-78

Résumé

A method of ranking the corpus of texts of a news portal, based on measures of graph centrality, is proposed. Each text is assigned a vertex of a certain graph, and its structure is determined based on the semantic connectivity of the texts. As a measure of centrality, the Myerson value is used in a cooperative game on a graph, where the number of simple paths in a subgraph of a certain length m is chosen as a characteristic function For different values of m, the ranking based on the Myerson value will be different. For the final ranking, it is proposed to use the ranking procedure based on the tournament matrix. The operation of the ranking algorithm is illustrated by numerical examples related to a specific news porta.

Détail

Keywords: text corpus of news, graph, centrality measure, Myerson value, tournament matrix, ranking procedure.

Bibliographie

[1] Silva A., Lozkins A., Bertoldi L. R., Rigo S., Bure V. M., “Semantic textual similarity on Brazilian Portuguese: An approach based on language-mixture models”, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 15:2 (2019), 235–244 (In Russian) | DOI | MR

[2] Jones K. S., “A statistical interpretation of term specificity and its application in retrieval”, J. Documentation, 60:5 (2004), 493–502 | DOI

[3] Page L., Brin S., Motwani R., Winograd T., “The pagerank citation ranking: Bringing order to the Web”, Proceedings of the $7^{th}$ International World Wide Web Conference (Brisbane, Australia, 1998), 161–172 (accessed: July 15, 2021) http://citeseer.nj.nec.com/page98pagerank.html

[4] Freeman L. C., “A set of measures of centrality based on betweenness”, Sociometry, 40:1 (1977), 35–41 | DOI

[5] Brandes U., “Centrality measures based on current flow”, STACS 2005. $22^{nd}$ Annual Symposium on Theoretical Aspects of Computer Science (Stuttgart, Germany. February 24–26, 2005), Lecture Notes in Computer Science, 3404, eds. V. Diekert, B. Durand, Springer, Stuttgart, 2005, 533–544 | DOI | MR | Zbl

[6] Avrachenkov K., Litvak N., Medyanikov V., Sokol M., “Alpha current flow betweenness centrality”, Algorithms and Models for the Web Graph, $10^{\rm th}$ International Workshop (WAW 2013) (Cambridge, MA, USA, December 14–15, 2013), Lecture Notes in Computer Science, 8305, eds. A. Bonato, M. Mitzenmacher, P. Pralat, Springer, Cambridge, 2013, 106–117 | DOI | MR | Zbl

[7] Avrachenkov K. E., Mazalov V. V., Tsynguev B. T., “Beta current flow centrality for weighted networks”, Computational Social Networks, $4^{\rm th}$ International Conference (CSoNet 2015) (Beijing, China, August 4–6, 2015), Lecture Notes in Computer Science, 9197, 2015, 216–227 | DOI

[8] Newman M. E. J., “A measure of betweenness centrality based on random walks”, Social Networks, 27 (2005), 39–54 | DOI

[9] Jackson M. O., Social and economic networks, Princeton University Press, Princeton, USA, 2008, 504 pp. | DOI | MR | Zbl

[10] Gómez D., González-Arangüena E., Manuel C. et al., “Centrality and power in social networks: a game theoretic approach”, Math. Soc. Sci., 46:1 (2003), 27–54 | DOI | MR | Zbl

[11] Skibski O., Tomasz P., Talal R., “Axiomatic characterization of game theoretic centrality”, J. Artif. Intell. Res., 62 (2018), 33–68 | DOI | MR | Zbl

[12] Mazalov V. V., Trukhina L. I., “Generating functions and the Myerson vector in communication networks”, Diskr. Mat., 26:3 (2014), 65–75 | DOI | MR | Zbl

[13] Avrachenkov K., Kondratev A. Yu., Mazalov V. V., Rubanov D. G., “Network partitioning as cooperative games”, Computational social networks, 5:11 (2018), 1–28

[14] Mazalov V. V., Khitraya V. A., “Modified Mayerson value for determining the centrality of graph vertices”, Mathematical theory players and its supplements, 11:2 (2019), 19–39 (In Russian) | MR | Zbl

[15] Mazalov V. V., Nikitina N. N., “Maximum likelihood method for detecting communities in communication networks”, Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 14:3 (2018), 200–214 (In Russian) | DOI | MR

[16] Korobov M., “Morphological analyzer and generator for russian and ukrainian languages”, Analysis of Images, Social Networks and Texts, Communications in Computer and Information Science, 542, eds. M. Yu. Khachay, N. Konstantinova, A. Panchenko et al., Springer International Publ, Cham, 2015, 320–332 | DOI

[17] Lovins J. B., “Development of a stemming algorithm”, Mech. Transl. Comput. Linguistics, 11:12 (1968), 22–31 (accessed: July 15, 2021) http://www.mtarchive.info/MT1968-Lovins.pdf

[18] Van Rijsbergen C. J., Robertson S. E., Porter M. F., New models in probabilistic information retrieval, Computer Laboratory, Cambridge University Press, Cambridge, USA, 1980, 613 pp.

[19] Harris Z., “Distributional structure”, Word, 10:2–3 (1954), 146–162 | DOI

[20] Manning C. D., Raghavan P., Schütze H., Introduction to information retrieval, Cambridge University Press, Cambridge, USA, 2008, 535 pp. | MR | Zbl

[21] Kondratev A. A., Mazalov V. V., “Ranking procedure with the shapley value”, Intelligent Information and Database Systems, $9^{\rm th}$ Asian Conference (ACIIDS 2017), Proceedings (Kanazawa, Japan. April 3–5, 2017), v. II, Lecture Notes in Computer Science, 10192, eds. by N. T. Nguyen, S. Tojo, L. M. Nguyen, B. Trawinski, 2017, 691–700 | DOI